启发式将如何影响Dijkstra的算法，使其成为A *算法

Question

我正在开发一种应该解决传教士和食人族问题的A *算法。我不理解的是启发式的做法是使搜索节点少于Dikstras算法。

据我所知，程序将首先使用启发式值+当前值来搜索最佳值，以确定可能的值，但算法如何知道何时停止搜索而不是分支到其他节点？

Answer 1

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