关于这题的无解的证明如下：
有人发现15-puzzle的状态可以均分为两个状态集：同一状态集中的
任意两个状态可以相互转换，非同一状态集的则不能。证明后一半不难，先从8-puzzle
开始，目标状态是：
1 2
3 4 5
7 8 9
对任意一个状态，如果按照从左到右，从上到下的顺序列出，去掉空白，就是
一个8个数的排列了。如果空白左右移动，排列不变。如果空白上下移（如果可以的话，
相当于排列中的某一数向前或向后移2个位置，不难证明新的排列逆序数齐偶性不变。
所以无论空白如何移，其产生的排列逆序数齐偶性恒定。
下一步看15-puzzle了，其目标状态是
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
空白左移右移，排列不变。空白上移或下移一次，排列逆序数齐偶性倒转。要构造
出一个恒定的measurement，我们可以用逆序数与空白所在行的行数之和的齐偶性。根据这
种齐偶性很容易判断出一个状态是否有解。
不过一些研究者却发现这种sliding-tile puzzles是一个很好的搜索算法的试验场，
于是许多search enhancements陆陆续续被提出，在人工智能很多领域都得到了应用。不
过他们更关心一个instance的最优解，即用最小的步数移到目标状态。下面是一些介绍
了：
1. 8-puzzle: 已经全部解决。所以有解状态都被解出。最难的状态需要31步
2. 15-puzzle: 能够比较快得解出随机生成的instances
3. 24-puzzle: 能够解出随机生成的instnaces，但是需要很多时间(比如1个月以上）。
一般最优解的长度在100以上，
对于n*m puzzle (m,n>1) 且n为齐数，逆序数齐偶性相同的状态可以相互转化。
(n为列数，m为行数).偶就不严密证了，点点就行了：
首先，注意以下转换：
1 2 -> 1 2
3 4 5 5 3 4
要不熟的话，排一排也就出来了，大概要十来步。这个转换告诉我们一行中
任意元素可以跳到与其相距为二的同一行位置，且有一相邻行有空格。（在
例子中，5插到3的位置）。
接下来我们又可以得到以下转换：
1 2 -> 3 1 2 -> 1 2 3
3 4 5 4 5 4 5
这步直接用到了上面的结论。
所以我们可以得到以下结论：排列相同的状态都可以相互转化。
下一个引论就是： 如果一个排列可以通过移动某一排列中的一个元素向前或者
向后两个位置得到，那么这两个排列所对应的状态都可以相互转化。这个引论
可以通过以上两个结论证出。
举个例子：
排列A: (1,2,3,4,5,6,7,8)
排列B: (1,4,2,3,5,6,7,8)
排列A 中将4 向前移动两位就可以得到排列B
所以状态
1 2 3 1 4 2
4 5 可以转化到 3 5 6
6 7 8 7 8
下面只需证明所有逆序数为偶数的排列都可以通过若干次两位移动从排列
(1,2,3,...,n-1,n)中得到，而逆序数为齐数的排列都可以通过若干次两位移动
从排列(1,2,3,...,n)中得到。这个可以用数学归纳法证明，比较简单。
n为偶数的情况:
定理一：如果相邻行有空格，经过有限次移动，一行中任意元素可以跳到与其相距为
二的同一行位置。
这个定理在前面已经证明了。一个推论就是该元素可以向前或向后移动偶数个位置。
下面观察一个2*4的转换：
1 2 3 4 1 2 3 4 3 1 2 3 1 4 2 1 4 2
4 5 6 7 -> 5 6 7 -> 5 6 7 -> 5 6 7 -> 3 5 6 7
4 up 3 jump ahead 4 jump back 3 down
于是我们可以得到以下结论：
对于2*4-puzzle，如果一个排列可以通过移动某一排列中的一个元素向前或者
向后两个位置得到，且在这两个排列所对应的状态中空白在第一行，这些状态
可以相互转化.
这个结论可以先推广到2*n-puzzle(n为偶数):
假设n=2k
1 2 ... 2k-1 2k 1 2 ... 2k-1
2k 2k+1 2k+2 ... 4k-1 -> 2k+1 2k+2 ... 4k-1
(2k up)
2k 2k-1 1 2 ... 2k-2 2k-1 1 2 ... 2k 2k-2
-> 2k+1 2k+2 2k+3 ... 4k-1 -> 2k+1 2k+2 ... 4k-2 4k-1
(2k-1 move 2k-2 steps ahead ) (2k move 2k-2 steps back)
1 2 ... 2k 2k-2
-> 2k-1 2k+1 2k+2 ... 4k-2 4k-1
(2k-1 down)
这个结论可以继续推广到m*n-puzzle(n为偶数):
定理二：对于m*n-puzzle(n为偶数,m>1), 如果一个排列可以通过移动某一排列中
的一个元素向前或者向后两个位置得到，且在这两个排列所对应的状态中空白
在第一行，这些状态可以相互转化.
这个定理比较好证，先把空格移下来，用完以后再移回去。
前面已经提了：所有逆序数为偶数的排列都可以通过若干次两位移动从排列
(1,2,3,...,n-1,n)中得到，而逆序数为齐数的排列都可以通过若干次两位移动
从排列(1,2,3,...,n)中得到。
于是我们又得到了以下引理：
对于m*n-puzzle(n为偶数,m>1)，空白在第一行且逆序数齐偶性相同的状态可以
相互转化。
实际上，空白在同一行的状态都有此种性质，所以我们得到下一个定理：
定理三：对于对于m*n-puzzle(n为偶数,m>1)，空白在同一行且逆序数齐偶性相同的
状态可以相互转化。
下面就是结论了，由定理三引出：
结论：对于对于m*n-puzzle(n为偶数,m>1)，逆序数与空白行数之和齐偶性相同的状态
可以相互转化。即：逆序数与空白行数之和为齐数的状态形成一个集合；逆序数
与空白行数之和为偶数的状态形成另一个集合。两个集合的状态数相等。任一
状态可以通过有限次移动达到同一集合的任一状态。不同集合的状态不能相互转化。 |
发表于 2007-9-14 23:08
| 
发表于 2007-9-15 08:45
| 
.
