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

Question

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

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

四名传教士和四名食人者在河的西岸 (W)，还有一艘最多可容纳三个人的船：0 < 船容量 ≤ 3。想办法让每个人都到达东岸 (E)把一群传教士留在一个地方，那个地方的食人族人数超过了那个地方。这个问题在人工智能中很有名，因为它是第一篇从分析的角度研究问题表述的论文的主题（Amerel，1968）。

标签： algorithmartificial-intelligencegraph-algorithmheuristics

Answer 1

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

然而，一般来说，启发式方法的一个富有成效的来源是放弃一个或多个使问题变得困难的约束，从而“放松”问题（这是一个技术术语）。不幸的是，弄清楚哪些是一门艺术。对于这个特定的问题，您可以放弃食人族人数不超过传教士的限制，从而使启发式值成为船在哪里以及河两岸有多少人的简单函数。