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

关于埃亚尔·施耐德的澄清：

​

​

Answer 1

我只谈可解决的问题。需要一些排列的背景知识。

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

1234
1432

这意味着置换具有奇偶性。以下排列具有偶数奇偶(12，34)：

1234
2143

当然，身份置换(保持项目顺序)具有偶数的奇偶性。

如果我们从第一行开始，将15个谜题(或8个谜题)中的任何状态看作是最后一个状态的排列，则可以将它看作是行的连接。注意，每一次合法的移动都会改变置换的奇偶性(因为我们交换了两个元素，并且涉及到它们之间的项的反转的数目必须是偶数)。因此，如果你知道空的正方形要经过偶数步才能到达它的最终状态，那么置换也必须是偶数。否则，您将以最后状态的奇怪排列结束，这必然与其不同。对于空正方形的奇数步也是一样的。

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

Answer 2

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

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

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

这种启发的第一个想法：

1. 在我的脑海中出现了一个很好但很有效的启发，那就是空旷的田野到它的最终目的地的曼哈顿距离。
2. 每个字段到其最终目的地的曼哈顿距离之和，除以可以在一次移动内改变位置的最大字段数。(我认为这是一个很好的启发)