当前在线人数15589
首页 - 分类讨论区 - 电脑网络 - 葵花宝典版 -阅读文章
未名交友
[更多]
[更多]
文章阅读:偶三年多前写的东东 Re: 8-puzzle
[同主题阅读] [版面: 葵花宝典] [作者:antelope] , 2005年02月03日18:47:17
antelope
进入未名形象秀
我的博客
[上篇] [下篇] [同主题上篇] [同主题下篇]

发信人: antelope (虽碎岁随), 信区: Programming
标  题: 偶三年多前写的东东 Re: 8-puzzle
发信站: Unknown Space - 未名空间 (Thu Feb  3 18:49:32 2005), 转信

发信人: glider (sui sui), 信区: Algorithm
标  题: 小小总结一把 Re: 再来一题
发信站: 南京大学小百合站 (Thu Aug  9 07:52:45 2001), 站内信件

   100多年前有一位同学不知怎么想的就发明了15-puzzle,但是这个游戏得到风靡
的一个原因是这位给出了1000元的奖金,悬赏第一个成功将一个状态移到目标状态
的智者。结果没有人能够拿到这笔巨款,因为这个问题无解,除非耍赖。

    后来呢,就有人发现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以上,

   各位老大,如何证明同一状态集的状态可以在有限步内相互转化?大家讨论一下吧。

发信人: glider (sui sui), 信区: Algorithm
标  题: 又进一步 Re: 小小总结一把 Re: 再来一题
发信站: 南京大学小百合站 (Thu Aug  9 14:09:40 2001), 站内信件

只证出来了一半:

对于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)中得到。这个可以用数学归纳法证明,比较简单。
我看的证明网址是 http://kevingong.com/Math/SixteenPuzzle.html
不过很多步只给出了引理,没有证明。


n为偶数的情况比较复杂,争取今天搞定。

发信人: glider (sui sui), 信区: Algorithm
标  题: 成功搞定 Re: 小小总结一把 Re: 再来一题
发信站: 南京大学小百合站 (Fri Aug 10 09:53:37 2001), 站内信件

终于证出来了另一半,不过可能繁琐些。

定理一:如果相邻行有空格,经过有限次移动,一行中任意元素可以跳到与其相距为
二的同一行位置。

这个定理在前面已经证明了。一个推论就是该元素可以向前或向后移动偶数个位置。

下面观察一个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),逆序数与空白行数之和齐偶性相同的状态
可以相互转化。即:逆序数与空白行数之和为齐数的状态形成一个集合;逆序数
与空白行数之和为偶数的状态形成另一个集合。两个集合的状态数相等。任一
状态可以通过有限次移动达到同一集合的任一状态。不同集合的状态不能相互转化。



说明:
15-puzzle在学术界出现可以溯源到1879年的一篇论文,偶倒是找到了,不过这100多年前
的“古董”比较晦涩。可能其早就证明了以上的结论。




--
                          爱琴海 -- Aegean Sea

※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 68.149.]

[上篇] [下篇] [同主题上篇] [同主题下篇]
[转寄] [转贴] [回信给作者] [修改文章] [删除文章] [同主题阅读] [从此处展开] [返回版面] [快速返回] [收藏] [举报]
 
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996