寻找一个启发式的传教士和食人族

Question

我正试图建立一个算法来解决传教士和食人族的问题。我不确定我应该使用什么样的启发式，也不确定我应该寻找什么来尝试并最终解决这个问题。

这是你可以移动的需求和方式。

西岸(W)上有四名传教士和四名食人者，还有一艘可容纳三人的船:0<≤3号船的容量。想办法把每个人都送到东岸(E)，而不把一群传教士留在一个地方，人数超过那里的食人族。这个问题在人工智能中很有名，因为它是第一篇论文的主题，从分析的角度来探讨问题的制定(Amerel，1968)。

Answer 1

这个特定的状态空间足够小，你可以先用广度优先搜索来探索它。

然而，通常情况下，启发式的一个有效来源是放弃一个或多个使问题变得困难的约束，从而“放松”问题(这是一个技术术语)。不幸的是，弄清楚哪些是一门艺术。对于这个特殊的问题，你可以放弃食人族人数不超过传教士的限制，从而使启发式值成为一个简单的函数，即船在哪里，河的两边有多少人。