最佳优先搜索（知情搜索）

最佳优先搜索是一种遍历技术，通过检查哪个结点最具希望然后对其进行检查，来确定接下来要访问哪个结点。出于此目的，它使用评估函数来判定遍历。

树遍历的这种最佳优先搜索技术属于启发式搜索或知情搜索技术。

结点的成本存储在一个优先级队列中。这使得最佳优先搜索的实现与广度优先搜索的实现相同。我们会使用优先级队列，就像我们在广度优先搜索中使用队列一样。

实现最佳优先搜索的算法

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) 时间。

更新于： 2019 年 11 月 22 日

6,000+ 浏览量

开启你的职业生涯

完成课程即可获取认证

开始
广告