8数码问题：可解性和最短解决方案

Question

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

可解性

我们如何确定8拼图是否可解？（给定起始状态和目标状态） 这是维基百科上的说法：
“不变量是所有16个方块的排列的奇偶性加上空方格从右下角到达的出租车距离（行数加上列数）的奇偶性。”

不幸的是，我无法理解它的含义。它有点复杂难懂。有人能用更简单的语言解释一下吗？

最短解决方案

给定一个启发式算法，它能保证使用A*算法得到最短的解决方案吗？更具体地说，开放列表中的第一个节点的深度（或迄今为止所做的移动次数）是否总是所有节点的深度的最小值？

启发式算法是否需要满足某些条件才能使上述语句成立？

编辑：为什么可接受的启发式算法总是提供最优解？以及我们如何测试一个启发式算法是否可接受？

我将使用此处列出的启发式算法here。

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

---

针对 Eyal Schneider 的澄清：

---

- Ranjith

---

广告 #2：是的，如果您使用一个可接受的启发式算法（永不高估），A*算法保证找到最优解。 - John Dvorak

有没有办法可以检查一个启发式函数是否是可接受的？我想使用此页面上列出的各种启发式函数：http://heuristicswiki.wikispaces.com/N+-+Puzzle - Ranjith

我希望有人能够解释如何测试一个启发式函数的可行性。 - Ranjith

Answer 1

我只提到可解性问题。需要一些排列组合的背景知识。

排列是有序集合的重新排序。例如，2134是列表1234的重新排序，其中1和2交换位置。排列具有奇偶性属性；它指的是逆序对数量的奇偶性。例如，在下面的排列中，您可以看到恰好存在3个逆序对（23、24、34）：

1234
1432

这意味着该排列具有奇置换。下一个排列具有偶置换（12, 34）。

1234
2143

自然情况下，保持项目顺序的恒等置换具有偶数奇偶性。

如果我们将15拼图（或8拼图）中的任何状态视为最终状态的排列，那么它就是从第一行开始连接的排列。请注意，每个合法移动都会改变排列的奇偶性（因为我们交换了两个元素，它们之间涉及的倒置数量必须是偶数）。因此，如果您知道空方块必须走过偶数步才能到达其最终状态，则排列也必须是偶数。否则，您将得到最终状态的奇排列，这与它不同。空方块的步数为奇数也是如此。

根据您提供的维基百科链接，上述标准足够且必要以使给定的谜题可解。

- Eyal Schneider

---

我理解了什么是奇偶性。 现在，来看这个句子： “所有9个方块的排列的奇偶性加上空白方块到右下角的出租车距离（行数加列数）的奇偶性” 因此，我们将通过将其视为目标状态的排列并将其添加到某个其他数字中来获得状态的奇偶性作为整数。（出租车距离的奇偶性）现在，出租车距离本身不就是一个数字吗？它的奇偶性是什么意思？ - Ranjith

@Ranjith：它意味着数字的简单奇偶性。您可以将其视为0和1，因此添加奇偶校验位只是检查总和的奇偶校验位。 - Eyal Schneider

@Ranjith：现在，可解性标准很简单：当且仅当以下两个条件相等时，谜题才是可解的：1）空方块需要移动的步数的奇偶性（只需计算起始位置和结束位置之间的曼哈顿距离的奇偶性）。2）与目标状态相比，初始状态所表示的排列的奇偶性。 - Eyal Schneider

@Ranjith-SR2GF：是的，看起来没问题，除了B案例中的一个笔误，数字3被错误地标记为偶数... - Eyal Schneider

@Ranjith-SR2GF：你应该证明你的启发式函数是可接受的。 - Eyal Schneider

Answer 2

A*算法保证能够找到（如果有多个等效的最短解，则只找到其中一个）最短解，前提是你使用的启发函数始终低估实际代价（在此建议为到达解决方案所需的实际步数）。

但目前我还不能提供一个好的启发式函数来解决您的问题。这需要一些思考才能找到这样的启发式函数。

真正灵活运用A*算法的技巧在于找到一个始终低估实际代价但尽可能少地加速搜索的启发式函数。

---

以下是几种可行的启发式函数：

1. 我想到的一个非常简单但有效的启发式函数是空格到其最终位置的曼哈顿距离。
2. 每个方格到达最终位置的曼哈顿距离之和除以可以在一步内改变位置的最大方格数量（我认为这是一个相当不错的启发式函数）。

- MrSmith42

---

关于可解性部分有什么想法吗？ - Ranjith

@Ranjith - SR2GF：我还没有关于可解性部分的想法。天真的方法是：尝试找到一个解决方案，如果没有，你就不会找到一个解决方案;-) - MrSmith42

但那需要很多时间！ - Ranjith

@Ranjith - SR2GF：关于solvability（可解性）：1. 一般来说，这些谜题是可以解决的。2. 如果你在开始时交换两个相邻的方格，一个不可解的谜题也可以变得可解。因此，一种可能性是尝试解决这个谜题，并同时尝试解决交换了一个相邻对方格的谜题。如果在修改后的版本中找到了解决方案，则原始谜题是不可解的。 - MrSmith42

这是一个好主意 - 并行解决原始谜题和交换的谜题。如果我可以直接检查可解性会更好。 - Ranjith

感谢回答问题的第二部分。 - Ranjith

Answer 3

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

好的，现在来讲一下逆序对。对于每一对值，找到它们在起始状态中的索引位置。如果左边的索引大于右边的索引，那么就是一个逆序对（已经高亮显示）。状态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，所以没有逆序对

对于每一对进行这个操作，并计算总逆序对数。如果两者都是偶数或奇数（空格的曼哈顿距离和总逆序对数），则可以解决。希望这能帮到你！

- David