A*算法被廣泛應用于遊戲中的自動尋路功能，說明它作為一個路徑規劃的算法，确實有着很大的優勢。以遊戲舉例來看，比如在遊戲中我們想要找到從一個位置到另一個位置的路徑，我們不僅嘗試着找到最短距離的路徑；我們還想要顧忌到消耗的時間。在一張地圖上，穿過一片池塘速度會明顯減慢，是以我們想要找到一條可以繞過水路的路徑。
首先我們來回顧一下廣度優先搜尋和深度優先搜尋算法。我們從前兩篇文章中可以得知，廣度優先搜尋算法中使用資料結構是隊列，而深度優先搜尋算法中适用的資料結構是棧。對于一個隊列，節點總是先進先出（FIFO），是以對于隊列中的第一個節點來說，它的所有直接子節點在隊列中都是緊緊跟随在該節點之後，這樣程式在運作的時候，對于第一個入隊列的節點，就會先周遊完他所有的直接子節點，接着才會去周遊他的每個直接子節點的直接子節點。可以看出周遊的順序就是一個類似金字塔的形狀：第一行有一個頭結點，第二行是該頭結點的直接子節點，而第三行是直接子節點的直接子節點…每周遊一行都會找出這一行的所有子節點，是以這種算法被稱為“廣度優先搜尋”。
廣度優先搜尋的節點周遊順序
而相對地，深度優先搜尋就很好了解。對于任何一個節點，都會先去周遊它的第一個子節點的第一個子節點的第一個子節點…後進先出（LIFO）的棧則正好保證了這一點。這種“一條路走到黑”的方式，在它周遊的第一條路徑就可能會找到解，但是由于不是橫向周遊，路徑的長度并不一定是最短，即程式不一定會給出最優解。
深度優先搜尋的節點周遊順序
這兩種算法的優缺點都很明顯，于是我們需要想出一種能結合兩種算法優點的算法。我們可以做出如下處理：對于廣度優先搜尋算法的隊列，如果我們可以想出一種方法，對隊列進行排序，把前文中類似“穿過一片沼澤”這樣的節點盡量放在最後去周遊，那麼我們就可以在相對短的時間内找出一個最優解來。在A*算法中，我們對節點按以下的方式進行排序：
其中，F是我們計算出的權值，F值越大，代表這個節點的收益越小，也就越接近于我們上文提到的“沼澤地”。
G指的是我們從初始節點到達現在的節點的過程中付出的代價。例如我們的機器人每走一格或每清理一個灰塵會耗費1個機關時間，那麼機器人做了5個動作之後，我們的G值就是5。
H值是一個相對開放的概念，它指的是從目前狀态到目标狀态預計要付出的代價。這個值由算法工程師來進行估算，H值被估算的越準确，算法所需要周遊的節點就越少。以我們的掃地機器人舉例，假如目前房間内隻剩下一個灰塵，而這個灰塵就在機器人的東側（右側），那麼機器人通過這種算法就可以直接選擇先往東走去清理這個灰塵，而不是向其他方向走，避免了“南轅北轍”這種人工智障???的情況出現。
計算出這個值之後，我們就按這個F值在隊列中進行排序。本例中源碼由Java編寫，在Java中有一種資料結構，PriorityQueue，即優先級隊列，這種資料結構正好可以用來存放要周遊的節點。
首先是Point類，用于表示坐标系中的點。這個檔案與前兩個算法中相同。代碼如下：
接下來是State類。如果把問題的情景（房間、機器人）比作一個系統，那麼State類就表示某一時刻系統的狀态，也就是我們要周遊的節點。注意這個類裡比之前的兩個算法多了兩個屬性，F值和G值。G值就是機器人從其實狀态到目前狀态所進行的操作次數。F值是G值和H值的和。而H值，在這裡并沒有列出來，因為我把它視為目前狀态下仍未被清理的灰塵數量，也就是灰塵清單的size，通過目前狀态的dirtList取size()即可得到，便不再單獨設該屬性。
最後是算法的實作類，Robot類。該類使用了一個新的資料結構：PriorityQueue來作為存儲節點的open list。PriorityQueue需要我們自定義一個比較器（Comparator）用于在插入元素時将該元素與清單中的元素進行比較，并插入适當的位置，保證PriorityQueue在任何時刻都是有序的。需要注意的一點是我們需要把F值較小的元素排在前面。
我們使用一個6×6的比較複雜的地圖來測試。
地圖為
其中@表示機器人初始位置，*表示灰塵位置，#表示障礙物，_表示空格子。來看結果。
首先是A*算法，注意程式需要運作一段時間才會出結果：
可以看到周遊的節點數為42824個。
接下來是廣度優先搜尋算法，程式同樣需要運作一段時間才會出結果：
需要周遊的節點是56691個。可以看出以上兩種算法都可以得到最優解，而A*算法需要周遊的節點數要比廣度優先搜尋少14000個左右。
最後是深度優先搜尋。
可以看到深度優先搜尋的效率特别高，在隻周遊了155個節點的情況下得出了解。但是很顯然機器人選擇的線路比前兩種算法長很多。并不是最優解。
我在文中說過，A*算法中H值的估算的準确度可以影響到算法的效率，即最終周遊到的節點的數量。周遊的節點數量越少，算法的執行速度就越快。本文中僅僅是把H值估算為剩餘灰塵的數量，隻是為了說明H值的意義，但是這樣估算的準确度較低。在實際應用中，我們可以對H值進行更加準确的估算。比如在這個例子中，有一種思路是計算機器人目前位置與所有灰塵格子的距離的方差。但是這可能仍然不是特别準确，具體的思路和實作讀者可以自己進行考慮和斟酌。當然這也是A*算法的最大魅力：工程師可以在不同的情況中對算法進行不同的優化。