快捷導(dǎo)航

使用python求解迷宮問題的三種實(shí)現(xiàn)方法

更新時(shí)間：2022年03月17日 11:24:42 作者：不吃魚的貓748

關(guān)于迷宮問題,常見會(huì)問能不能到達(dá)某點(diǎn),以及打印到達(dá)的最短路徑,下面這篇文章主要給大家介紹了關(guān)于如何使用python求解迷宮問題的三種實(shí)現(xiàn)方法,需要的朋友可以參考下

前言

在迷宮問題中，給定入口和出口，要求找到路徑。本文將討論三種求解方法，遞歸求解、回溯求解和隊(duì)列求解。

在介紹具體算法之前，先考慮將迷宮數(shù)字化。這里將迷宮用一個(gè)二維的list存儲(chǔ)（即list嵌套在list里），將不可到達(dá)的位置用1表示，可到達(dá)的位置用0表示，并將已經(jīng)到過的位置用2表示。

遞歸求解

遞歸求解的基本思路是：

每個(gè)時(shí)刻總有一個(gè)當(dāng)前位置，開始時(shí)這個(gè)位置是迷宮人口。
如果當(dāng)前位置就是出口，問題已解決。
否則，如果從當(dāng)前位置己無路可走，當(dāng)前的探查失敗，回退一步。
取一個(gè)可行相鄰位置用同樣方式探查，如果從那里可以找到通往出口的路徑，那么從當(dāng)前位置到出口的路徑也就找到了。

在整個(gè)計(jì)算開始時(shí)，把迷宮的人口（序?qū)Γ┳鳛闄z查的當(dāng)前位置，算法過程就是：

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"表示“倒過了”
    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是出口位置，*代表找到的路徑，#代表探索過的路徑。

回溯求解

在回溯解法中，主要是用棧來存儲(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)（如鏈表）。