使用 A* 搜索解决山羊、狼和卷心菜问题

Question

在我的算法课程中，我们遇到了使用 A* 搜索解决山羊、狼和卷心菜问题的挑战。

问题陈述如下： 一个农民想把这三个人都运过河。但是如果单独留下山羊和卷心菜，山羊会吃卷心菜*，如果狼和山羊单独留下，狼会吃山羊！

我一直在努力为这个问题找到一个有意义的启发式函数，任何帮助将不胜感激。

Answer 1

这个怎么样：每个“地方”都是4元组，山羊、狼、卷心菜和农夫的位置。如果从一个地方到另一个地方的过渡代表一个单一的、合法的举动，那么这些地方就是相连的。

现在距离启发式是，如果一个食者和它吃的东西在同一侧并且农民不在那里，则距离是无限的。

示例：状态是

(farmer: left, goat: left, cabbage: left, wolf: left)

（所有都在左岸）所以连接到（假设规则是你可以在船上携带任何两件东西但不能更多）

(farmer: right, goat: right, cabbage: right, wolf: left)

并且该距离是1因为那是安全的并且它也连接到

(farmer: right, cabbage: right, wolf: left, goat: left)

但是那个距离是无限的因为可怜的山羊会被吞噬。

Answer 2

一个简单的启发式方法可以是仍然在河流起始侧的物品数量乘以 2，如果船在同一侧则减去 1。所以初始状态有启发式 5.