AITerms 登入
AI基礎演算法搜尋演算法

最佳優先搜尋(Best-First Search)是什麼?

最佳優先搜尋每一步都先展開目前估計最好的候選,通常用優先佇列實作,貪婪搜尋與 A* 搜尋都是它的變體。

同主題的術語AI基礎

完整定義

最佳優先搜尋(Best-First Search)是一種狀態空間搜尋演算法,每一步都先處理目前「估計最好」的部分解,通常用優先佇列(priority queue)實作,評估值最好的候選排在最前面。「最好」怎麼估決定了它的變體:只看目前已花成本的是均一成本搜尋(Uniform-Cost Search),只看到目標的估計成本的是貪婪最佳優先搜尋(Greedy Best-First Search,NIST 稱為 greedy search),把已花成本加上到目標的估計成本的是 A* 搜尋。NIST 演算法與資料結構辭典把它描述為改良的廣度優先搜尋:廣度優先搜尋通常用一般佇列,依離起點的步數一層一層往外擴展,最佳優先搜尋則依評估值決定下一步先探索哪裡。這個名稱有廣義與狹義兩種用法,有些教材的「最佳優先搜尋」專指貪婪的版本。例如在地圖上找路線時,用沿道路走過的距離加上到目的地的直線距離當評估值,就是 A* 搜尋的做法。

白話說明

要在一大堆可能的路線裡找到終點,先走哪一條?

最佳優先搜尋的做法是:替目前待展開的候選算一個「評估值」排出順序,每一步都先展開看起來最有希望的那一個。

評估值怎麼算,決定它是均一成本搜尋、貪婪最佳優先搜尋還是 A* 搜尋,它們都是同一個家族。

記住這句

待展開的候選排好優先順序,每次先看評估最好的那一個。

比喻:最佳優先搜尋像在陌生城市找餐廳,手上有一張依評估分數排好順序的清單,每次都先去清單最前面的那家,不滿意就把附近新發現的選項排進清單,再挑最前面的

容易混淆

最佳優先搜尋 vs 廣度優先搜尋

廣度優先搜尋通常用一般佇列,先把離起點步數少的一層看完,再往外一層(步數是經過幾條邊,不看實際距離)

最佳優先搜尋通常用優先佇列,不管層次,評估值最好的先看

最關鍵的區別是下一步怎麼決定。NIST 把最佳優先搜尋描述為改良的廣度優先搜尋,改良指的是用評估值決定順序,不代表每個變體都比較好。

貪婪最佳優先搜尋 vs A* 搜尋

貪婪最佳優先搜尋只看到目標還要多少的估計成本,不保證找到成本最低的路徑

A* 搜尋把已經花掉的成本加上到目標的估計成本一起算,只要估計值不會高估實際剩下的成本,就保證找到成本最低的路徑

最關鍵的區別是有沒有把已花的成本算進去,兩者都是最佳優先搜尋的變體。

實際案例

地圖找路線

從台北找路到高雄,把每個路口當成節點,用「從台北沿道路走到這個路口的距離」加上「這個路口到高雄的直線距離」當評估值,評估值最小的路口先展開,這就是 A* 搜尋的做法。道路距離不可能比直線距離短,這個估計值不會高估,所以 A* 能找到最短路線。

AI 代理挑下一步(示意情境)

假設把 AI 代理執行行動後到達的每個狀態看成節點,替每個狀態打一個分數放進優先佇列,每次取出分數最好的往下試。新的候選也依分數排進佇列,所以下一步可能沿著目前這條路繼續走,也可能跳回先前分數更好的另一條路,這就是最佳優先的思路。

演算法與應用

把起點放進優先佇列,評估值最好的排在最前面。

每一輪取出佇列最前面的節點,如果是目標就結束,不是的話就把它標記為已展開,算出它的鄰居的評估值放進佇列,避免在有環的圖上重複展開同一個節點(A* 找到更便宜的路徑時要更新)。

評估值怎麼算決定變體:只看已花成本是均一成本搜尋,只看到目標的估計成本是貪婪最佳優先搜尋,兩者相加是 A* 搜尋。

以 A* 為例,只要到目標的估計值不會高估實際剩下的成本,就保證找到成本最低的路徑。估計值不準時可能先探索很多沒有希望的方向,如果高估,A* 可能找不到最短路徑。

情境判斷

Q1(直覺題):搜尋時把所有候選依「估計離目標多近」排序,每次先展開最近的那個,這是什麼搜尋策略?

這是最佳優先搜尋,只看到目標估計成本的版本稱為貪婪最佳優先搜尋,有些教材直接把它叫做最佳優先搜尋。

Q2(判斷題):最佳優先搜尋和廣度優先搜尋一樣,都用一般佇列先進先出?

不對。廣度優先搜尋通常用一般佇列,最佳優先搜尋通常用優先佇列,依評估值決定順序。

常見問題

相關術語

本頁內容有提到,或屬於同一組主題的術語

來源

參考來源:xlinux.nist.gov

其他格式:Markdown 版本