寻找启发式传教士和食人者

Question

我正在尝试构建一个*算法来解决传教士和食人者问题。我不确定我应该使用的启发式方法以及我应该寻找什么来尝试并最终解决这个问题。

这是您可以移动的要求和方式。

四个传教士和四个食人者在河的西岸（W），还有一艘最多可容纳三个人的船：0 <船的容量≤3。想办法让所有人都到东岸(E) 从未将一群传教士留在一个地方，人数多于那个地方的食人者。这个问题在 AI 中很有名，因为它是第一篇从分析角度处理问题表述的论文的主题（Amerel，1968 年）。

Answer 1

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

然而，总的来说，启发式方法的一个富有成效的来源是放弃一个或多个使问题变得困难的约束，从而 "relaxing" 问题（这是一个技术术语）。不幸的是，弄清楚哪些是一门艺术。对于这个特定问题，您可以放弃食人者人数不超过传教士的限制，从而使启发值成为船所在位置和河流两边人数的简单函数。