运维开发网

用python解决迷宫问题的三种方法

运维开发网 https://www.qedev.com 2022-06-30 21:45 出处:网络
关于迷宫问题,常见会问能不能到达某点,以及打印到达的最短路径,下面这篇文章主要给大家介绍了关于如何使用python求解迷宫问题的三种实现方法,需要的朋友可以参考下

关于迷宫问题,常见会问能不能到达某点,以及打印到达的最短路径,下面这篇文章主要给大家介绍了关于如何使用python求解迷宫问题的三种实现方法,需要的朋友可以参考下


前言

在迷宫问题中,给定入口和出口,就要求找到路径。本文将讨论三种解决方案:递归解决方案、回溯解决方案和队列解决方案。

在介绍具体算法之前,先考虑把迷宫数字化。这里,迷宫存储在一个二维列表中(即列表嵌套在列表中),不可到达的位置用1表示,可到达的位置用0表示,已经访问过的位置用2表示。



递归求解

递归求解的基本思想是:

每时每刻都有一个当前位置。一开始,这个位置就是迷宫人口。

如果当前位置是出口,则问题已经解决。

否则,如果从当前位置没有出路,当前探索失败,就退一步。

取一个可行的相邻位置,用同样的方法探索。如果从那里可以找到出口的路径,那么就可以找到从当前位置到出口的路径。

整个计算开始时,将迷宫的种群(序对)作为当前检查的位置,算法过程为:

马克现在的位置。

检查当前位置是否是出口,如果是,则成功结束。

检查当前位置的邻居是否能逐个到达出口(递归调用自身)。

如果邻居的探索失败了,报告就失败了。

dirs=[(0,1),(1,0),(0,-1),(-1,0)]#当前位置四个方向的偏移量path=[]#存找到的路径defmark(maze,pos):#给迷宫maze的位置pos标quot;2quot;表示“倒过了”maze[pos[0]][pos[1]]=2defpassable(maze,pos):#检查迷宫maze的位置pos是否可通行returnmaze[pos[0]][pos[1]]==0deffind_path(maze,pos,end):mark(maze,pos)ifpos==end:print(pos,end=quot;quot;)#已到达出口,输出这个位置。成功结束path.append(pos)returnTrueforiinrange(4):#否则按四个方向顺序检查nextp=pos[0]+dirs[i][0],pos[1]+dirs[i][1]#考虑下一个可能方向ifpassable(maze,nextp):#不可行的相邻位置不管iffind_path(maze,nextp,end):#如果从nextp可达出口,输出这个位置,成功结束print(pos,end=quot;quot;)path.append(pos)returnTruereturnFalsedefsee_path(maze,path):#使寻找到的路径可视化fori,pinenumerate(path):ifi==0:maze[p[0]][p[1]]=quot;Equot;elifi==len(path)-1:maze[p[0]][p[1]]=quot;Squot;else:maze[p[0]][p[1]]=3print(quot;\nquot;)forrinmaze:forcinr:ifc==3:print(#39;\033[0;31m#39;+quot;*quot;+quot;quot;+#39;\033[0m#39;,end=quot;quot;)elifc==quot;Squot;orc==quot;Equot;:print(#39;\033[0;34m#39;+c+quot;quot;+#39;\033[0m#39;,end=quot;quot;)elifc==2:print(#39;\033[0;32m#39;+quot;#quot;+quot;quot;+#39;\033[0m#39;,end=quot;quot;)elifc==1:print(#39;\033[0;;40m#39;+quot;quot;*2+#39;\033[0m#39;,end=quot;quot;)else:print(quot;quot;*2,end=quot;quot;)print()if__name__==#39;__main__#39;: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是出口位置,*代表找到的路径,#代表探索的路径。


回溯求解

在回溯法中,堆栈主要用于存储可以探索的位置。利用堆栈的后进先出特性,当分支路径上的探索失败时,用户可以返回到最后存储的可探索位置。这是一种深度优先的搜索方法。

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


队列求解

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

defmaze_solver_queue(maze,start,end):path.append(start)ifstart==end:print(quot;找到路径quot;)returnqu=SQueue()mark(maze,start)qu.enqueue(start)#start位置入队whilenotqu.is_empty():#还有候选位置pos=qu.dequeue()#取出下一位置foriinrange(4):#检查每个方向nextp=pos[0]+dirs[i][0],pos[1]+dirs[i][1]ifpassable(maze,nextp):#找到新的探索方向ifnextp==end:#是出口,成功print(quot;找到路径quot;)path.append(end)returnmark(maze,nextp)qu.enqueue(nextp)#新位置入队path.append(nextp)print(quot;未找到路径quot;)

而队列求解法无法直接找到具体路径,需要其他存储结构(如链表)才能得到找到的路径。


总结

关于用python解决迷宫问题的三种方法,本文到此结束。关于用python解决迷宫问题的更多信息

0

精彩评论

暂无评论...
验证码 换一张
取 消