algorithm - Heuristic 将如何影响 Dijkstra 算法使其成为 A* 算法

Question

我正在开发一种 A* 算法，旨在解决传教士和食人者问题。我不明白的是启发式算法是如何使搜索的节点数少于 Dikstras 算法的。

我理解程序会根据启发式值+当前值来确定可能的值，从而根据最佳优先进行搜索，但是算法如何知道何时停止搜索而不分支到其他节点？

Answer 1

启发式必须保证它永远不会太高(假设您正在寻找最小的解决方案)。因此，一旦找到完整的解决方案，您就知道它一定是最好的。任何不完整的解决方案(已经比您当前的解决方案具有更高的值(value)，否则您会进一步探索它)在完成后只会更高。