logo标签列表

可接受启发式算法曼哈顿距离

algorithmartificial-intelligencea-starheuristics
7
我最近开始学习人工智能入门课程，并被分配了一个任务，在Python中实现一个可接受的启发式函数，用A*搜索解决15-Puzzle问题。
我实现了曼哈顿距离以及其他一些启发式算法。Python代码运行得很好，算法实际上解决了这个问题，但我对曼哈顿距离启发式是否适用于这个特定问题有一些疑问。
根据理论，如果启发式算法从不高估到达目标的成本，则它是可接受的。这意味着启发式算法是乐观的，并且返回的成本永远不会大于实际成本。
当初始状态如下所示时（0表示空槽）：
1  2  3  4
0  6  7  8
5  9  10 12
13 14 11 15

我的程序可以在5步内解决问题，但是每个放错位置的方块的曼哈顿距离之和等于10，是实际成本的两倍。因此，实际成本远低于估计成本。这是否意味着启发式函数不可用或者我的逻辑有问题？

我考虑只计算空块的曼哈顿距离，但这会导致当空块处于正确位置但其他方块放错位置时，状态的预估成本为零。

你还没有展示你的逻辑，我们怎么能够评估它呢？ - Robert Harvey
我对代码没有任何问题。我的问题是理论上的。这个问题可以通过五次移动来解决。每次移动空白块都是向上、向下、向右或向左移动。解决问题的五个步骤是：向下、向右、向右、向下、向右。但是，如果将启发式应用于初始状态，则返回10，这是实际成本的两倍。根据理论，它应该小于实际成本。你不需要代码来计算曼哈顿距离。 曼哈顿距离感谢快速回复 ;) - dimlucas
2
在我看来，你的例子中曼哈顿距离的总和确实是5。你怎么得到10的？ - j_random_hacker
2
@j_random_hacker 我怀疑他们加上了移动空白块的成本。 - Peter de Rivaz
我认为空白块的成本也需要计算在内。感谢澄清！ - dimlucas
1个回答
9

曼哈顿距离 启发式算法是可接受的，因为它独立地考虑每个图块（而事实上图块相互干扰）。因此，它是乐观的。

在您的示例中，所有图块到目标位置的距离之和为5（图块5、9、10、11、15需要移动一次）。

enter image description here

2
谢谢，我正在添加移动空白块的成本。 - dimlucas
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接