制作迷宮地圖和行走路線（4）

說(shuō)在前面

前3節(jié)課我們分別構(gòu)造了不含環(huán)和含環(huán)兩種迷宮，然后使用深度優(yōu)先搜索算法尋找路徑，并繪制了路線圖。不含環(huán)迷宮中任意兩個(gè)點(diǎn)之間的連通路徑都是唯一的，含環(huán)迷宮則可能存在多條不同路徑。采用深度優(yōu)先搜索算法時(shí)，若隨機(jī)設(shè)置每次前進(jìn)的方向，則每次尋找的路徑都可能不一樣。

在搜索迷宮路徑時(shí)，除了深度優(yōu)先搜索算法，我們還可以使用廣度優(yōu)先搜索算法。它采用隊(duì)列數(shù)據(jù)結(jié)構(gòu)，依次處理相鄰格子，可以尋找到最短路徑。今天我們就來(lái)研究廣度優(yōu)先搜索算法尋路，并繪制最短路徑路線圖。

第4節(jié)?使用廣度優(yōu)先搜索算法尋找路徑

自定義函數(shù)bfs_ans()使用廣度優(yōu)先搜索算法尋找路徑。它采用隊(duì)列數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)各個(gè)格子的行列下標(biāo)。先將起點(diǎn)坐標(biāo)加入隊(duì)列，然后依次處理隊(duì)列中的元素，直至隊(duì)列為空或找到終點(diǎn)為止。

參考代碼如下：

'''函數(shù)功能：使用廣度優(yōu)先搜索來(lái)尋找路徑函數(shù)名：bfs_ans(r1, c1)參數(shù)表：r1,c1 -- 表示起點(diǎn)在二維數(shù)組maze中的行列下標(biāo)。返回值：把列表maze當(dāng)做全局變量，返回存儲(chǔ)了各格子前驅(qū)位置的字典path。''' def bfs_ans(r1, c1):    from queue import Queue  # 引入queue模塊FIFO隊(duì)列Queue    q = Queue()    path = {(r1, c1): (r1, c1)} #用字典記錄其前驅(qū)位置，起點(diǎn)的前驅(qū)為其本身    # 標(biāo)記(r1, c1)來(lái)過(guò)    maze[r1][c1] = 1    q.put((r1, c1))    while not q.empty():        r, c = q.get()        if r==r2 and c==c2: #遇到終點(diǎn)，跳出循環(huán)            break        for (i, j) in route[r][c]:             if maze[i][j] == 0: #將滿足條件的相鄰格子加入隊(duì)列                maze[i][j] = 1                q.put((i, j))                path[(i, j)] = (r, c) #記錄(i, j)的前驅(qū)位置(r, c)    return path

代碼說(shuō)明：

循環(huán)體內(nèi)的操作步驟如下：首先將隊(duì)頭元素出隊(duì)，把它作為當(dāng)前格子(r, c)來(lái)處理，然后判斷(r, c)是否為終點(diǎn)，若是直接跳出循環(huán)；否則遍歷當(dāng)前格子的相鄰格子，將滿足條件的相鄰格子加入隊(duì)列。同時(shí)，為了記錄路徑，還需要把每個(gè)格子的前驅(qū)位置存儲(chǔ)到字典path中。

path中鍵值對(duì)的形式為(i, j):(r, c)，鍵和值都是記錄格子位置的元組，表示(r, c)是(i,j)的前驅(qū)位置。我們?cè)O(shè)置起點(diǎn)的前驅(qū)位置為它本身，即設(shè)置path的初值為path = {(r1, c1): (r1, c1)}。之后在處理當(dāng)前格子(r, c)時(shí)，每添加一個(gè)相鄰格子(i,j)到隊(duì)列中，就記錄path[(i, j)] = (r, c)，表示(r, c)是(i, j)的前驅(qū)位置。

最后返回字典path，以便后續(xù)繪制路線圖。

2.逆序繪制使用廣度優(yōu)先搜索獲得的路徑：

有了字典path，我們就可以繪制路線圖了。因?yàn)樽值?/span>path存儲(chǔ)的是每個(gè)格子的前驅(qū)位置，所以只能從終點(diǎn)開(kāi)始逆序繪制路線。

自定義函數(shù)print_path()根據(jù)path的值，逆序繪制使用廣度優(yōu)先搜索獲得的路徑。

它先將畫(huà)筆放到終點(diǎn)位置，然后根據(jù)前驅(qū)位置信息，逆序遍歷路徑。利用起點(diǎn)的前驅(qū)為其本身可以結(jié)束循環(huán)。最后繪制起點(diǎn)位置。參考代碼如下：

'''函數(shù)功能：根據(jù)path的值，逆序繪制使用廣度優(yōu)先搜索獲得的路徑函數(shù)名：print_path()參數(shù)表：直接使用字典path的元素值，不需要任何參數(shù)。返回值：直接利用畫(huà)筆繪制路線，不需要返回值。''' 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)

3.主函數(shù)部分增加代碼：

我們可以在上一節(jié)內(nèi)容的基礎(chǔ)上增加廣度優(yōu)先搜索并繪制路徑的功能。只需在主函數(shù)部分增加如下代碼即可：

# 使用廣度優(yōu)先搜索來(lái)尋找路徑maze =[[0] * w for i in range(h)] # 將maze歸零，重新遍歷地圖maze[r1][c1]= 1  # 標(biāo)記起點(diǎn)已經(jīng)去過(guò)了path =bfs_ans(r1, c1)  # 使用廣度優(yōu)先搜索來(lái)尋找路徑print_path()     # 輸出使用廣度優(yōu)先搜索獲得的路徑

代碼說(shuō)明：

前面我們已經(jīng)繪制了迷宮，并使用深度優(yōu)先搜索算法繪制了路徑。因?yàn)榍懊嫠阉髀窂綍r(shí)修改了數(shù)組maze的值，為了重新遍歷地圖，我們需要將maze歸零。先標(biāo)記起點(diǎn)(r1, c1)已經(jīng)去過(guò)了，然后調(diào)用函數(shù)bfs_ans(r1, c1)，并返回path，最后調(diào)用函數(shù)print_path()繪制路徑。

這樣深度優(yōu)先搜索和廣度優(yōu)先搜索獲得的路徑就能夠同時(shí)呈現(xiàn)在地圖上。

?

課后練習(xí)

本例中我們使用字典path記錄了各位置的前驅(qū)位置，故而可以遍歷字典path，從終點(diǎn)到起點(diǎn)逆序輸出路徑。但通常我們更習(xí)慣順序輸出路徑。你能否想辦法對(duì)字典path中的元素加以處理，使得能夠?qū)崿F(xiàn)從起點(diǎn)到終點(diǎn)順序繪制路徑的功能呢？

需要本文PPT、源代碼和課后練習(xí)答案的，可以加入“Python算法之旅”知識(shí)星球參與討論和下載文件，“Python算法之旅”知識(shí)星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

我們專注Python算法，感興趣就一起來(lái)！

相關(guān)優(yōu)秀文章：

閱讀代碼和寫(xiě)更好的代碼

最有效的學(xué)習(xí)方式

Python算法之旅文章分類