使用python求解迷宮問(wèn)題的三種實(shí)現(xiàn)方法
前言
在迷宮問(wèn)題中,給定入口和出口,要求找到路徑。本文將討論三種求解方法,遞歸求解、回溯求解和隊(duì)列求解。
在介紹具體算法之前,先考慮將迷宮數(shù)字化。這里將迷宮用一個(gè)二維的list存儲(chǔ)(即list嵌套在list里),將不可到達(dá)的位置用1表示,可到達(dá)的位置用0表示,并將已經(jīng)到過(guò)的位置用2表示。
遞歸求解
遞歸求解的基本思路是:
- 每個(gè)時(shí)刻總有一個(gè)當(dāng)前位置,開(kāi)始時(shí)這個(gè)位置是迷宮人口。
- 如果當(dāng)前位置就是出口,問(wèn)題已解決。
- 否則,如果從當(dāng)前位置己無(wú)路可走,當(dāng)前的探查失敗,回退一步。
- 取一個(gè)可行相鄰位置用同樣方式探查,如果從那里可以找到通往出口的路徑,那么從當(dāng)前位置到出口的路徑也就找到了。
在整個(gè)計(jì)算開(kāi)始時(shí),把迷宮的人口(序?qū)Γ┳鳛闄z查的當(dāng)前位置,算法過(guò)程就是:
- mark當(dāng)前位置。
- 檢查當(dāng)前位置是否為出口,如果是則成功結(jié)束。
- 逐個(gè)檢查當(dāng)前位置的四鄰是否可以通達(dá)出口(遞歸調(diào)用自身)。
- 如果對(duì)四鄰的探索都失敗,報(bào)告失敗。
dirs=[(0,1),(1,0),(0,-1),(-1,0)] #當(dāng)前位置四個(gè)方向的偏移量 path=[] #存找到的路徑 def mark(maze,pos): #給迷宮maze的位置pos標(biāo)"2"表示“倒過(guò)了” maze[pos[0]][pos[1]]=2 def passable(maze,pos): #檢查迷宮maze的位置pos是否可通行 return maze[pos[0]][pos[1]]==0 def find_path(maze,pos,end): mark(maze,pos) if pos==end: print(pos,end=" ") #已到達(dá)出口,輸出這個(gè)位置。成功結(jié)束 path.append(pos) return True for i in range(4): #否則按四個(gè)方向順序檢查 nextp=pos[0]+dirs[i][0],pos[1]+dirs[i][1] #考慮下一個(gè)可能方向 if passable(maze,nextp): #不可行的相鄰位置不管 if find_path(maze,nextp,end):#如果從nextp可達(dá)出口,輸出這個(gè)位置,成功結(jié)束 print(pos,end=" ") path.append(pos) return True return False def see_path(maze,path): #使尋找到的路徑可視化 for i,p in enumerate(path): if i==0: maze[p[0]][p[1]] ="E" elif i==len(path)-1: maze[p[0]][p[1]]="S" else: maze[p[0]][p[1]] =3 print("\n") for r in maze: for c in r: if c==3: print('\033[0;31m'+"*"+" "+'\033[0m',end="") elif c=="S" or c=="E": print('\033[0;34m'+c+" " + '\033[0m', end="") elif c==2: print('\033[0;32m'+"#"+" "+'\033[0m',end="") elif c==1: print('\033[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函數(shù)可以在控制臺(tái)直觀打印出找到的路徑,打印結(jié)果如下:
S是入口位置 ,E是出口位置,*代表找到的路徑,#代表探索過(guò)的路徑。
回溯求解
在回溯解法中,主要是用棧來(lái)存儲(chǔ)可以探索的位置。利用棧后進(jìn)先出的特點(diǎn),在一條分路上探索失敗時(shí),回到最近一次存儲(chǔ)的可探索位置。這是一種深度優(yōu)先搜索的方法。
def maze_solver(maze,start,end): if start==end: print(start) return st=SStack() mark(maze,start) st.push((start,0)) #入口和方向0的序?qū)θ霔? while not st.is_empty(): #走不通時(shí)回退 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) #到達(dá)出口,打印位置 return if passable(maze,nextp): #遇到未探索的新位置 st.push((pos,i+1)) #原位置和下一方向入棧 mark(maze,nextp) st.push((nextp,0)) #新位置入棧 break #退出內(nèi)層循環(huán),下次迭代將以新棧頂作為當(dāng)前位置繼續(xù) print("找不到路徑")
隊(duì)列求解
隊(duì)列求解算法中,以隊(duì)列存儲(chǔ)可以探索的位置。利用隊(duì)列先進(jìn)先出的特點(diǎn),實(shí)現(xiàn)在每個(gè)分支上同時(shí)進(jìn)行搜索路徑,直到找到出口。這是一種廣度優(yōu)先搜索的方法。
def maze_solver_queue(maze,start,end): path.append(start) if start==end: print("找到路徑") return qu=SQueue() mark(maze,start) qu.enqueue(start) #start位置入隊(duì) while not qu.is_empty(): #還有候選位置 pos=qu.dequeue() #取出下一位置 for i in range(4): #檢查每個(gè)方向 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) #新位置入隊(duì) path.append(nextp) print("未找到路徑")
但隊(duì)列求解方法,不能直接得出找到的具體路徑,要得到找到的路徑還需要其他存儲(chǔ)結(jié)構(gòu)(如鏈表)。
總結(jié)
到此這篇關(guān)于使用python求解迷宮問(wèn)題的三種實(shí)現(xiàn)方法的文章就介紹到這了,更多相關(guān)python求解迷宮問(wèn)題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Python多線(xiàn)程threading join和守護(hù)線(xiàn)程setDeamon原理詳解
這篇文章主要介紹了Python多線(xiàn)程threading join和守護(hù)線(xiàn)程setDeamon原理詳解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03詳解Python2.x中對(duì)Unicode編碼的使用
這篇文章主要介紹了詳解Python2.x中對(duì)Unicode編碼的使用,Python3中Unicode被作為默認(rèn)的編碼來(lái)使用,而在目前仍被廣泛應(yīng)用的Python2的版本中Unicode卻是一個(gè)在使用中需要注意的地方,需要的朋友可以參考下2015-04-04新手必備Python開(kāi)發(fā)環(huán)境搭建教程
今天向大家介紹如何搭建Python開(kāi)發(fā)環(huán)境, Python可應(yīng)用于多平臺(tái)包括 Linux 和 Mac OS X,文中有非常詳細(xì)的圖文介紹,需要的朋友可以參考下2021-05-05python實(shí)現(xiàn)在一個(gè)畫(huà)布上畫(huà)多個(gè)子圖
今天小編就為大家分享一篇python實(shí)現(xiàn)在一個(gè)畫(huà)布上畫(huà)多個(gè)子圖,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-01-01Python Pandas中合并數(shù)據(jù)的5個(gè)函數(shù)使用詳解
數(shù)據(jù)合并是數(shù)據(jù)處理過(guò)程中的必經(jīng)環(huán)節(jié),pandas作為數(shù)據(jù)分析的利器,提供了五種常用的數(shù)據(jù)合并方式,讓我們看看如何使用這些方法吧!2022-05-05python爬蟲(chóng)入門(mén)教程--正則表達(dá)式完全指南(五)
要想做爬蟲(chóng),不可避免的要用到正則表達(dá)式,如果是簡(jiǎn)單的字符串處理,類(lèi)似于split,substring等等就足夠了,可是涉及到比較復(fù)雜的匹配,當(dāng)然是正則的天下,下面這篇文章主要給大家介紹了python爬蟲(chóng)之正則表達(dá)式的相關(guān)資料,需要的朋友可以參考下。2017-05-05python獲取系統(tǒng)內(nèi)存占用信息的實(shí)例方法
在本篇文章里小編給大家整理的是關(guān)于python獲取系統(tǒng)內(nèi)存占用信息的實(shí)例方法,有需要的朋友們可以參考學(xué)習(xí)下。2020-07-07Python抓取京東圖書(shū)評(píng)論數(shù)據(jù)
最近接了個(gè)項(xiàng)目,需要抓取京東圖書(shū)的評(píng)論,把代碼放出來(lái)給大家分享下,希望能有所幫助2014-08-08