8

我使用广度优先搜索构建了一个 8 谜题求解器。我现在想修改代码以使用启发式方法。如果有人能回答以下两个问题，我将不胜感激：

可解性

我们如何决定一个 8 谜题是否可解？（给定一个起始状态和一个目标状态）这是维基百科所说的：

不变量是所有16个方格排列的奇偶性加上右下角空方格的出租车距离（行数加列数）的奇偶性。

不幸的是，我无法理解那是什么意思。理解起来有点复杂。有人可以用更简单的语言解释吗？

最短的解决方案

给定一个启发式，是否保证使用 A* 算法给出最短的解决方案？更具体地说，打开列表中的第一个节点是否总是有一个深度（或如此胖的移动次数），它是打开列表中所有节点的深度中的最小值？

启发式是否应该满足某些条件才能使上述陈述为真？

编辑：一个可接受的启发式方法如何总是提供最佳解决方案？我们如何测试启发式是否可以接受？

我将使用此处列出的启发式方法

Manhattan Distance 
Linear Conflict 
Pattern Database 
Misplaced Tiles
Nilsson's Sequence Score 
N-MaxSwap X-Y 
Tiles out of row and column

来自 Eyal Schneider 的澄清：

在此处输入图像描述 在此处输入图像描述 在此处输入图像描述

4

3 回答 3

6

我将仅提及可解决性问题。需要一些排列背景。

排列是对有序集合的重新排序。例如，2134 是列表 1234 的重新排序，其中 1 和 2 交换位置。排列具有奇偶性；它是指反转次数的奇偶性。例如，在以下排列中，您可以看到恰好存在 3 个反转 (23,24,34)：

1234
1432

这意味着排列具有奇校验。以下排列具有偶校验 (12, 34)：

1234
2143

自然，身份排列（保持项目顺序）具有偶数奇偶性。

15个拼图（或8个拼图）中的任何状态都可以看作是最终状态的排列，如果我们将其视为行的串联，从第一行开始。请注意，每个合法移动都会改变排列的奇偶性（因为我们交换了两个元素，并且涉及它们之间的项目的反转数量必须是偶数）。因此，如果你知道空方格必须经过偶数步才能到达其最终状态，那么排列也一定是偶数。否则，您将以最终状态的奇怪排列结束，这必然与它不同。与空方格的奇数步数相同。

根据您提供的 Wikipedia 链接，上述标准对于解决给定的谜题是足够且必要的。

于 2013-02-17T12:00:15.450 回答
3

如果您的启发式总是低估实际成本（在您的情况下，需要移动到解决方案的实际数量），则A* 算法可以保证找到（如果有多个相等的短解决方案，则为一个）最短解决方案。

但是在飞行中，我无法为您的问题想出一个好的启发式方法。这需要一些思考才能找到这样的启发式方法。

使用 A* 的真正艺术是找到一个总是低估实际成本但尽可能少的启发式算法以加快搜索速度。

这种启发式的第一个想法：

  1. 在我脑海中突然出现的一个非常实用但有效的启发式方法是空场到最终目的地的曼哈顿距离。
  2. 每个字段到其最终目的地的曼哈顿距离之和除以可以在一次移动中改变位置的最大字段数。（我认为这是一个很好的启发式）
于 2013-02-17T11:32:33.930 回答
0

对于任何出现的人，我将尝试解释 OP 如何获得值对以及他如何确定突出显示的值对，即反转，因为我花了几个小时才弄清楚。首先是对。首先取目标状态并将其想象为一维数组（例如 A）[1,2,3,8,0,4,7,5]。该数组中的每个值在表中都有自己的列（一直向下，这是该对的第一个值。）然后在数组中向右移动 1 个值（i + 1）并一直移动再次下降，第二对值。例如（状态 A）：第一列，第二个值将从 [2,3,8,0,4,7,5] 开始下降。第二列，将开始 [3,8,0,4,7,5] 等。

现在好了。对于 2 对值中的每一个，在开始状态中找到它们的INDEX位置。如果左INDEX > 右INDEX那么它是一个反转（突出显示）。前四对状态 A 是：(1,2),(1,3),(1,8),(1,0)
1 在索引 3
2 在索引 0
3 > 0 所以反转。

1 是 3
3 是 2
3 > 2 所以反转

1 是 3
8 是 1
3 > 2 所以反转

1 是 3
0 是 7
3 < 7 所以没有反转

对每一对执行此操作并计算总反转。如果都是偶数或都是奇数（曼哈顿距离的空白点和总反转），那么它是可以解决的。希望这可以帮助！

于 2017-01-02T17:12:07.077 回答