Python 迷宫,python走迷宫

　　关于迷宫问题，经常会问能不能到达某一点，打印到达该点的最短路径。下面这篇文章主要介绍用python解决迷宫问题的三种方法，有需要的朋友可以参考一下。

　　00-1010前言递归解决方案回溯解决方案队列解决方案摘要

前言

　　递归求解的基本思想是：

　　每时每刻都有一个当前位置。一开始，这个位置就是迷宫人口。如果当前位置是出口，则问题已经解决。否则，如果从当前位置没有出路，当前探索失败，就退一步。取一个可行的相邻位置，用同样的方法探索。如果可以从那里找到出口的路径，那么就可以找到从当前位置到出口的路径。整个计算开始时，将迷宫的种群(序对)作为当前检查的位置，算法过程为：

　　马克现在的位置。检查当前位置是否是出口，如果是，则成功结束。检查当前位置的邻居是否能逐个到达出口(递归调用自身)。如果邻居的探索失败了，报告就失败了。Dirs=[(0，1)，(1，0)，(0，-1)，(-1，0)] #当前位置在四个方向的偏移量

　　Path=[] #保存找到的路径。

　　标记(迷宫，位置)3360 #在迷宫位置标记“2 ”,表示“倒置”

　　迷宫[位置[0]][位置[1]]=2

　　DEF PASSABLE(迷宫，位置)3360 #检查迷宫的位置pos是否可以通过。

　　返回迷宫[位置[0]][位置[1]]==0

　　def find_path(迷宫，位置，终点):

　　标记(迷宫，位置)

　　如果pos==end:

　　Print(pos，end= ) #已经到达出口，输出这个位置。成功结束。

　　path.append(位置)

　　返回True

　　对于范围(4): #内的I，否则，检查四个方向。

　　nextp=位置[0]目录[i][0]，位置[1]目录[i][1]

　　#考虑下一个可能的方向

　　如果可通行(Maze，NextP) 3360 #不管不可行的相邻位置

　　If _ path (maze，nextp，end) 3360 #如果从Nextp可以到达出口，输出这个位置，成功结束。

　　打印(位置，结束= )

　　path.append(位置)

　　返回True

　　返回False

　　See _ path (maze，path) 3360 #将找到的路径可视化。

　　对于I，p在枚举(路径):

　　如果i==0:

　　迷宫[p[0]][p[1]]=E

　　elif i==len(path)-1:

　　迷宫[p[0]][p[1]]=S

　　else:

　　迷宫[p[0]][p[1]]=3

　　打印( \n )

　　对于maze:中的r

　　对于r:中的c

　　如果c==3:

　　打印( \ 033[0；31m * \ 033[0m ，end= )

　　elif c==S 或c==E:

　　打印( \ 033[0；34m c \ 033[0m ，end= )

　　elif c==2:

　　打印( \ 033[0；32m # \ 033[0m ，end= )

　　elif c==1:

　　打印( \0

　　33[0;;40m+" "*2+\033[0m,end="")

　　 else:

　　 print(" "*2,end="")

　　 print()

　　if __name__ == __main__:

　　 maze=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1],\

　　 [1,0,0,0,1,1,0,0,0,1,0,0,0,1],\

　　 [1,0,1,0,0,0,0,1,0,1,0,1,0,1],\

　　 [1,0,1,0,1,1,1,1,0,1,0,1,0,1],\

　　 [1,0,1,0,0,0,0,0,0,1,1,1,0,1],\

　　 [1,0,1,1,1,1,1,1,1,1,0,0,0,1],\

　　 [1,0,1,0,0,0,0,0,0,0,0,1,0,1],\

　　 [1,0,0,0,1,1,1,0,1,0,1,1,0,1],\

　　 [1,0,1,0,1,0,1,0,1,0,1,0,0,1],\

　　 [1,0,1,0,1,0,1,0,1,1,1,1,0,1],\

　　 [1,0,1,0,0,0,1,0,0,1,0,0,0,1],\

　　 [1,1,1,1,1,1,1,1,1,1,1,1,1,1]]

　　 start=(1,1)

　　 end=(10,12)

　　 find_path(maze,start,end)

　　 see_path(maze,path)

　　代码中see_path函数可以在控制台直观打印出找到的路径，打印结果如下:

　　S是入口位置，E是出口位置，*代表找到的路径，#代表探索过的路径。

回溯求解

　　在回溯解法中，主要是用栈来存储可以探索的位置。利用栈后进先出的特点，在一条分路上探索失败时，回到最近一次存储的可探索位置。这是一种深度优先搜索的方法。

def maze_solver(maze,start,end):
　　 if start==end:
　　 print(start)
　　 return
　　 st=SStack()
　　 mark(maze,start)
　　 st.push((start,0)) #入口和方向0的序对入栈
　　 while not st.is_empty(): #走不通时回退
　　 pos,nxt=st.pop() #取栈顶及其检查方向
　　 for i in range(nxt,4): #依次检查未检查方向，算出下一位置
　　 nextp = pos[0] + dirs[i][0], pos[1] + dirs[i][1]
　　 if nextp==end:
　　 print_path(end,pos,st) #到达出口，打印位置
　　 return
　　 if passable(maze,nextp): #遇到未探索的新位置
　　 st.push((pos,i+1)) #原位置和下一方向入栈
　　 mark(maze,nextp)
　　 st.push((nextp,0)) #新位置入栈
　　 break #退出内层循环，下次迭代将以新栈顶作为当前位置继续
　　 print("找不到路径")

队列求解

　　队列求解算法中，以队列存储可以探索的位置。利用队列先进先出的特点，实现在每个分支上同时进行搜索路径，直到找到出口。这是一种广度优先搜索的方法。

def maze_solver_queue(maze,start,end):
　　 path.append(start)
　　 if start==end:
　　 print("找到路径")
　　 return
　　 qu=SQueue()
　　 mark(maze,start)
　　 qu.enqueue(start) #start位置入队
　　 while not qu.is_empty(): #还有候选位置
　　 pos=qu.dequeue() #取出下一位置
　　 for i in range(4): #检查每个方向
　　 nextp = pos[0] + dirs[i][0], pos[1] + dirs[i][1]
　　 if passable(maze,nextp): #找到新的探索方向
　　 if nextp==end: #是出口，成功
　　 print("找到路径")
　　 path.append(end)
　　 return
　　 mark(maze,nextp)
　　 qu.enqueue(nextp) #新位置入队
　　 path.append(nextp)
　　 print("未找到路径")

　　但队列求解方法，不能直接得出找到的具体路径，要得到找到的路径还需要其他存储结构（如链表）。

总结

　　到此这篇关于使用python求解迷宫问题的三种实现方法的文章就介绍到这了,更多相关python求解迷宫问题内容请搜索盛行IT软件开发工作室以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT软件开发工作室！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

目录

前言

回溯求解

队列求解

总结

相关文章阅读