[UVA10181]十五数码解题报告

对于有解的情况，只需ID-A*即可。 首先谈一谈估价函数，估价函数表示的应该是对期望步数的下界。我一开始想的是用所有数现在的位置到应该在的位置的曼哈顿距离和，考虑到一次交换最多令其减少2，所以还要把它除以2。后来看了题解发现所有题解都是用的所有非0数的现在的位置到目标位置的曼哈顿距离和，这样的话一次交换最多令其减少1，这样应该是比较合适的。。 我一开始写的A*，（因为没有看懂ID-A*）A*需要面对map判重、heap维护，空间复杂度与时间复杂度相同，且挂了log的常数，时间空间都不占优。 后来终于看懂了ID-A*，ID-A*为什么不用判重？是因为我们考虑搜索树中的一个节点，如果它（假设我们做一个简单的剪枝、拒绝反着走到达当前状态的最后一步）被再次搜到，就意味着它至少又转了四下。也就是说一个点至多被搜，即其常数约为13！也就是说这其实是比用平衡树判重快得多的。但是ID-A*是不能像A*一样每次取出预估最优的状态的，它只能通过调整上下来解决这个问题；这跟DFS与ID-DFS的区别还不一样，因为在一个预估较劣的状态可能会达到一个预估较优的状态。所以实际上ID-A*与A*的区别还是很大的，它实际上并不是A*的简单优化；它也并不一定比A*跑得更快，如果你的估价函数不是很准的话。。

其实这个题更有意思的地方，在于对于无解的判断。 我在网上并没有找到关于15数码的完整证明，不过有8数码的，但是我似乎并不能把它推广到15数码甚至是N*M数码。但是我前前后后研究了差不多有4个月，在这里将会给出一个严谨的证明。 命题： 在一个N*M（）的矩阵中，我们放入0~N*M-1的排列，称之为数码。 我们允许两种操作，一种是将0与其所在的格子左右相邻的格子里的数互换，一种是将0与其所在的格子上下相邻的格子里的数互换。 则 当M为奇数时，两种数码可以互达与两种数码【排列逆序对数（不算0）】奇偶性相同等价。 当M为偶数时，两种数码可以互达与两种数码【排列逆序对数（不算0）+0的纵坐标】奇偶性相同等价。

证明： 首先证明两种数码可以互达当且仅当……（后面那一串） 考虑0左右移动，显然不会改变不算0的排列的逆序对数；而上下移动的话，考虑增量，就相当于是有M-1个数，每个数∈{-1,1}，问其和？在模2意义下，-1≡1，所以其实它们的和在模2意义下恒等于M-1. 那么接下来的事情就很显然了，其实这个玩意儿本身就是构造的，奇数的时候不用管它，反正M-1≡0（mod 2）；偶数的时候，上下移动0的纵坐标就会+1或-1，所以再加上0的纵坐标的话，奇偶性就不会变了。

好！接下来就是真正的核心部分了！（我可是玩了很久才玩出规律的。。） 由于两个数码之间的变换是可逆的，现在所有的数码都分为了两类，所以如果我们能证明出所有的数码都能变换到两个数码之一，那么就好了！ 我们选择将所有数码变换成类似这种形状：

或

但是我们该怎么做呢？ 首先我们看一下前人对八数码的研究（因为由于排版造成的问题。。我进行了一些修改。）：

转载自【水木清华BBS精华区】：

发信人: YourMajesty (花痴~~~~小魔男), 信区: AI 标 题: 关于八码数问题有解与无解的证明(zz) 发信站: BBS 水木清华站 (Fri Nov 23 22:26:49 2001)

我们将九宫格按行排成一行共九个数(空格也占一个位置，在本文种，我用@表示空 格)。比如： 1 2 3 4 @ 5＝> 1 2 3 4 @ 5 6 7 8 这样 6 7 8 ，九宫格的每一种状态和上图的行之间是一一对应的。 为了证明上述定理，我想先对问题进行一下转化。我定义两种行序列的变换：一种是空格@和相邻的数对换，一种是空格@和前后隔两个数的数之间的对换（按：或是从这一行的行首到上一行的行末），，前者对应着空格在九宫图中的左右移动，后者对应着空格在九宫图中的上下移动。 引理一：在上述的两种对换下，序列的奇偶性不改变。 这个引理很容易证明。 首先，相邻的对换肯定不改变奇偶性；其次，隔两格的对换也不改变奇偶性，它相当于三个数的轮换。这就说明了奇九宫图和偶九 宫图之间是互不可达的。 引理二：转化后行序列在上面定义的两种对换下的任意操作，可以转换成九宫图中 空格的合法变化。 这个引理也是比较容易证明的。我们只要证明如下的两种状态之 间是互达的： 1 2 31 2 3 4 5 6<=>4 5 @ @ 7 86 7 8 通过计算机搜索，可以发现上面两种状态之间的确是互达的。（按：我们其实也可以构造，使用与后面类似的方法。将数成对竖着排起来即可。由于非常简单而且我不会推广到高维。。这里略去不详细说明）从而，我们可以假定上面两种状态之间的转换可以用行序列中的两种邻对换来代替。 引理三：所有的奇状态可以转换为 @ 1 2 3 4 5 6 7 8, 所有的偶状态可以转换为 @ 2 1 3 4 5 6 7 8. 要证明这个引理，得分几个步骤。我的想法是先设法把8移到最后一个，然后8保持不动(注意，我们这里的不动只是形式上不动，但不管怎样，我们的每一个变换后，8还是保持在最后一个，余类似)，再将7移到8之前，然后， 保持7和8不动，依次移动6，5，4，3，得到 * * * 3 4 5 6 7 8这里 * * *是 @ 1 2 的一个排列。到这里，我想要得到前面的两种状态之一是显然的了。下面，我说明，上面的想法是可以实现的。如下： 1. 对于 a b c @ ，我们可以将其中的任意一个移到 最后，并且对变换仅限于这四个位置上。显然，对于a，c是一步就可以做到的。对于b， 步骤如下： a b c @ -> @ b c a -> b @ c a -> b c @ a -> b c a @ -> @ c a b 2. 先把要移到最后位置的那个数移到最后四个位置之一，然后再将空格移到最后一个位置，用1的方法将待移动的数变换到最后一个位置。循环这样做即可。引理三证毕。 证完了这三个引理，定理的成立就是显然的了。首先，将奇偶性相同的两种状态都变换到上述两种标准状态之一，然后对其一去逆变换即可。

我们知道M=5与M=3是相似的，但是我感觉这个证明如果往M=5的情况推广的话，会遇到很大问题啊。因为这样的话最终它需要面临的就不再是1~2的排列了，而是1~4的排列。。然而我们却希望把它们划归到两种状态。

你曾经说，你曾经说。走在爱的旅途，我们的脚步多么轻松……