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

我只会提到可解决性问题.需要一些排列的背景.

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

1234
1432

这意味着置换具有奇数奇偶性.以下排列具有偶数奇偶校验(12,34):

1234
2143

当然,身份置换(保持项目顺序)具有均衡性.

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

根据您提供的维基百科链接,上述标准对于给定的谜题是可解的是足够的和必要的.

Answer 2

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

但我无法即时为你的问题想出一个好的启发法。需要一些思考才能找到这样的启发式方法。

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

这种启发式的初步想法：

1. 我脑海中突然出现了一个相当简单但有效的启发式，那就是空域到最终目的地的曼哈顿距离。
2. 每个字段到最终目的地的曼哈顿距离之和除以一次移动中可以改变位置的最大字段数。（我认为这是一个很好的启发）