加载中…
正文 字体大小:

八数码问题有解的条件及其推广

(2011-09-14 23:43:58)
标签:

杂谈

分类: 搜索

>从八数码问题入手

我们首先从经典的八数码问题入手,即对于八数码问题的任意一个排列是否有解?有解的条件是什么?

我在网上搜了半天,找到一个十分简洁的结论。八数码问题原始状态如下:

1 2 3
4 5 6
7 8

为了方便讨论,我们把它写成一维的形式,并以0代替空格位置。那么表示如下:

1 2 3 4 5 6 7 8 0

通过实验得知,以下状态是无解的(交换了前两个数字1 2):

2 1 3 4 5 6 7 8 0

八数码问题的有解无解的结论:

一个状态表示成一维的形式,求出除0之外所有数字的逆序数之和,也就是每个数字前面比它大的数字的个数的和,称为这个状态的逆序。

若两个状态的逆序奇偶性相同,则可相互到达,否则不可相互到达。

由于原始状态的逆序为0(偶数),则逆序为偶数的状态有解。

也就是说,逆序的奇偶将所有的状态分为了两个等价类,同一个等价类中的状态都可相互到达。

简要说明一下:当左右移动空格时,逆序不变。当上下移动空格时,相当于将一个数字向前(或向后)移动两格,跳过的这两个数字要么都比它大(小),逆序可能±2;要么一个较大一个较小,逆序不变。所以可得结论:只要是相互可达的两个状态,它们的逆序奇偶性相同。我想半天只能说明这个结论的必要性,详细的证明请参考后面的附件。

 

>推广二维N×N的棋盘 (poj 2893)

我们先来看看4×4的情况,同样的思路,我们考虑移动空格时逆序的变化情况。

  2      4
      7    8
      C
     

我们用字母A~F代替数字10~15。同样地,当左右移动的时候,状态的逆序不改变。而当上下移动的时候,相当于一个数字跨过了另外三个格子,它的逆序可能±3或±1,逆序的奇偶性必然改变。那么又该如何

  2      4
      7    8
      
       

可以证明,以上状态是一个无解的状态(将C移到了第四行)。该状态的逆序为0,和原始状态相同,但是它的空格位置在第三行。若将空格移到第四行,必然使得它的逆序±1或±3,奇偶性必然改变。所以它是一个无解的状态。

然而以下状态就是一个有解的状态(交换了前两个数字1 2):

        4
        8
      
       F

这个状态的逆序为1,和原始状态奇偶性不同,而空格位置在第三行。由于空格每从第三行移动到第四行,奇偶性改变。则该状态的可到达原始状态。

通过观察,得出以下结论:

N×N的棋盘,N为奇数时,与八数码问题相同。

N为偶数时,空格每上下移动一次,奇偶性改变。称空格位置所在的到目标空格所在的行步数为空格的距离(不计左右距离),若两个状态的可相互到达,则有,两个状态的逆序奇偶性相同且空格距离为偶数,或者,逆序奇偶性不同且空格距离为奇数数。否则不能。

也就是说,当此表达式成立时,两个状态可相互到达:(状态1的逆序数 + 空格距离)的奇偶性==状态2奇偶性。

另外再详细说明一下,无论N是奇数还是偶数,空格上下移动,相当于跨过N-1个格子。那么逆序的改变可能为一下值±N-1,±N-3,±N-5 …… ±N-2k-1。当N为奇数数时N-1为偶数,逆序改变可能为0;当N为偶数时N-1为奇数,逆序的改变不能为0,只能是奇数,所以没上下移动一次奇偶性必然改变。

 

>推广到三维N×N×N   ( zju 2004 )

其实,三维的结论和二维的结论是一样的。

考虑左右移动空格,逆序不变;同一层上下移动空格,跨过N-1个格子;上下层移动空格,跨过N^2-1个格子。

当N为奇数时,N-1和N^2-1均为偶数,也就是任意移动空格逆序奇偶性不变。那么逆序奇偶性相同的两个状态可相互到达。

当N为偶数时,N-1和N^2-1均为奇数,也就是令空格位置到目标状态空格位置的y z方向的距离之和,称为空格距离。若空格距离为偶数,两个逆序奇偶性相同的状态可相互到达;若空格距离为奇数,两个逆序奇偶性不同的状态可相互到达。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有