[AI]贪婪最佳优先搜索 Greedy Best-First Search

一、算法原理

所谓贪婪，即只扩展当前代价最小的节点(或者说离当前节点最近的点)。这样做的缺点就是，目前代价小，之后的代价不一定小，如果解在代价最大的点，那么按照贪婪最佳优先算法，可能就找不到这个解，然后就会陷入死循环。

公式表示为：
f ( n ) = h ( n ) f(n)=h(n) f(n)=h(n)

h ( n ) h(n) h(n)代表当前节点到目标节点的最短距离。

二、算法应用

我们来举个例子实际应用一下该算法。

著名的Romania地图，以Bucharest为目标，Arad为起点：

• 初始状态：
  

• 扩展 Arad后：
  

• 可以看到Sibiu的路径最短，那么扩展Sibiu：
  

• 然后Fagaras路径最短，那就扩展Fagaras，然后就找到了目标节点：

三、算法性能

完成情况	时间复杂度	空间复杂度	评价
当陷入死循环时不能找到解	O(bm)	O(bm)	无最优解

各位看官老爷，一键三连再走吧~再不济点个赞也行啊~~