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

以下是要求以及移动方式。

四名传教士和四名食人族在河的西岸（W），旁边有一条船，最多可以容纳三人：0 < 船的容量 ≤ 3。寻找一种方法，将所有人转移到东岸（E），且在任何时候都不能让传教士在一个地方被食人族超过人数。这个问题在人工智能领域很有名，因为它是第一篇从分析角度处理问题制定的论文的主题（Amerel, 1968）。

回答：

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

然而，一般来说，一个有用的启发式来源是放宽一个或多个使问题变得困难的约束，从而“放松”问题（这是一个技术术语）。不幸的是，确定放宽哪些约束是一门艺术。对于这个问题，你可以放宽食人族不能超过传教士人数的约束，从而使启发式值成为一个简单的函数，仅取决于船的位置和河两岸的人数。