目錄

一、引入

二、具體細(xì)節(jié)

1、BFS（Breadth First Search）

2、Dijkstra（Uniform Cost Search）

3、啟發(fā)式（Heuristic search）

4、A*算法

4.1 算法細(xì)節(jié)

4.2 A與A*算法

4.3 A*算法證明

4.4 算法過(guò)程

三、具體實(shí)現(xiàn)

1、實(shí)驗(yàn)要求

2、代碼實(shí)現(xiàn)

四、源代碼

一、引入

? ? ? ?當(dāng)我開(kāi)始學(xué)習(xí)該算法時(shí)，網(wǎng)上已經(jīng)有了很多優(yōu)秀的介紹性文章了。如果你看到了文章中出現(xiàn)了以下有著紅色星星★和紫色×的路徑圖：

? ? ? ? 那么該文章很大概率參考了Red Blob Games（點(diǎn)擊跳轉(zhuǎn)）的A*算法教程。該教程是一個(gè)很不錯(cuò)的引入教程，有著很生動(dòng)的交互式圖表和簡(jiǎn)單易懂的描述過(guò)程。

????????以下通過(guò)BFS、貪婪BFS、Dijkstra算法作為引入逐步引入A*算法，使得對(duì)于A*算法有一個(gè)初步的整體了解。

????????Red Blob Games里面有三張圖來(lái)說(shuō)明BFS、Dijkstra、A*算法的的區(qū)別，如果有點(diǎn)基礎(chǔ)的其實(shí)看完就知道個(gè)大概了：

? ? ? ? BFS（Breadth First Search?）：每一個(gè)方向都平等的擴(kuò)展，因此它的探索軌跡是一圈又一圈的同心圓，像漣漪一樣一圈一圈均勻地往外擴(kuò)展。

????????我們知道BFS擴(kuò)展的時(shí)候是對(duì)一個(gè)節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)依次擴(kuò)展，每個(gè)節(jié)點(diǎn)被擴(kuò)展的機(jī)會(huì)是公平的，即各個(gè)鄰接節(jié)點(diǎn)的擴(kuò)展機(jī)會(huì)一樣，順序任意。在迷宮問(wèn)題中表現(xiàn)為，選一個(gè)節(jié)點(diǎn)的右、上、左、下（不一定要右上左下，你想上下左右都可以）節(jié)點(diǎn)加入到隊(duì)列里面，然后按放進(jìn)去的順序從隊(duì)列取出來(lái)節(jié)點(diǎn)繼續(xù)擴(kuò)展，同樣是將這個(gè)節(jié)點(diǎn)的右、上、左、下節(jié)點(diǎn)加入隊(duì)列。那么在迷宮上展現(xiàn)的過(guò)程就是對(duì)這個(gè)節(jié)點(diǎn)距離為1的一圈搜索一遍，然后又搜索距離為2的一圈、距離為3的一圈……

????????具體動(dòng)畫(huà)效果如下：

????????從上面可以看到，對(duì)于迷宮問(wèn)題以及其他路徑權(quán)重相等的圖搜索中，BFS是一種非常有用的算法。BFS一定可以搜索到所有可以到達(dá)的節(jié)點(diǎn)，它是一種暴力的窮盡查找算法，并且能找到最短路徑（前提所有邊權(quán)相等）。

? ? ? ? Dijkstra算法（Dijkstra’s Algorithm?）：某些節(jié)點(diǎn)（方向、路徑）會(huì)優(yōu)先被探索，一般是那些具有更小代價(jià)的節(jié)點(diǎn)和路徑會(huì)被優(yōu)先探索。因?yàn)樵撍惴ㄊ怯脕?lái)求最短路的，算法正確性要求每次都要選擇當(dāng)前已知的最短路進(jìn)行探索，因此它的探索軌跡是隨機(jī)的、不均勻的，就像山脊的等高線圖一樣。

????????Dijkstra相比BFS的區(qū)別就是此時(shí)圖的各條邊的邊權(quán)不同了，此時(shí)BFS不再適用。

? ? ? ? 還是迷宮問(wèn)題，方塊里面的值表示起點(diǎn)★到該方塊的代價(jià)（cost）(可以理解為距離、花費(fèi)的成本)，左圖中移動(dòng)到相鄰方塊的代價(jià)都是1，右圖中移動(dòng)到相鄰方塊的權(quán)值視方塊顏色而定：移動(dòng)到棕色■的代價(jià)是1，移動(dòng)到綠色■的代價(jià)是5，灰色■表示不可穿越的障礙。

????????左圖中因?yàn)楦鱾€(gè)方塊代價(jià)一致，使用BFS算法，算法會(huì)直接穿過(guò)綠色區(qū)域到達(dá)終點(diǎn)×；右圖中因?yàn)榉綁K代價(jià)不同，使用Dijkstra算法，算法則會(huì)繞過(guò)綠色區(qū)域到達(dá)終點(diǎn)×。

????????它倆算法的執(zhí)行動(dòng)畫(huà)如下：? ? ? ?

????????具體BFS和Dijkstra算法過(guò)程下面會(huì)詳細(xì)介紹，這里只需要知道他們應(yīng)用的區(qū)別。

? ? ? ? A*算法：它優(yōu)先考慮“似乎”更接近目標(biāo)的路徑。該算法也是不斷尋找估計(jì)的“當(dāng)前最有潛力”的節(jié)點(diǎn)，和Dijkstra算法一樣都是不均勻的山脊圖。但相比Dijkstra算法的雜亂無(wú)章的山脊軌跡，它是有目的性、方向性的，軌跡擴(kuò)展方向總是選擇更靠近目標(biāo)的那一側(cè)，下面的圖可以看到一直往尖端的一側(cè)伸展，因?yàn)樵贏*算法眼中那里更接近終點(diǎn)。

? ? ? ? 它是對(duì) Dijkstra 算法的修改，針對(duì)單個(gè)目標(biāo)進(jìn)行了優(yōu)化。Dijkstra的算法可以發(fā)現(xiàn)到達(dá)所有位置的路徑。但是在我們尋路算法中，我們可能只需要尋找到達(dá)一個(gè)位置的路徑，這意味著Dijkstra算法中的一些額外開(kāi)銷是不必要的。A*算法是一種單點(diǎn)對(duì)單點(diǎn)的路徑尋找算法，就像在LOL中點(diǎn)擊小地圖的某個(gè)位置，系統(tǒng)會(huì)自動(dòng)尋路，得到通往目的位置的一條“白線”，來(lái)表示它是最短的路徑。

????????它會(huì)利用自己一些已知的啟發(fā)信息，來(lái)合理規(guī)劃自己的探索方向，避免了Dijkstra的一些盲目性。

二、具體細(xì)節(jié)

????????在這里需要提一點(diǎn)的是，下面討論的A*算法僅僅作為一種尋路算法，討論的也是僅限于圖中路徑的搜索。但其實(shí)A*算法不止適用于路徑搜索，它是一種啟發(fā)式的思想，它還可以用于其他問(wèn)題如八數(shù)碼問(wèn)題的求解，只是大多數(shù)問(wèn)題最后化簡(jiǎn)之后可以歸結(jié)為圖論（或者樹(shù)）的路徑求解，因此我們只需理解路徑搜索就能理解整個(gè)算法思想。

????????這一點(diǎn)正如BFS算法，BFS也不僅僅適用于路徑搜索，例如算法題目中常用的暴力窮舉，但我們學(xué)習(xí)該算法的時(shí)候也只關(guān)心路徑的搜索，因?yàn)楸┝ΩF舉最后實(shí)質(zhì)上也是一棵根節(jié)點(diǎn)開(kāi)始的搜索樹(shù)。

? ? ? ? ?同時(shí)為了方便理解，采用的都是網(wǎng)格圖，但是其實(shí)應(yīng)用在所有類型的圖結(jié)構(gòu)中都是一樣的、正確的。這不難理解，因?yàn)?strong>網(wǎng)格圖最終也可以化成節(jié)點(diǎn)+邊權(quán)為1的一般圖。

? ? ? ? BFS和Dijkstra算法我們?cè)偈煜げ贿^(guò)了，事實(shí)上不必多講。我們的重點(diǎn)是A*算法，這里具體展開(kāi)BFS和Dijkstra的算法過(guò)程原因是，一方面是希望大家清楚地知道A*算法是如何得來(lái)的；另一方面，是我個(gè)人太喜歡這個(gè)網(wǎng)站的代碼圖和交互動(dòng)畫(huà)了，真的是百看不厭。

1、BFS（Breadth First Search）

? ? ? ?BFS思想的關(guān)鍵就是不斷地?cái)U(kuò)展邊界（frontier）。

???????BFS的python代碼如下：

? ? ? ? 思路是：

????????先創(chuàng)建一個(gè)隊(duì)列(Queue，先進(jìn)先出：先放進(jìn)的節(jié)點(diǎn)先擴(kuò)展)frontier，frontier用來(lái)存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn)，因此初始時(shí)需要將起點(diǎn)start★放進(jìn)frontier；

? ? ? ? 再創(chuàng)建一個(gè)集合(Set，集合的元素?zé)o序且不會(huì)重復(fù))reached，reached用來(lái)存儲(chǔ)已經(jīng)到過(guò)的節(jié)點(diǎn)，就是我們常命名的visit。

? ? ? ? 只要frontier不為空，就從frontier中取出一個(gè)元素current進(jìn)行擴(kuò)展。對(duì)于的所有current鄰居 next，只要next不在reached里面（即沒(méi)有到達(dá)過(guò)），就把next放進(jìn)frontier里面，然后放到reached標(biāo)記為已經(jīng)到達(dá)。

? ? ? ? 上面的BFS代碼沒(méi)有構(gòu)建出一條路徑，僅僅告訴了我們?nèi)绾伪闅v圖上的所有點(diǎn)。因此需要進(jìn)行修改，記錄我們是怎么到達(dá)每一個(gè)點(diǎn)的路徑。

? ? ? ? 黃色部分是修改的部分：

? ? ? ? 這里用came_from替換了reached。

? ? ? ? came_from是字典(Dictionary，鍵值對(duì)，一個(gè)key對(duì)應(yīng)value)，came_from不僅可以表示和reached一樣的功能（判斷一個(gè)節(jié)點(diǎn)是否到達(dá)過(guò)），方法是判斷came_from里面是不是存在key為這個(gè)節(jié)點(diǎn)的鍵值對(duì)；還能記錄每個(gè)點(diǎn)的前序節(jié)點(diǎn)，用came_from[節(jié)點(diǎn)i]來(lái)記錄，這樣當(dāng)找到終點(diǎn)時(shí)就能順著前序節(jié)點(diǎn)一直尋找到起點(diǎn)。

? ? ? ? 還有一處修改部分是：之前是判斷是否在reached里面，不在的話直接放到reached集合里面；現(xiàn)在是判斷是否在came_from里面，不在的話存儲(chǔ)came_from[該節(jié)點(diǎn)的鄰居next]為當(dāng)前擴(kuò)展的current。

? ? ? ? ?當(dāng)每個(gè)節(jié)點(diǎn)都存儲(chǔ)了從哪里來(lái)的信息后，整張圖的情況就是下面這樣：

? ? ? ? ?上面的指示箭頭就告訴了前序節(jié)點(diǎn)是誰(shuí)，這樣當(dāng)我們BFS找到終點(diǎn)時(shí)，我們就有了足夠的信息知道我們是怎么到達(dá)終點(diǎn)的，也就能重建這一條路徑。方法如下：

? ? ? ? ?從goal開(kāi)始，順著came_from存儲(chǔ)的前序節(jié)點(diǎn)，一個(gè)一個(gè)地回溯到起點(diǎn)，期間不斷將路徑放到數(shù)組path里面，因?yàn)樵娇拷K點(diǎn)的節(jié)點(diǎn)越早放進(jìn)去，所以存儲(chǔ)的path最后存儲(chǔ)的是一條從終點(diǎn)到起點(diǎn)的反向路徑，最后要將整個(gè)path反過(guò)來(lái)。

? ? ? ? 上面的BFS最后會(huì)遍歷完圖里的所有節(jié)點(diǎn)，也就是會(huì)知道起點(diǎn)到所有節(jié)點(diǎn)的最短路徑（前提是圖上邊權(quán)都相等，否則不是最短）。但實(shí)際上我們一般只需要求到某一個(gè)目標(biāo)節(jié)點(diǎn)的路徑，因此很多過(guò)程是不必要的。原有的BFS一定是所有節(jié)點(diǎn)遍歷完才終止，而我們現(xiàn)在只需要遍歷到目標(biāo)節(jié)點(diǎn)后就可以停下了，故我們可以及時(shí)終止。

? ? ? ? 過(guò)程如下，一旦找到目標(biāo)節(jié)點(diǎn)，BFS就停止繼續(xù)擴(kuò)展：

? ? ? ? ?修改后的代碼如下，只需要加入一條及時(shí)終止的條件：

????????當(dāng)發(fā)現(xiàn)當(dāng)前正要擴(kuò)展的節(jié)點(diǎn)就是終點(diǎn)goal×時(shí)，代碼就結(jié)束了。

2、Dijkstra（Uniform Cost Search）

? ? ? ? 上面討論的BFS只能用于圖上每一條路徑的權(quán)重都相等的情況，如果圖中各條路徑權(quán)重不完全相同，那么再次采用BFS也能遍歷所有節(jié)點(diǎn)，但得不到最短路徑，因?yàn)樽钕缺闅v到的不一定就是最短的。

? ? ? ? Dijkstra算法也很簡(jiǎn)單，就是從起點(diǎn)開(kāi)始，不斷擴(kuò)展到當(dāng)前耗費(fèi)總代價(jià)最短的節(jié)點(diǎn)，直到到達(dá)終點(diǎn)（前提是邊權(quán)非負(fù)）。簡(jiǎn)單證明思路就是，目前選擇的耗費(fèi)最短的節(jié)點(diǎn)，之后再通過(guò)其他節(jié)點(diǎn)到達(dá)該節(jié)點(diǎn)的代價(jià)一定大于目前的代價(jià)。

? ? ? ? 因?yàn)樾枰獙ふ?strong>當(dāng)前耗費(fèi)總代價(jià)最短的節(jié)點(diǎn)，所以需要將原本的隊(duì)列（queue，先進(jìn)先出）修改為優(yōu)先隊(duì)列（priority queue，元素存在優(yōu)先級(jí)，可以返回最大優(yōu)先級(jí)的元素）。

? ? ? ? 同時(shí)除了記錄這個(gè)節(jié)點(diǎn)的前序節(jié)點(diǎn)came_from，還需要記錄當(dāng)前到達(dá)這個(gè)節(jié)點(diǎn)的代價(jià)cost_so_far。

? ? ? ? 在BFS代碼基礎(chǔ)上進(jìn)行修改：

? ? ? ? ?首先創(chuàng)建優(yōu)先隊(duì)列frontier，將起點(diǎn)放進(jìn)去，并且代價(jià)設(shè)置為0（python中的PriorityQueue的優(yōu)先級(jí)的值越小，則表明優(yōu)先級(jí)越高，越先被取出。但我印象中PriortyQueue的put([priority, value])的第一個(gè)參數(shù)是優(yōu)先級(jí)第二個(gè)參數(shù)才是值）。

? ? ? ? 接著創(chuàng)建came_from用來(lái)記錄從哪來(lái)的，創(chuàng)建cost_so_far用來(lái)記錄目前到達(dá)的各個(gè)節(jié)點(diǎn)所花費(fèi)的路徑總代價(jià)。

? ? ? ? 然后不斷地從frontier取出目前最小的代價(jià)的節(jié)點(diǎn)current進(jìn)行擴(kuò)展，直到最后到達(dá)goal結(jié)束。

? ? ? ? 擴(kuò)展的方法變?yōu)椋翰檎?span style="color:#4da8ee;">current的所有鄰接節(jié)點(diǎn)next，計(jì)算next的new_cost，計(jì)算方法是將current的當(dāng)前代價(jià)cost_so_far[current]加上這一條鄰邊的代價(jià)graph.cost(current,next)。如果next是沒(méi)有到達(dá)過(guò)的節(jié)點(diǎn)或者new_cost小于已知的最短路節(jié)點(diǎn)，那么添加或者修改當(dāng)前next的代價(jià)cost_so_far[next]，優(yōu)先級(jí)設(shè)置為新的代價(jià)new_cost，并且將這一鍵值對(duì)加入到擴(kuò)展的優(yōu)先隊(duì)列frontier里面，最后記錄next的前序節(jié)點(diǎn)是current。

? ? ? ? 值得一提的是，Dijkstra算法的執(zhí)行一般要求沒(méi)有負(fù)邊，但上面的Dijkstra實(shí)現(xiàn)代碼是可以處理含有正負(fù)邊的圖的，只是不能處理含有負(fù)環(huán)的圖。

????????原因在于，當(dāng)擴(kuò)展時(shí)發(fā)現(xiàn)一條更短的路時(shí)，會(huì)將其加入到優(yōu)先隊(duì)列。一般的Dijkstra算法所有節(jié)點(diǎn)只會(huì)進(jìn)入到優(yōu)先隊(duì)列一次，但上述代碼一旦發(fā)現(xiàn)通過(guò)其他節(jié)點(diǎn)到達(dá)的某個(gè)節(jié)點(diǎn)x路徑更短，就會(huì)將節(jié)點(diǎn)x放入到優(yōu)先隊(duì)列，而不管這個(gè)節(jié)點(diǎn)是否被擴(kuò)展過(guò)，也就是給了這個(gè)節(jié)點(diǎn)再次修改最短路的機(jī)會(huì)。所以如果圖有負(fù)邊沒(méi)負(fù)環(huán)（意味著所有節(jié)點(diǎn)都存在一條最短路），使用上面代碼也能找到最短路。

? ? ? ? 效果圖如下：

????????

? ? ? ? 上圖中走綠色■方格耗費(fèi)的代價(jià)大于棕色■，可以看到會(huì)先去探索一些棕色的格子然后再探索一些綠色的格子，即每次選擇當(dāng)前耗費(fèi)總路程最短的格子在擴(kuò)展。

3、啟發(fā)式（Heuristic search）

? ? ? ? 上面兩種方法都是往各個(gè)方向擴(kuò)展，當(dāng)我們的目標(biāo)是尋找到所有位置或者多個(gè)位置的路徑時(shí)這是合理的，但是如果我們僅僅是需要到一個(gè)位置的路徑，這樣的時(shí)間代價(jià)是不必要的。

? ? ? ? 我們的目的是讓邊界的擴(kuò)展方向朝著目標(biāo)位置擴(kuò)展，而不是朝其他方向盲目擴(kuò)展。為了實(shí)現(xiàn)上述目的，需要定義一個(gè)啟發(fā)式函數(shù)（heuristic?function），它將用來(lái)衡量我們目前的狀態(tài)離終點(diǎn)還有多遠(yuǎn)。

? ? ? ? 在網(wǎng)格圖中常用的是曼哈頓距離，定義方式如下：

? ? ? ? ?如果我們只用啟發(fā)式函數(shù)計(jì)算出的距離作為優(yōu)先級(jí)，即總是優(yōu)先擴(kuò)展離終點(diǎn)近的點(diǎn)，那么會(huì)得到如下結(jié)果：????????

? ? ? ? 可以看到在啟發(fā)式函數(shù)的幫助下，更快地尋找到了終點(diǎn)，而這正是它的優(yōu)勢(shì)：速度快。

????????這種搜索方法是貪婪最優(yōu)先搜索算法（Greedy Best First Search）

????????但是如果存在有障礙物的情況下，僅僅用啟發(fā)式函數(shù)的計(jì)算結(jié)果作為優(yōu)先級(jí)可能不能得到正確結(jié)果。如下所示：? ? ? ?

? ? ? ? ?可以看到，僅靠啟發(fā)式函數(shù)計(jì)算的優(yōu)先級(jí)并不能得出最短路徑，它舍棄了Dijstra算法每次擴(kuò)展最短路徑節(jié)點(diǎn)這一保證正確性的優(yōu)勢(shì)，也就不能保證得到一條最短路徑。

? ? ? ? 有沒(méi)有能同時(shí)兼顧速度和正確性的方法？那就是要下面要介紹的A*算法。

4、A*算法

4.1 算法細(xì)節(jié)

? ? ? ? Dijkstra算法可以很好的找到最短路徑，但是浪費(fèi)了不必要的時(shí)間去探索沒(méi)有希望的方向；僅僅使用啟發(fā)式的貪婪最優(yōu)先搜索算法（Greedy Best First Search）總是選擇最有希望的方向進(jìn)行探索，但它可能找不到最優(yōu)路徑。

? ? ? ? A*算法同時(shí)使用同時(shí)使用了上述兩種方法的信息：從起點(diǎn)到目前位置的實(shí)際距離和目前位置到終點(diǎn)的估計(jì)距離。

? ? ? ? A*算法通過(guò)如下公式來(lái)綜合考慮每個(gè)待擴(kuò)展節(jié)點(diǎn)的優(yōu)先級(jí)：

? ? ? ?

? ? ? ? 其中：

????????即待擴(kuò)展節(jié)點(diǎn)的綜合優(yōu)先級(jí)，他由和計(jì)算而來(lái)，我們?nèi)匀贿x擇待擴(kuò)展節(jié)點(diǎn)中最小的進(jìn)行擴(kuò)展。

????????是節(jié)點(diǎn)距離起點(diǎn)的代價(jià)。

????????是節(jié)點(diǎn)距離終點(diǎn)的估計(jì)代價(jià)。

? ? ? ? 從上面公式來(lái)看，整體上繼承了Dijkstra算法的思想，總是拓展最短的節(jié)點(diǎn)，這樣能保證一旦搜索到終點(diǎn)時(shí)必然是最短路徑；同時(shí)的計(jì)算上又考慮了離終點(diǎn)的預(yù)估距離，減少或避免擴(kuò)展個(gè)別沒(méi)有希望的節(jié)點(diǎn)，使得整體搜索過(guò)程趨向于有希望的方向。

? ? ? ? 應(yīng)注意的是，上述的選取不是任意的，它是保證最終結(jié)果正確與否、搜索速度快慢的關(guān)鍵。越大，那么搜索速度越快，但也不是無(wú)限大，它有自己的限制條件。如果設(shè)距離終點(diǎn)的真正代價(jià)為，那么必須滿足如下要求才能保證尋找到最優(yōu)解，即永遠(yuǎn)不能大于真正的距離。

?????????

? ? ? ? 可以直觀地認(rèn)為，是一種保守估計(jì)。

4.2 A與A*算法

????????要注意的一點(diǎn)是A算法和A*算法的區(qū)別。目前查找的資料沒(méi)有明確說(shuō)明，對(duì)于兩者的定義也有些模糊，以下是兩種A*算法的說(shuō)法：

? ? ? ? 第一種是認(rèn)為A*算法即上面的思想。即上述就是，對(duì)于所有都滿足如下公式的A算法就是A*算法。

????????

? ? ? ? 第二種是認(rèn)為在算法中對(duì)于往往存在了很多種估價(jià)函數(shù)，例如我們既可以采用曼哈頓距離，也可以采用對(duì)角距離，還可以采用歐幾里得距離，那么必然有多種估價(jià)函數(shù)、、等等。我們?nèi)绻麑?duì)A算法進(jìn)一步限制，即如果且（即大于等于任意的估價(jià)函數(shù)），那么該算法就是A*算法。可以看到，這種定義下A*是最優(yōu)的A算法。但實(shí)際應(yīng)用中，我們往往難以判斷或者尋找到最優(yōu)的估價(jià)函數(shù)，因此A*算法和A算法的區(qū)別并不是很重要，常常用A*算法表示這一種思想。

4.3 A*算法證明

? ? ? ? 對(duì)于上面A*算法的思想，我給出如下一種簡(jiǎn)單的反證思路，可能有所紕漏，但是希望可以幫助理解：

? ? ? ? 假設(shè)A*算法找出的路徑不是最短路徑，那么A*算法結(jié)束時(shí)說(shuō)明找到了一條更長(zhǎng)的從起點(diǎn)到終點(diǎn)的路徑。我們要證明矛盾，只需要證明A*算法在這一條更長(zhǎng)的路徑上不會(huì)順利地執(zhí)行下去即可。

? ? ? ? 設(shè)起點(diǎn)為，終點(diǎn)為。設(shè)最短路徑為，A*算法找的路徑為。這條路徑上與路徑上第1個(gè)不同的節(jié)點(diǎn)為,接下來(lái)依次是,,,…（這些節(jié)點(diǎn)中可能有些與路徑上的相同，但無(wú)所謂，此時(shí)已經(jīng)是一條不同的路徑）。設(shè)路徑上，節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為。同時(shí)令表示節(jié)點(diǎn)到終點(diǎn)的實(shí)際距離。如下所示：

????????假設(shè)當(dāng)A*算法運(yùn)行至?xí)r，不出意外的話就要擴(kuò)展，即此時(shí)節(jié)點(diǎn)的是所有待擴(kuò)展節(jié)點(diǎn)中最小的，所以會(huì)選擇。而我們要證明的恰恰就是這個(gè)“意外”，使得A*算法不會(huì)在之后選擇，也就不會(huì)在算法結(jié)束時(shí)選擇一條比最短路還長(zhǎng)的路。

? ? ? ? 我們知道（到本身的實(shí)際距離為0），而是t到t的估計(jì)距離，必然小于，即，所以此時(shí)也是0。因此:

? ? ? ? 而表示的是目前到的實(shí)際距離，也就是路徑的長(zhǎng)度。已知的路徑長(zhǎng)度大于路徑的長(zhǎng)度，而路徑的長(zhǎng)度可以表示為，所以：

????????

? ? ? ? 而是到的估計(jì)距離，一定小于等于到的實(shí)際距離，所以：

? ? ? ? 所以：

? ? ? ?

? ? ? ? 即：

????????

? ? ? ? 也就是：

????????

? ? ? ? 所以我們知道，此時(shí)待擴(kuò)展節(jié)點(diǎn)中，并不是最小值，我們有更小的節(jié)點(diǎn)來(lái)進(jìn)行擴(kuò)展。

? ? ? ? 當(dāng)擴(kuò)展之后，因?yàn)?img src="https://latex.csdn.net/eq?g%28b%29+h%5E%7B%27%7D%28b%29%20%5Cleq%20g%28t%29" alt="A*算法求解迷宮問(wèn)題（算法講解與證明、python實(shí)現(xiàn)與可視化）" referrerpolicy="no-referrer" />，同理可推出，所以接下來(lái)拓展的就是節(jié)點(diǎn)。我們可以類推最短路徑路徑上的余下的所有節(jié)點(diǎn),,…，不妨設(shè)為，它們都滿足：?，可以同理推出。

? ? ? ? 也就是節(jié)點(diǎn)的永遠(yuǎn)不會(huì)是待擴(kuò)展節(jié)點(diǎn)中最小的，直到最短路徑上的余下節(jié)點(diǎn)被擴(kuò)展完，節(jié)點(diǎn)都不會(huì)被擴(kuò)展。當(dāng)最短路徑?最后一個(gè)非節(jié)點(diǎn)被擴(kuò)展后，自然擴(kuò)展的就是t節(jié)點(diǎn)，此時(shí)算法結(jié)束。我們可以知道，結(jié)束時(shí)我們所找到的到的路徑正是而非，與我們假設(shè)的矛盾。

? ? ? ? 所以如果始終小于等于節(jié)點(diǎn)到終點(diǎn)的代價(jià)，則A*算法保證一定能夠找到最短路徑。當(dāng)?shù)闹翟叫?，算法將遍歷越多的節(jié)點(diǎn)，也就導(dǎo)致算法越慢。 如果很大，以至于完全等于節(jié)點(diǎn)到終點(diǎn)的真實(shí)代價(jià)，則A*算法將找到最佳路徑，并且速度很快?？上У氖牵⒎撬袌?chǎng)景下都能做到這一點(diǎn)。因?yàn)樵跊](méi)有達(dá)到終點(diǎn)之前，我們很難確切算出距離終點(diǎn)還有多遠(yuǎn)。

? ? ? ? 對(duì)于評(píng)價(jià)函數(shù)，我們可以發(fā)現(xiàn)以下有趣的事情：

? ? ? ? ①當(dāng)時(shí)，，說(shuō)明此時(shí)完全依據(jù)所到達(dá)節(jié)點(diǎn)中的最短距離，就是Dijkstra算法。

? ? ? ? ②當(dāng)時(shí)，就是貪婪最優(yōu)先搜索算法（Greedy Best First Search）

4.4 算法過(guò)程

? ? ? ? 以下是算法的偽代碼，相比前面所說(shuō)的Dijkstra算法過(guò)程只是加入了啟發(fā)式信息：

? ? ? ? 上面過(guò)程和Dijkstra過(guò)程較為相似，這里不再描述。

????????對(duì)于目前網(wǎng)上搜索的資料，與上述的過(guò)程基本相似，但是具體細(xì)節(jié)和叫法有所差別。一般說(shuō)的open_set就是上述代碼的frontier。close_set類似于放入到cost_so_far后的節(jié)點(diǎn)，但是區(qū)別在于上面?zhèn)未a是可以處理負(fù)邊無(wú)負(fù)環(huán)的圖，而一般的代碼不能處理。以下是另一種版本的算法過(guò)程：

1.初始化open_set和close_set；
2.將起點(diǎn)加入open_set中，并設(shè)置優(yōu)先級(jí)為0（優(yōu)先級(jí)越小表示優(yōu)先級(jí)越高）；
3.如果open_set不為空，則從open_set中選取優(yōu)先級(jí)最高的節(jié)點(diǎn)x：
    ①如果節(jié)點(diǎn)x為終點(diǎn)，則：
        從終點(diǎn)開(kāi)始逐步追蹤parent節(jié)點(diǎn)，一直到達(dá)起點(diǎn)，返回找到的結(jié)果路徑，算法結(jié)束；
    ②如果節(jié)點(diǎn)x不是終點(diǎn)，則：
        1.將節(jié)點(diǎn)x從open_set中刪除，并加入close_set中；
        2.遍歷節(jié)點(diǎn)x所有的鄰近節(jié)點(diǎn)：
            ①如果鄰近節(jié)點(diǎn)y在close_set中，則：
                跳過(guò)，選取下一個(gè)鄰近節(jié)點(diǎn)
            ②如果鄰近節(jié)點(diǎn)y不在open_set中，則：
                設(shè)置節(jié)點(diǎn)m的parent為節(jié)點(diǎn)x，計(jì)算節(jié)點(diǎn)m的優(yōu)先級(jí)，將節(jié)點(diǎn)m加入open_set中

? ? ? ? 在代碼實(shí)現(xiàn)時(shí)，我主要依據(jù)第一個(gè)偽代碼來(lái)實(shí)現(xiàn)。

三、具體實(shí)現(xiàn)

1、實(shí)驗(yàn)要求

????????迷宮問(wèn)題是實(shí)驗(yàn)心理學(xué)中一個(gè)古典問(wèn)題。迷宮從入口到出口可能有若干條通路，本實(shí)驗(yàn)要求求出從入口到出口的最短路徑。

????????下圖是一個(gè)4×4的迷宮問(wèn)題的示意圖，每個(gè)位置用平面坐標(biāo)系中的點(diǎn)表示，如圖所示，入口位置點(diǎn)的坐標(biāo)，出口位置點(diǎn)的坐標(biāo)為。兩個(gè)點(diǎn)之間有線相連則代表兩個(gè)位置相通。若沒(méi)有線相連，則表示不通。

2、代碼實(shí)現(xiàn)

? ? ? ? 為了解決上述迷宮問(wèn)題，我的思路是對(duì)上述矩形的迷宮的每個(gè)節(jié)點(diǎn)編號(hào)，從開(kāi)始依次從左到右是0，1，2，3……這樣編號(hào)還有一個(gè)好處是可以很方便的直到該節(jié)點(diǎn)位于第幾行第幾列。

? ? ? ? 每個(gè)節(jié)點(diǎn)的鄰接表記錄相鄰的節(jié)點(diǎn)，因?yàn)槭菬o(wú)向邊，所以一條邊會(huì)被記錄兩次。

? ? ? ? 具體算法過(guò)程根據(jù)上述偽代碼來(lái)編寫。

? ? ? ? 以下是實(shí)現(xiàn)代碼：

import numpy as np
from queue import PriorityQueue


class Map:  # 地圖
    def __init__(self, width, height) -> None:
        # 迷宮的尺寸
        self.width = width
        self.height = height
        # 創(chuàng)建size x size 的點(diǎn)的鄰接表
        self.neighbor = [[] for i in range(width*height)]

    # 添加邊
    def addEdge(self, from_: int, to_: int):
        if (from_ not in range(self.width*self.height)) or (to_ not in range(self.width*self.height)):
            return 0
        self.neighbor[from_].append(to_)
        self.neighbor[to_].append(from_)
        return 1

    # 由序號(hào)獲得該點(diǎn)在迷宮的x、y坐標(biāo)
    def get_x_y(self, num: int):
        if num not in range(self.width*self.height):
            return -1, -1
        x = num % self.width
        y = num // self.width
        return x, y


class Astar:  # A*尋路算法
    def __init__(self, _map: Map, start: int, end: int) -> None:
        # 地圖
        self.run_map = _map
        # 起點(diǎn)和終點(diǎn)
        self.start = start
        self.end = end
        # open集
        self.open_set = PriorityQueue()
        # cost_so_far表示到達(dá)某個(gè)節(jié)點(diǎn)的代價(jià)，也可相當(dāng)于close集使用
        self.cost_so_far = dict()
        # 每個(gè)節(jié)點(diǎn)的前序節(jié)點(diǎn)
        self.came_from = dict()

        # 將起點(diǎn)放入,優(yōu)先級(jí)設(shè)為0，無(wú)所謂設(shè)置多少，因?yàn)榭偸堑谝粋€(gè)被取出
        self.open_set.put((0, start))
        self.came_from[start] = -1
        self.cost_so_far[start] = 0

    # h函數(shù)計(jì)算,即啟發(fā)式信息
    def heuristic(self, a, b):
        x1, y1 = self.run_map.get_x_y(a)
        x2, y2 = self.run_map.get_x_y(b)
        return abs(x1-x2) + abs(y1-y2)

    # 運(yùn)行A*尋路算法，如果沒(méi)找到路徑返回0，找到返回1
    def find_way(self):
        # open表不為空
        while not self.open_set.empty():
            # 從優(yōu)先隊(duì)列中取出代價(jià)最短的節(jié)點(diǎn)作為當(dāng)前遍歷的節(jié)點(diǎn)，類型為(priority,node)
            current = self.open_set.get()
            # 找到終點(diǎn)
            if current[1] == self.end:
                break
            # 遍歷鄰接節(jié)點(diǎn)
            for next in self.run_map.neighbor[current[1]]:
                # 新的代價(jià)
                new_cost = self.cost_so_far[current[1]]+1
                # 沒(méi)有到達(dá)過(guò)的點(diǎn) 或 比原本已經(jīng)到達(dá)過(guò)的點(diǎn)的代價(jià)更小
                if (next not in self.cost_so_far) or (new_cost < self.cost_so_far[next]):
                    self.cost_so_far[next] = new_cost
                    priority = new_cost+self.heuristic(next, self.end)
                    self.open_set.put((priority, next))
                    self.came_from[next] = current[1]

        if self.end not in self.cost_so_far:
            return 0
        return 1

    def show_way(self):
        # 記錄路徑經(jīng)過(guò)的節(jié)點(diǎn)
        result = []
        current = self.end
        # 不斷尋找前序節(jié)點(diǎn)
        while self.came_from[current] != -1:
            result.append(current)
            current = self.came_from[current]
        # 加上起點(diǎn)
        result.append(current)
        # 翻轉(zhuǎn)路徑
        result.reverse()
        print(result)


# 初始化迷宮
theMap = Map(4, 4)
# 添加邊
theMap.addEdge(0, 1)
theMap.addEdge(1, 2)
theMap.addEdge(2, 6)
theMap.addEdge(3, 7)
theMap.addEdge(4, 5)
theMap.addEdge(5, 6)
theMap.addEdge(6, 7)
theMap.addEdge(4, 8)
theMap.addEdge(5, 9)
theMap.addEdge(7, 11)
theMap.addEdge(8, 9)
theMap.addEdge(9, 10)
theMap.addEdge(10, 11)
theMap.addEdge(8, 12)
theMap.addEdge(10, 14)
theMap.addEdge(12, 13)
theMap.addEdge(13, 14)
theMap.addEdge(14, 15)
# A* 算法尋路
theAstar = Astar(theMap, 0, 15)
theAstar.find_way()
theAstar.show_way()

? ? ? ? 運(yùn)行之后得到如下結(jié)果：

[0, 1, 2, 6, 7, 11, 10, 14, 15]

? ? ? ? 也就是在圖上的路徑為：

? ? ? ? ?上述是代碼的主體，為了更好地實(shí)現(xiàn)結(jié)果的可視化，我使用python的matploblib庫(kù)來(lái)可視化。

? ? ? ? ?matploblib庫(kù)一般用來(lái)可視化數(shù)據(jù)圖表，我的思路是采用其畫(huà)圓函數(shù)Circle來(lái)繪制節(jié)點(diǎn)，畫(huà)矩形函數(shù)Rectangle來(lái)繪制邊，然后使用plt（matplotlib.pyplot）的ion()函數(shù)打開(kāi)交互，繪制動(dòng)態(tài)圖，呈現(xiàn)查找中的每一個(gè)階段。具體細(xì)節(jié)如下：

import numpy as np
from queue import PriorityQueue
import matplotlib.pyplot as plt
import matplotlib.patches as mpathes
import random

# 畫(huà)布
fig, ax = plt.subplots()


class Map:  # 地圖
    def __init__(self, width, height) -> None:
        # 迷宮的尺寸
        self.width = width
        self.height = height
        # 創(chuàng)建size x size 的點(diǎn)的鄰接表
        self.neighbor = [[] for i in range(width*height)]

    def addEdge(self, from_: int, to_: int):    # 添加邊
        if (from_ not in range(self.width*self.height)) or (to_ not in range(self.width*self.height)):
            return 0
        self.neighbor[from_].append(to_)
        self.neighbor[to_].append(from_)
        return 1

    def get_x_y(self, num: int):    # 由序號(hào)獲得該點(diǎn)在迷宮的x、y坐標(biāo)
        if num not in range(self.width*self.height):
            return -1, -1
        x = num % self.width
        y = num // self.width
        return x, y

    def drawCircle(self, num, color):    # 繪制圓形
        x, y = self.get_x_y(num)
        thePoint = mpathes.Circle(np.array([x+1, y+1]), 0.1, color=color)
        # 聲明全局變量
        global ax
        ax.add_patch(thePoint)

    def drawEdge(self, from_, to_, color):    # 繪制邊
        # 轉(zhuǎn)化為(x,y)
        x1, y1 = self.get_x_y(from_)
        x2, y2 = self.get_x_y(to_)
        # 整體向右下方移動(dòng)一個(gè)單位
        x1, y1 = x1+1, y1+1
        x2, y2 = x2+1, y2+1
        # 繪長(zhǎng)方形代表邊
        offset = 0.05
        global ax
        if from_-to_ == 1:  # ← 方向的邊
            rect = mpathes.Rectangle(
                np.array([x2-offset, y2-offset]), 1+2*offset, 2*offset, color=color)
            ax.add_patch(rect)
        elif from_-to_ == -1:  # → 方向的邊
            rect = mpathes.Rectangle(
                np.array([x1-offset, y1-offset]), 1+2*offset, 2*offset, color=color)
            ax.add_patch(rect)
        elif from_-to_ == self.width:  # ↑ 方向的邊
            rect = mpathes.Rectangle(
                np.array([x2-offset, y2-offset]), 2*offset, 1+2*offset, color=color)
            ax.add_patch(rect)
        else:  # ↓ 方向的邊
            rect = mpathes.Rectangle(
                np.array([x1-offset, y1-offset]), 2*offset, 1+2*offset, color=color)
            ax.add_patch(rect)

    def initMap(self):    # 繪制初始的迷宮
        # 先繪制邊
        for i in range(self.width*self.height):
            for next in self.neighbor[i]:
                self.drawEdge(i, next, '#afeeee')

        # 再繪制點(diǎn)
        for i in range(self.width*self.height):
            self.drawCircle(i, '#87cefa')


class Astar:  # A*尋路算法
    def __init__(self, _map: Map, start: int, end: int) -> None:
        # 地圖
        self.run_map = _map
        # 起點(diǎn)和終點(diǎn)
        self.start = start
        self.end = end
        # open集
        self.open_set = PriorityQueue()
        # cost_so_far表示到達(dá)某個(gè)節(jié)點(diǎn)的代價(jià)，也可相當(dāng)于close集使用
        self.cost_so_far = dict()
        # 每個(gè)節(jié)點(diǎn)的前序節(jié)點(diǎn)
        self.came_from = dict()

        # 將起點(diǎn)放入,優(yōu)先級(jí)設(shè)為0，無(wú)所謂設(shè)置多少，因?yàn)榭偸堑谝粋€(gè)被取出
        self.open_set.put((0, start))
        self.came_from[start] = -1
        self.cost_so_far[start] = 0

        # 標(biāo)識(shí)起點(diǎn)和終點(diǎn)
        self.run_map.drawCircle(start, '#ff8099')
        self.run_map.drawCircle(end, '#ff4d40')

    def heuristic(self, a, b):    # h函數(shù)計(jì)算,即啟發(fā)式信息
        x1, y1 = self.run_map.get_x_y(a)
        x2, y2 = self.run_map.get_x_y(b)
        return abs(x1-x2) + abs(y1-y2)

    def find_way(self):    # 運(yùn)行A*尋路算法，如果沒(méi)找到路徑返回0，找到返回1
        while not self.open_set.empty():  # open表不為空
            # 從優(yōu)先隊(duì)列中取出代價(jià)最短的節(jié)點(diǎn)作為當(dāng)前遍歷的節(jié)點(diǎn)，類型為(priority,node)
            current = self.open_set.get()

            # 展示A*算法的執(zhí)行過(guò)程
            if current[1] != self.start:
                # 當(dāng)前節(jié)點(diǎn)的前序
                pre = self.came_from[current[1]]
                # 可視化
                self.run_map.drawEdge(pre, current[1], '#fffdd0')
                if pre != self.start:
                    self.run_map.drawCircle(pre, '#99ff4d')
                else:  # 起點(diǎn)不改色
                    self.run_map.drawCircle(pre, '#ff8099')
                if current[1] != self.end:
                    self.run_map.drawCircle(current[1], '#99ff4d')
                else:
                    self.run_map.drawCircle(current[1], '#ff4d40')
                # 顯示當(dāng)前狀態(tài)
                plt.show()
                plt.pause(0.5)

            # 找到終點(diǎn)
            if current[1] == self.end:
                break
            # 遍歷鄰接節(jié)點(diǎn)
            for next in self.run_map.neighbor[current[1]]:
                # 新的代價(jià)
                new_cost = self.cost_so_far[current[1]]+1
                # 沒(méi)有到達(dá)過(guò)的點(diǎn) 或 比原本已經(jīng)到達(dá)過(guò)的點(diǎn)的代價(jià)更小
                if (next not in self.cost_so_far) or (new_cost < self.cost_so_far[next]):
                    self.cost_so_far[next] = new_cost
                    priority = new_cost+self.heuristic(next, self.end)
                    self.open_set.put((priority, next))
                    self.came_from[next] = current[1]

    def show_way(self):  # 顯示最短路徑
        # 記錄路徑經(jīng)過(guò)的節(jié)點(diǎn)
        result = []
        current = self.end

        if current not in self.cost_so_far:
            return

        # 不斷尋找前序節(jié)點(diǎn)
        while self.came_from[current] != -1:
            result.append(current)
            current = self.came_from[current]
        # 加上起點(diǎn)
        result.append(current)
        # 翻轉(zhuǎn)路徑
        result.reverse()
        # 生成路徑
        for point in result:
            if point != self.start:  # 不是起點(diǎn)
                # 當(dāng)前節(jié)點(diǎn)的前序
                pre = self.came_from[point]
                # 可視化
                self.run_map.drawEdge(pre, point, '#ff2f76')
                if pre == self.start:  # 起點(diǎn)顏色
                    self.run_map.drawCircle(pre, '#ff8099')
                elif point == self.end:  # 終點(diǎn)顏色
                    self.run_map.drawCircle(point, '#ff4d40')
                # 顯示當(dāng)前狀態(tài)
                plt.show()
                plt.pause(0.1)

    def get_cost(self):  # 返回最短路徑
        if self.end not in self.cost_so_far:
            return -1
        return self.cost_so_far[self.end]


# 初始化迷宮
theMap = Map(4, 4)

# 設(shè)置迷宮顯示的一些參數(shù)
plt.xlim(0, theMap.width+1)
plt.ylim(0, theMap.height+1)
# 將x軸的位置設(shè)置在頂部
ax.xaxis.set_ticks_position('top')
# y軸反向
ax.invert_yaxis()
# 等距
plt.axis('equal')
# 不顯示背景的網(wǎng)格線
plt.grid(False)
# 允許動(dòng)態(tài)
plt.ion()
# 添加邊
theMap.addEdge(0, 1)
theMap.addEdge(1, 2)
theMap.addEdge(2, 6)
theMap.addEdge(3, 7)
theMap.addEdge(4, 5)
theMap.addEdge(5, 6)
theMap.addEdge(6, 7)
theMap.addEdge(4, 8)
theMap.addEdge(5, 9)
theMap.addEdge(7, 11)
theMap.addEdge(8, 9)
theMap.addEdge(9, 10)
theMap.addEdge(10, 11)
theMap.addEdge(8, 12)
theMap.addEdge(10, 14)
theMap.addEdge(12, 13)
theMap.addEdge(13, 14)
theMap.addEdge(14, 15)

# 初始化迷宮
theMap.initMap()

# A* 算法尋路
theAstar = Astar(theMap, 0, 15)
theAstar.find_way()
theAstar.show_way()

# 輸出最短路徑長(zhǎng)度
theCost = theAstar.get_cost()
if theCost == -1:
    print("不存在該路徑！")
else:
    print("從起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度為: ", theCost)

# 關(guān)閉交互，展示結(jié)果
plt.ioff()
plt.show()

? ? ? ? 運(yùn)行效果如下：

? ? ? ? ?輸出結(jié)果如下：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-403153.html

從起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度為:  8

? ? ? ? ?對(duì)于稍微大一點(diǎn)的圖(6x6)進(jìn)行測(cè)試：

# 初始化迷宮
theMap = Map(6, 6)

# 設(shè)置迷宮顯示的一些參數(shù)
plt.xlim(0, theMap.width+1)
plt.ylim(0, theMap.height+1)
# 將x軸的位置設(shè)置在頂部
ax.xaxis.set_ticks_position('top')
# y軸反向
ax.invert_yaxis()
# 等距
plt.axis('equal')
# 不顯示背景的網(wǎng)格線
plt.grid(False)
# 允許動(dòng)態(tài)
plt.ion()

# 添加邊
theMap.addEdge(0, 1)
theMap.addEdge(1, 2)
theMap.addEdge(2, 3)
theMap.addEdge(3, 4)
theMap.addEdge(4, 5)
theMap.addEdge(1, 7)
theMap.addEdge(3, 9)
theMap.addEdge(4, 10)
theMap.addEdge(5, 11)
theMap.addEdge(6, 7)
theMap.addEdge(8, 9)
theMap.addEdge(6, 12)
theMap.addEdge(7, 13)
theMap.addEdge(8, 14)
theMap.addEdge(10, 16)
theMap.addEdge(11, 17)
theMap.addEdge(12, 13)
theMap.addEdge(13, 14)
theMap.addEdge(15, 16)
theMap.addEdge(16, 17)
theMap.addEdge(14, 20)
theMap.addEdge(15, 21)
theMap.addEdge(16, 22)
theMap.addEdge(17, 23)
theMap.addEdge(18, 19)
theMap.addEdge(19, 20)
theMap.addEdge(20, 21)
theMap.addEdge(22, 23)
theMap.addEdge(18, 24)
theMap.addEdge(19, 25)
theMap.addEdge(20, 26)
theMap.addEdge(22, 28)
theMap.addEdge(26, 27)
theMap.addEdge(27, 28)
theMap.addEdge(24, 30)
theMap.addEdge(27, 33)
theMap.addEdge(29, 35)
theMap.addEdge(30, 31)
theMap.addEdge(31, 32)
theMap.addEdge(33, 34)
theMap.addEdge(34, 35)

# 初始化迷宮
theMap.initMap()

# A* 算法尋路
theAstar = Astar(theMap, 0, 35)
theAstar.find_way()
theAstar.show_way()

# 輸出最短路徑長(zhǎng)度
theCost = theAstar.get_cost()
if theCost == -1:
    print("不存在該路徑！")
else:
    print("從起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度為: ", theCost)

# 關(guān)閉交互，展示結(jié)果
plt.ioff()
plt.show()

? ? ? ? 運(yùn)行結(jié)果：

????????

? ? ? ? ?輸出結(jié)果：

從起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度為:  10

????????可以知道，運(yùn)行結(jié)果正確。

? ? ? ? 但我們發(fā)現(xiàn)，每一次輸入一個(gè)新的圖都得輸入一大堆邊，對(duì)于復(fù)雜一點(diǎn)的圖很不方便調(diào)試。有沒(méi)有一種方法，能在我們?cè)O(shè)置迷宮的大小后讓程序自己隨機(jī)生成迷宮？

? ? ? ? 為此，我們可以編寫一個(gè)隨機(jī)生成迷宮的函數(shù)。

? ? ? ? 我采用的隨機(jī)生成方法是簡(jiǎn)單的深度搜索法。初始狀態(tài)下的迷宮沒(méi)有邊，只有指定大小的節(jié)點(diǎn)陣列。從起點(diǎn)開(kāi)始，依次探索四個(gè)方向（四個(gè)方向的探索順序隨機(jī)），如果該方向的鄰接點(diǎn)沒(méi)有被探索過(guò)，那么生成一條邊，同時(shí)前進(jìn)到該點(diǎn)。對(duì)于該點(diǎn)繼續(xù)重復(fù)上面過(guò)程，直到所有點(diǎn)被探索完，算法終止。

    # 尋找
    def search(self, current: int):
        # 四個(gè)方向的順序
        sequence = [i for i in range(4)]
        # 打亂順序
        random.shuffle(sequence)
        # 依次選擇四個(gè)方向
        for i in sequence:
            # 要探索的位置
            x = self.direction[i]+current

            # 跨了一行
            if (current % self.width == self.width-1 and self.direction[i] == 1) or (current % self.width == 0 and self.direction[i] == -1):
                continue

            # 要探索的位置沒(méi)有超出范圍 且 該位置沒(méi)有被探索過(guò)
            if 0 <= x < self.width*self.height and self.visited[x] == 0:
                self.addEdge(current, x)
                self.visited[x] = 1
                self.search(x)


    def randomCreateMap(self, start, k):  # 隨機(jī)生成迷宮
        # 標(biāo)識(shí)每個(gè)節(jié)點(diǎn)是否被探索過(guò)
        self.visited = np.zeros(self.width*self.height)
        self.visited[start] = 1
        # 四個(gè)方向,分別代表上、下、左、右
        self.direction = {0: -self.width,
                          1: self.width,
                          2: -1,
                          3: 1}
        # 從起點(diǎn)開(kāi)始
        self.search(start)

? ? ? ? 以下是隨機(jī)生成的10x10、20x20、30x25迷宮：

?????????

? ? ? ? ?可以看到生成的迷宮效果不錯(cuò)，可以滿足基本需要。但因?yàn)樯擅詫m的算法使用的是深度搜索，所以導(dǎo)致起點(diǎn)到終點(diǎn)的路徑有且僅有一條。這對(duì)于我們尋找最短路徑而言，似乎無(wú)法說(shuō)明，因?yàn)橐坏┱业搅私K點(diǎn)那必定是最短路。因此我們對(duì)迷宮增加復(fù)雜度，也就是隨機(jī)在迷宮里面添加k條邊，使得圖存在多條路徑。

    # 隨機(jī)添加k條邊
    def randomAddEdges(self, k):
        # 循環(huán)k次(可能不止k次)
        for i in range(k):
            node = random.randint(0, self.width*self.height)
            # 隨機(jī)添加一個(gè)方向
            sequence = [i for i in range(4)]
            random.shuffle(sequence)
            isPick = 0
            for d in sequence:
                # 跨了一行,不存在該方向的邊
                if (node % self.width == self.width-1 and self.direction[d] == 1) or (node % self.width == 0 and self.direction[d] == -1):
                    continue
                x = self.direction[d]+node
                # 該邊存在
                if x in self.neighbor[node]:
                    continue
                # 該邊不存在
                self.addEdge(node, x)
                isPick = 1
            # 重新添加一條邊,即重新循環(huán)一次
            if isPick == 0:
                if i == 0:  # 第一次
                    i = 0
                else:
                    i -= 1

? ? ? ? 生成后的迷宮如下：

? ? ? ? 可以看到多了很多冗余路徑，使得起點(diǎn)到終點(diǎn)的路徑不止一條。

? ? ? ? 將A*算法應(yīng)用于隨機(jī)生成的迷宮：

????????

? ? ? ? ?輸出結(jié)果如下：

從起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度為:  18

????????

????????輸出結(jié)果如下：

從起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度為:  28

????????

? ? ? ? ?輸出結(jié)果如下：

從起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度為:  50

四、源代碼

import numpy as np
from queue import PriorityQueue
import matplotlib.pyplot as plt
import matplotlib.patches as mpathes
import random

# 畫(huà)布
fig, ax = plt.subplots()


class Map:  # 地圖
    def __init__(self, width, height) -> None:
        # 迷宮的尺寸
        self.width = width
        self.height = height
        # 創(chuàng)建size x size 的點(diǎn)的鄰接表
        self.neighbor = [[] for i in range(width*height)]

    def addEdge(self, from_: int, to_: int):    # 添加邊
        if (from_ not in range(self.width*self.height)) or (to_ not in range(self.width*self.height)):
            return 0
        self.neighbor[from_].append(to_)
        self.neighbor[to_].append(from_)
        return 1

    def get_x_y(self, num: int):    # 由序號(hào)獲得該點(diǎn)在迷宮的x、y坐標(biāo)
        if num not in range(self.width*self.height):
            return -1, -1
        x = num % self.width
        y = num // self.width
        return x, y

    def drawCircle(self, num, color):    # 繪制圓形
        x, y = self.get_x_y(num)
        thePoint = mpathes.Circle(np.array([x+1, y+1]), 0.1, color=color)
        # 聲明全局變量
        global ax
        ax.add_patch(thePoint)

    def drawEdge(self, from_, to_, color):    # 繪制邊
        # 轉(zhuǎn)化為(x,y)
        x1, y1 = self.get_x_y(from_)
        x2, y2 = self.get_x_y(to_)
        # 整體向右下方移動(dòng)一個(gè)單位
        x1, y1 = x1+1, y1+1
        x2, y2 = x2+1, y2+1
        # 繪長(zhǎng)方形代表邊
        offset = 0.05
        global ax
        if from_-to_ == 1:  # ← 方向的邊
            rect = mpathes.Rectangle(
                np.array([x2-offset, y2-offset]), 1+2*offset, 2*offset, color=color)
            ax.add_patch(rect)
        elif from_-to_ == -1:  # → 方向的邊
            rect = mpathes.Rectangle(
                np.array([x1-offset, y1-offset]), 1+2*offset, 2*offset, color=color)
            ax.add_patch(rect)
        elif from_-to_ == self.width:  # ↑ 方向的邊
            rect = mpathes.Rectangle(
                np.array([x2-offset, y2-offset]), 2*offset, 1+2*offset, color=color)
            ax.add_patch(rect)
        else:  # ↓ 方向的邊
            rect = mpathes.Rectangle(
                np.array([x1-offset, y1-offset]), 2*offset, 1+2*offset, color=color)
            ax.add_patch(rect)

    def initMap(self):    # 繪制初始的迷宮
        # 先繪制邊
        for i in range(self.width*self.height):
            for next in self.neighbor[i]:
                self.drawEdge(i, next, '#afeeee')

        # 再繪制點(diǎn)
        for i in range(self.width*self.height):
            self.drawCircle(i, '#87cefa')

    # 尋找
    def search(self, current: int):
        # 四個(gè)方向的順序
        sequence = [i for i in range(4)]
        # 打亂順序
        random.shuffle(sequence)
        # 依次選擇四個(gè)方向
        for i in sequence:
            # 要探索的位置
            x = self.direction[i]+current

            # 跨了一行
            if (current % self.width == self.width-1 and self.direction[i] == 1) or (current % self.width == 0 and self.direction[i] == -1):
                continue

            # 要探索的位置沒(méi)有超出范圍 且 該位置沒(méi)有被探索過(guò)
            if 0 <= x < self.width*self.height and self.visited[x] == 0:
                self.addEdge(current, x)
                self.visited[x] = 1
                self.search(x)

    # 隨機(jī)添加k條邊
    def randomAddEdges(self, k):
        # 循環(huán)k次(可能不止k次)
        for i in range(k):
            node = random.randint(0, self.width*self.height)
            # 隨機(jī)添加一個(gè)方向
            sequence = [i for i in range(4)]
            random.shuffle(sequence)
            isPick = 0
            for d in sequence:
                # 跨了一行,不存在該方向的邊
                if (node % self.width == self.width-1 and self.direction[d] == 1) or (node % self.width == 0 and self.direction[d] == -1):
                    continue
                x = self.direction[d]+node
                # 該邊存在
                if x in self.neighbor[node]:
                    continue
                # 該邊不存在
                self.addEdge(node, x)
                isPick = 1
            # 重新添加一條邊,即重新循環(huán)一次
            if isPick == 0:
                if i == 0:  # 第一次
                    i = 0
                else:
                    i -= 1

    def randomCreateMap(self, start, k):  # 隨機(jī)生成迷宮
        # 標(biāo)識(shí)每個(gè)節(jié)點(diǎn)是否被探索過(guò)
        self.visited = np.zeros(self.width*self.height)
        self.visited[start] = 1
        # 四個(gè)方向,分別代表上、下、左、右
        self.direction = {0: -self.width,
                          1: self.width,
                          2: -1,
                          3: 1}
        # 從起點(diǎn)開(kāi)始
        self.search(start)
        # 隨機(jī)添加k條邊，使得迷宮盡可能出現(xiàn)多條到達(dá)終點(diǎn)的路徑
        self.randomAddEdges(k)


class Astar:  # A*尋路算法
    def __init__(self, _map: Map, start: int, end: int) -> None:
        # 地圖
        self.run_map = _map
        # 起點(diǎn)和終點(diǎn)
        self.start = start
        self.end = end
        # open集
        self.open_set = PriorityQueue()
        # cost_so_far表示到達(dá)某個(gè)節(jié)點(diǎn)的代價(jià)，也可相當(dāng)于close集使用
        self.cost_so_far = dict()
        # 每個(gè)節(jié)點(diǎn)的前序節(jié)點(diǎn)
        self.came_from = dict()

        # 將起點(diǎn)放入,優(yōu)先級(jí)設(shè)為0，無(wú)所謂設(shè)置多少，因?yàn)榭偸堑谝粋€(gè)被取出
        self.open_set.put((0, start))
        self.came_from[start] = -1
        self.cost_so_far[start] = 0

        # 標(biāo)識(shí)起點(diǎn)和終點(diǎn)
        self.run_map.drawCircle(start, '#ff8099')
        self.run_map.drawCircle(end, '#ff4d40')

    def heuristic(self, a, b):    # h函數(shù)計(jì)算,即啟發(fā)式信息
        x1, y1 = self.run_map.get_x_y(a)
        x2, y2 = self.run_map.get_x_y(b)
        return abs(x1-x2) + abs(y1-y2)

    def find_way(self):    # 運(yùn)行A*尋路算法，如果沒(méi)找到路徑返回0，找到返回1
        while not self.open_set.empty():  # open表不為空
            # 從優(yōu)先隊(duì)列中取出代價(jià)最短的節(jié)點(diǎn)作為當(dāng)前遍歷的節(jié)點(diǎn)，類型為(priority,node)
            current = self.open_set.get()

            # 展示A*算法的執(zhí)行過(guò)程
            if current[1] != self.start:
                # 當(dāng)前節(jié)點(diǎn)的前序
                pre = self.came_from[current[1]]
                # 可視化
                self.run_map.drawEdge(pre, current[1], '#fffdd0')
                if pre != self.start:
                    self.run_map.drawCircle(pre, '#99ff4d')
                else:  # 起點(diǎn)不改色
                    self.run_map.drawCircle(pre, '#ff8099')
                if current[1] != self.end:
                    self.run_map.drawCircle(current[1], '#99ff4d')
                else:
                    self.run_map.drawCircle(current[1], '#ff4d40')
                # 顯示當(dāng)前狀態(tài)
                plt.show()
                plt.pause(0.01)

            # 找到終點(diǎn)
            if current[1] == self.end:
                break
            # 遍歷鄰接節(jié)點(diǎn)
            for next in self.run_map.neighbor[current[1]]:
                # 新的代價(jià)
                new_cost = self.cost_so_far[current[1]]+1
                # 沒(méi)有到達(dá)過(guò)的點(diǎn) 或 比原本已經(jīng)到達(dá)過(guò)的點(diǎn)的代價(jià)更小
                if (next not in self.cost_so_far) or (new_cost < self.cost_so_far[next]):
                    self.cost_so_far[next] = new_cost
                    priority = new_cost+self.heuristic(next, self.end)
                    self.open_set.put((priority, next))
                    self.came_from[next] = current[1]

    def show_way(self):  # 顯示最短路徑
        # 記錄路徑經(jīng)過(guò)的節(jié)點(diǎn)
        result = []
        current = self.end

        if current not in self.cost_so_far:
            return

        # 不斷尋找前序節(jié)點(diǎn)
        while self.came_from[current] != -1:
            result.append(current)
            current = self.came_from[current]
        # 加上起點(diǎn)
        result.append(current)
        # 翻轉(zhuǎn)路徑
        result.reverse()
        # 生成路徑
        for point in result:
            if point != self.start:  # 不是起點(diǎn)
                # 當(dāng)前節(jié)點(diǎn)的前序
                pre = self.came_from[point]
                # 可視化
                self.run_map.drawEdge(pre, point, '#ff2f76')
                if pre == self.start:  # 起點(diǎn)顏色
                    self.run_map.drawCircle(pre, '#ff8099')
                elif point == self.end:  # 終點(diǎn)顏色
                    self.run_map.drawCircle(point, '#ff4d40')
                # 顯示當(dāng)前狀態(tài)
                plt.show()
                plt.pause(0.005)

    def get_cost(self):  # 返回最短路徑
        if self.end not in self.cost_so_far:
            return -1
        return self.cost_so_far[self.end]


# 初始化迷宮，設(shè)置寬度和高度
theMap = Map(20, 20)

# 設(shè)置迷宮顯示的一些參數(shù)
plt.xlim(0, theMap.width+1)
plt.ylim(0, theMap.height+1)
# 將x軸的位置設(shè)置在頂部
ax.xaxis.set_ticks_position('top')
# y軸反向
ax.invert_yaxis()
# 等距
plt.axis('equal')
# 不顯示背景的網(wǎng)格線
plt.grid(False)
# 允許動(dòng)態(tài)
plt.ion()

# 隨機(jī)添加邊，生成迷宮，第一個(gè)參數(shù)為起點(diǎn)；第二個(gè)參數(shù)為額外隨機(jī)生成的邊，可以表示為圖的復(fù)雜程度
theMap.randomCreateMap(0, 20)

# 初始化迷宮
theMap.initMap()

# A* 算法尋路
theAstar = Astar(theMap, 0, 399)  # 設(shè)置起點(diǎn)和終點(diǎn)
theAstar.find_way()  # 尋路
theAstar.show_way()  # 顯示最短路徑

# 輸出最短路徑長(zhǎng)度
theCost = theAstar.get_cost()
if theCost == -1:
    print("不存在該路徑！")
else:
    print("從起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度為: ", theCost)

# 關(guān)閉交互，展示結(jié)果
plt.ioff()
plt.show()

到了這里，關(guān)于A*算法求解迷宮問(wèn)題（算法講解與證明、python實(shí)現(xiàn)與可視化）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！