八数码从初始状态到目标状态是否有解问题
http://blog.csdn.net/tiaotiaoyly/article/details/2008233
?
为了方便讨论,我们把它写成一维的形式,并以0代替空格位置。那么表示如下:
1 2 3 4 5 6 7 8 0
通过实验得知,以下状态是无解的(交换了前两个数字1 2):
2 1 3 4 5 6 7 8 0
八数码问题的有解无解的结论:
一个状态表示成一维的形式,求出除0之外所有数字的逆序数之和,也就是每个数字前面比它大的数字的个数的和,称为这个状态的逆序。
若两个状态的逆序奇偶性相同,则可相互到达,否则不可相互到达。
由于原始状态的逆序为0(偶数),则逆序为偶数的状态有解。
也就是说,逆序的奇偶将所有的状态分为了两个等价类,同一个等价类中的状态都可相互到达。
简要说明一下:当左右移动空格时,逆序不变。当上下移动空格时,相当于将一个数字向前(或向后)移动两格,跳过的这两个数字要么都比它大(小),逆序可能±2;要么一个较大一个较小,逆序不变。所以可得结论:只要是相互可达的两个状态,它们的逆序奇偶性相同。我想半天只能说明这个结论的必要性,详细的证明请参考后面的附件。