8难题：可解性和最短解

Question

我使用广度优先搜索构建了一个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的澄清：

Answer 1

对于即将到来的任何人，我将尝试解释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]等。

好了，现在开始倒转。对于两对值中的每一个，在开始状态下找到它们的索引位置。如果左侧索引

1是3
3是2
3

1是3
8是1
3

1是3
0是7
3

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

Answer 2

如果您的启发式算法总是低估实际成本（在您的情况下，实际需要移动到解决方案的次数），那么A*算法保证能够找到（如果有多个相等的短路径）最短的解决方案。

但在飞行中，我不能想出一个好的启发你的问题。这需要一些思考才能找到这样的启发。

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

这种启发式的最初想法：

1. 在我脑海中浮现的一个相当重要但有效的启发是，空旷场地到其最终目的地的曼哈登距离

Answer 3

我只会提到可解决性问题。需要一些排列方面的背景知识。

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

1234
1432

这意味着置换具有奇偶校验。以下排列具有偶数奇偶性（12，34）：

1234
2143

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

15字谜（或8字谜）中的任何状态都可以被视为最终状态的排列，如果我们将其视为从第一行开始的行的串联。请注意，每一个合法的移动都会改变排列的奇偶校验（因为我们交换两个元素，并且涉及它们之间的项目的倒置次数必须是偶数）。因此，如果您知道空方块必须行进偶数步才能达到其最终状态，那么排列也必须是偶数。否则，您将以最终状态的奇数排列结束，这必然与它不同。空方块的奇数步也是如此。

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