algorithm - 需要 AI 问题的可接受启发式

Question

我需要帮助来找出一个简单的启发式方法（这是可接受的/从不高估），使用 A* 搜索来解决 AI 问题：https ://en.wikipedia.org/wiki/Brigdge_ah_problem

请注意：我已经实现了高级问题，我可以在每一侧选择任意数量的人，将桥梁容量设置为任何值并选择火炬的结束位置。此外，目标可以是任何情况（其中一方不一定需要为空 - 例如，它可能必须以左侧 2 人和右侧 5 人结束）。

它背后的逻辑应该是什么，永远不会高估？

标签： algorithm

Answer 1

以下是构建启发式的两种方法：

建立启发式的一种常见方法是放宽原始问题定义，以允许以前无法采取的新行动。这样做只会使解决方案更短，因此我们可以使用它来获得可接受的启发式。当前的问题限制了一次只能有两个人在桥上，并且他们需要手电筒才能过桥。如果您放宽这两个要求，您只需花费原边某人通过的最长时间，这将为您提供可接受的启发式方法。也就是说，您假设它们都交叉并且您完成了。

示例 1：

原文：ABCD【火炬】

目标：

启发式：8 分钟（最多 1、2、5、8）

示例 2：

原文：ABC

目标：D [火炬]

启发式：5 分钟（最多 1、2、5）

您可以通过放松其中一个来做得更好 - 他们仍然需要火炬，但是任何数量的人都可以在桥上。如果火炬在原始一侧，那就是上面的启发式方法。否则，您可以将让手电筒恢复到原来一侧的最短时间添加到您的总时间中。（而且，如果火炬与慢的人在一起，那么慢的人将成为双向启发式计算的一部分。）

示例 3：

原文：ABC

目标：D [火炬]

启发式：16 分钟（8 分钟让 D 用火炬穿过，8 分钟让所有人回来）

示例 4：

原作：CD

目标：AB [火炬]

启发式：9 分钟（1 分钟让 A 用火炬穿过，8 分钟让每个人都回来）

另一种方法是将问题抽象为一个子问题（抽象问题中总共有 N 个人中只有 k 个）并彻底解决它。然后，当前状态的启发式是抽象问题中 k 个人的解决方案的成本。您可以通过这种方式进行多次抽象并最大限度地获得更好的启发式方法。