完整定義
最佳優先搜尋(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(判斷題):最佳優先搜尋和廣度優先搜尋一樣,都用一般佇列先進先出?
不對。廣度優先搜尋通常用一般佇列,最佳優先搜尋通常用優先佇列,依評估值決定順序。
常見問題
一種狀態空間搜尋演算法,每一步都先處理目前估計最好的部分解,通常用優先佇列實作,評估值最好的候選先展開。
廣度優先搜尋通常用一般佇列,依離起點的步數一層一層往外擴展。最佳優先搜尋通常用優先佇列,依評估值決定先探索哪裡。NIST 把它描述為改良的廣度優先搜尋,改良指用評估值決定順序,不代表每個變體都比較好,例如貪婪最佳優先搜尋就不保證找到成本最低的路徑。
A* 搜尋是最佳優先搜尋的一種,評估值是目前已花的成本加上到目標的估計成本。只要估計值不會高估實際剩下的成本,A* 就保證找到成本最低的路徑。
這個名稱有兩種用法。廣義的最佳優先搜尋指依評估值展開的整個家族,包含均一成本搜尋、貪婪搜尋與 A*,NIST 與 Russell 和 Norvig 的人工智慧教科書採用這種用法。有些作者則把只看到目標估計成本的貪婪搜尋直接叫做最佳優先搜尋,看題目時要注意是哪一種。
通常用優先佇列,每次取出評估值最好的候選,再把新的候選依評估值放回佇列。
相關術語
本頁內容有提到,或屬於同一組主題的術語
來源
參考來源:xlinux.nist.gov
其他格式:Markdown 版本