制作迷宮地圖和行走路線（6）
說在前面
在繪制迷宮地圖時(shí)，除了深度優(yōu)先搜索算法，我們還可以使用廣度優(yōu)先搜索算法。因?yàn)榈貓D信息是由二維數(shù)組maze來決定的，所以無(wú)論是采用哪種算法，最終畫出來的圖形是一樣的，區(qū)別在于繪制的過程不同。
廣度優(yōu)先搜索算法通過設(shè)置隊(duì)列數(shù)據(jù)結(jié)構(gòu)，采用先進(jìn)先出的順序，依次繪制每個(gè)通道節(jié)點(diǎn)的相鄰位置，直至繪制出整個(gè)地圖。今天我們就來研究使用廣度優(yōu)先搜索算法繪制地圖、采用廣度優(yōu)先搜索算法尋找并繪制最短路徑路線圖的方法。
第5節(jié)?使用廣度優(yōu)先搜索算法繪制二維迷宮
因?yàn)楸竟?jié)課是建立在上一節(jié)課內(nèi)容的基礎(chǔ)上，二維數(shù)組maxe和book的含義均保持不變，只有少量函數(shù)調(diào)用發(fā)生了變化，所以我們只分析變化部分的代碼。
首先是主函數(shù)部分，把調(diào)用函數(shù)dfs()使用深度優(yōu)先搜索算法繪制迷宮，改成調(diào)用函數(shù)bfs()使用廣度優(yōu)先搜索算法繪制迷宮。參考代碼如下：
for i in range(h):for j in range(w):if maze[i][j] == 1 and book[i][j] == 0:tt.penup()bfs(i, j)
自定義函數(shù)bfs()有兩個(gè)參數(shù)r和c，分別表示當(dāng)前格子在二維數(shù)組maze中的行、列下標(biāo)。若當(dāng)前位置(r, c)為未訪問過的通道，則先設(shè)置book[r][c]=1標(biāo)記位置(r, c)來過了。然后將位置(r, c)加入到隊(duì)列q中。之后就是出隊(duì)、入隊(duì)等常用隊(duì)列操作手法了。
先將隊(duì)首元素出隊(duì)，調(diào)用函數(shù)draw_rectangle()在該處繪制白色矩形。然后依次將(r, c)周圍的通道位置加入到隊(duì)列中，并依次處理隊(duì)列元素，直至隊(duì)列為空，就把與(r, c)連通的所有位置都繪制成白色矩形了。
自定義函數(shù)及函數(shù)頭說明如下：
'''函數(shù)功能：使用廣度優(yōu)先搜索來生成迷宮函數(shù)名：dfs(r, c)參數(shù)表：r,c -- 表示當(dāng)前格子在二維數(shù)組maze中的行列下標(biāo)。返回值：把二維數(shù)組book當(dāng)做全局變量，直接使用畫筆繪制迷宮通道，不需要返回值。'''def bfs(r, c):from queue import Queue #引入queue模塊FIFO隊(duì)列Queueq = Queue()# 標(biāo)記(r, c)來過book[r][c] = 1q.put((r, c))while not q.empty():r, c = q.get()draw_rectangle(start_x+c*size-size//2, start_y-r*size+size//2, size, size, 'white')# (r, c)的上下左右位置d = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]for (i, j) in d:if 0<=iand 0<=jand maze[i][j]==1 and book[i][j]==0: book[i][j] = 1q.put((i, j))
2.使用廣度優(yōu)先搜索算法尋找并繪制最短路徑：
繪制好迷宮地圖以后，就可以輸入起點(diǎn)和終點(diǎn)坐標(biāo)，尋找連接二者的路徑了。因?yàn)樵诶L制地圖過程中，二維數(shù)組book的值發(fā)生了變化，所以需要先將book歸零，以便重新遍歷地圖。
與深度優(yōu)先搜索算法不同的是，使用廣度優(yōu)先搜索算法搜索路徑時(shí)，需要定義一個(gè)字典path來記錄每個(gè)節(jié)點(diǎn)的入隊(duì)介紹人（即前驅(qū)節(jié)點(diǎn)），起點(diǎn)的前驅(qū)為其本身。有了字典path，我們就可以通過從終點(diǎn)開始，遍歷路徑上各節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，從而實(shí)現(xiàn)逆序繪制路徑功能。
我們從起點(diǎn)(r1, c1)開始，調(diào)用函數(shù)bfs_ans()，使用廣度優(yōu)先搜索來尋找路徑，并返回存儲(chǔ)了各節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)信息的字典path。最后調(diào)用函數(shù)print_path()逆序繪制路徑。
主函數(shù)中調(diào)用函數(shù)的代碼如下：
# 使用廣度優(yōu)先搜索來尋找路徑book = [[0] * w for i in range(h)] # 將book歸零，重新遍歷地圖book[r1][c1] = 1 # 標(biāo)記起點(diǎn)已經(jīng)去過了path = bfs_ans(r1, c1) # 使用廣度優(yōu)先搜索來尋找路徑print_path() # 輸出使用廣度優(yōu)先搜索獲得的路徑
自定義函數(shù)bfs_ans()有兩個(gè)參數(shù)r1和c1，表示起點(diǎn)在二維數(shù)組maze中的行、列下標(biāo)。
函數(shù)bfs_ans()與bfs()的算法結(jié)構(gòu)相似，都是先將起點(diǎn)坐標(biāo)入隊(duì)，再按照隊(duì)列基本操作處理。區(qū)別僅在于循環(huán)體中。因?yàn)閎fs()函數(shù)需要繪制出所有可通行的位置，故循環(huán)條件為隊(duì)列不為空；但是bfs_ans()函數(shù)是找到終點(diǎn)就可以跳出循環(huán)了。此外，在bfs_ans()函數(shù)中，我們每讓一個(gè)新位置(i, j)加入隊(duì)列，就要執(zhí)行語(yǔ)句path[(i, j)] = (r, c)，將其入隊(duì)介紹人（前驅(qū)節(jié)點(diǎn)）添加到字典path中，以便今后繪制路徑。
自定義函數(shù)及函數(shù)頭說明如下：
'''函數(shù)功能：使用廣度優(yōu)先搜索來尋找路徑函數(shù)名：bfs_ans(r1, c1)參數(shù)表：r1,c1 -- 表示起點(diǎn)在二維數(shù)組maze中的行列下標(biāo)。返回值：把列表book當(dāng)做全局變量，返回存儲(chǔ)了各格子前驅(qū)位置的字典path。'''def bfs_ans(r1, c1):from queue import Queue # 引入queue模塊FIFO隊(duì)列Queueq = Queue()path = {(r1, c1): (r1, c1)} #用字典記錄其前驅(qū)位置，起點(diǎn)的前驅(qū)為其本身# 標(biāo)記(r1, c1)來過book[r1][c1] = 1q.put((r1, c1))while not q.empty():r, c = q.get()if r==r2 and c==c2:break# (r, c)的上下左右位置d = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]for (i, j) in d:if 0<=iand 0<=jand maze[i][j]==1 and book[i][j]==0: book[i][j] = 1q.put((i, j))path[(i, j)] = (r, c)return path
這里順便給出一個(gè)思考題：如果你想要順序繪制路徑，該怎么處理呢？
答案就是先將字典path中鍵和值的位置互換，使得字典元素以前驅(qū)節(jié)點(diǎn)的坐標(biāo)為鍵、后繼節(jié)點(diǎn)的坐標(biāo)為值，終點(diǎn)的后繼為其本身。這樣就可以從起點(diǎn)開始繪制路徑了。
自定義函數(shù)及函數(shù)頭說明如下：
'''函數(shù)功能：根據(jù)path的值，逆序繪制使用廣度優(yōu)先搜索獲得的路徑函數(shù)名：print_path()參數(shù)表：直接使用字典path的元素值，不需要任何參數(shù)。返回值：直接利用畫筆繪制路線，不需要返回值。'''def print_path():tt.speed(1)# 路線粗細(xì)tt.pensize(size*0.3)tt.color("green")tt.penup()tt.goto(start_x+c2*size, start_y-r2*size)tt.pendown()pos = path[(r2, c2)]# 根據(jù)前驅(qū)結(jié)點(diǎn)信息，逆序遍歷路徑，起點(diǎn)的前驅(qū)為其本身while path[pos] != pos:tt.goto(start_x+pos[1]*size, start_y-pos[0]*size)pos = path[pos]tt.goto(start_x+pos[1]*size, start_y-pos[0]*size)
到此，關(guān)于制作迷宮地圖和行走路線的系列文章就告一段落了。根據(jù)文章的介紹，我們知道了，在已有二維數(shù)組maze的基礎(chǔ)上，可以使用深度優(yōu)先或廣度優(yōu)先搜索算法來繪制地圖，雖然繪制過程不同，但最終形成的圖像是一樣的。
在使用深度優(yōu)先搜索算法尋找路徑時(shí)，如果我們隨機(jī)打亂周圍位置的訪問順序，就能夠獲得一條隨機(jī)搜索路線；使用廣度優(yōu)先搜索算法獲得的是最短路徑，我們可以通過設(shè)置字典鍵值對(duì)的方式，在前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)之間建立聯(lián)系，從而繪制出路線圖。
課后練習(xí)
迷宮問題是學(xué)習(xí)二維數(shù)組、棧和隊(duì)列的經(jīng)典案例。在本專題的系列文章中，我們使用隊(duì)列來實(shí)現(xiàn)廣度優(yōu)先搜索算法，使用遞歸函數(shù)來實(shí)現(xiàn)深度優(yōu)先搜索算法，并沒有使用到棧結(jié)構(gòu)。但是在浙教版選考信息技術(shù)教材中，對(duì)遞歸函數(shù)的掌握要求較低，而對(duì)棧的掌握要求較高，所以更多的題目中是要求用棧來模擬遞歸過程，實(shí)現(xiàn)非遞歸算法。
現(xiàn)在請(qǐng)你使用棧來模擬遞歸過程，使用深度優(yōu)先搜索算法尋找路徑，并用綠色畫筆把路徑繪制出來。
需要本文PPT、源代碼和課后練習(xí)答案的，可以加入“Python算法之旅”知識(shí)星球參與討論和下載文件，“Python算法之旅”知識(shí)星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。
我們專注Python算法，感興趣就一起來！
相關(guān)優(yōu)秀文章：