最佳優先搜尋（知情搜尋）

最佳優先搜尋是一種遍歷技術，透過檢查哪個結點最具希望然後對其進行檢查，來確定接下來要訪問哪個結點。出於此目的，它使用評估函式來判定遍歷。

樹遍歷的這種最佳優先搜尋技術屬於啟發式搜尋或知情搜尋技術。

結點的成本儲存在一個優先順序佇列中。這使得最佳優先搜尋的實現與廣度優先搜尋的實現相同。我們會使用優先順序佇列，就像我們在廣度優先搜尋中使用佇列一樣。

實現最佳優先搜尋的演算法

Step 1 : Create a priorityQueue pqueue.
Step 2 : insert ‘start’ in pqueue : pqueue.insert(start)
Step 3 : delete all elements of pqueue one by one.
   Step 3.1 : if, the element is goal . Exit.
   Step 3.2 : else, traverse neighbours and mark the node examined.
Step 4 : End.

此演算法將首先遍歷佇列中最短路徑。在最壞的情況下，演算法需要 O(n*logn) 時間。

sudhir sharma

更新於： 2019 年 11 月 22 日

6,000+ 瀏覽量

開啟你的職業生涯

完成課程即可獲取認證

開始