传教士和食人族的最佳搜索算法是什么?

Question

我以为这将是深度优先搜索(但这可能会陷入循环(，所以我认为这不是最好的算法。会*，统一成本吗,...或者呼吸优先搜索是否有机会成为最好的搜索算法？

Answer 1

答案取决于您正在测量的内容。可能的度量包括运行时间、节点扩展/生成、实现复杂性或其他。

我建议使用广度优先搜索(BFS(，因为它是最容易实现的，而且这个特定的问题足够小，甚至可以通过BFS几乎立即解决。

此外，需要注意的是，BFS 与具有零启发式的 A* 不同。BFS 可以在目标生成后立即终止，而 A* 会在目标从 OPEN 中删除以进行扩展时终止。此外，A*需要更复杂的数据结构，这些结构将更难实现，而BFS可以使用简单的FIFO队列。