33,009
社区成员
发帖
与我相关
我的任务
分享组合数学的高手请帮忙一下...
问题描述：
给定一 6*6 棋盘，并有编号为1--35 共35个棋子。初始时，这些棋子随机地分布在各方格中，显然，还有一个方格为空。
现要求写一算法，将原始棋盘上的方格重新安排，以达到一个特定目标排列.
如果目标为：
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35
现在已排到：
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 35 34
下面该如何进行呢？
*---------------------
这样的目标能够达到吗? 可以不给出完整的数学证明,但要求结论要真实可信!
可以参看相关网页:
http://community.csdn.net/Expert/topic/4484/4484947.xml?temp=.7055017
给定一 6*6 棋盘，并有编号为1--35 共35个棋子。初始时，这些棋子随机地分布在各方格中，显然，还有一个方格为空。
现要求写一算法，将原始棋盘上的方格重新安排，以达到一个特定目标排列.
如果目标为：
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35
现在已排到：
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 35 34
下面该如何进行呢？
*---------------------
这样的目标能够达到吗? 可以不给出完整的数学证明,但要求结论要真实可信!
可以参看相关网页:
http://community.csdn.net/Expert/topic/4484/4484947.xml?temp=.7055017
...全文
请发表友善的回复…
发表回复
boodweb 2006-01-14
- 打赏
- 举报
找了些资料研究了一下，似乎证明并不是如mathe所说的构造法
做了个笔记，有兴趣的可以看看：
http://www.x2blog.cn/bood/3231.html
做了个笔记，有兴趣的可以看看：
http://www.x2blog.cn/bood/3231.html
tudou614 2006-01-13
- 打赏
- 举报
mk
daipeanut 2006-01-12
- 打赏
- 举报
对mathe()的佩服如滔滔江水
boodweb 2006-01-11
- 打赏
- 举报
to mathe:
提两个问题：
1. "如果目标状态和初始状态的逆序数的奇偶性相同,那么这个变化是可以存在的"
是不是必然存在呢？
2. "先将除了一个包含空格的2*3矩形位置的其他格子逐步调整好"
这个我没看懂...，是说先将包含空格的2*3矩阵以外的所有格子调整好么？这个调整很trivial么？
提两个问题：
1. "如果目标状态和初始状态的逆序数的奇偶性相同,那么这个变化是可以存在的"
是不是必然存在呢？
2. "先将除了一个包含空格的2*3矩形位置的其他格子逐步调整好"
这个我没看懂...，是说先将包含空格的2*3矩阵以外的所有格子调整好么？这个调整很trivial么？
mathe 2006-01-11
- 打赏
- 举报
1.是的,必然存在.
2.是比较trivial,如果空格在角上那更加简单
如果你觉得这种方法还麻烦,可以先找一个空格在角上的状态,这个状态逆序数的奇偶性同初始状态和目标状态都相同.
然后分别将初始状态和目标状态变换到那个状态的方法通过上面的方法找到.
然后先将初始状态变换到那个状态,在将目标状态变换到那个状态的过程逆过来,就可以变换到目标状态了.存在性就是这样通过构造法证明的
2.是比较trivial,如果空格在角上那更加简单
如果你觉得这种方法还麻烦,可以先找一个空格在角上的状态,这个状态逆序数的奇偶性同初始状态和目标状态都相同.
然后分别将初始状态和目标状态变换到那个状态的方法通过上面的方法找到.
然后先将初始状态变换到那个状态,在将目标状态变换到那个状态的过程逆过来,就可以变换到目标状态了.存在性就是这样通过构造法证明的
mathe 2006-01-09
- 打赏
- 举报
不需用用人工智能的方法，
我前面已经提到如何求一个解的方法，这也是人工玩这个游戏的方法：
至于找一个变化的方案,也很简单,先将除了一个包含空格的2*3矩形位置的其他格子逐步调整好,最后就成为一个2*3矩阵的调整问题了,总共就没有几种情况,穷举就可以了
我前面已经提到如何求一个解的方法，这也是人工玩这个游戏的方法：
至于找一个变化的方案,也很简单,先将除了一个包含空格的2*3矩形位置的其他格子逐步调整好,最后就成为一个2*3矩阵的调整问题了,总共就没有几种情况,穷举就可以了
quicksoftxyz 2006-01-07
- 打赏
- 举报
这可以用人工智能的A*算法，这个算法本质上也就是优先队列式的分枝限界法。
这个算法的完整源码本人已完成。因代码较长，发布不方便，需要的可以给我发邮件。
quicksoftxyz@yahoo.com.cn
这个算法的完整源码本人已完成。因代码较长，发布不方便，需要的可以给我发邮件。
quicksoftxyz@yahoo.com.cn
wvins 2006-01-07
- 打赏
- 举报
“如果目标状态和初始状态的逆序数的奇偶性相同,那么这个变化是可以存在的”
//-----------------------------------------------------------------------
对mathe()的佩服如滔滔江水
如果要解呢？
有何高招？
//-----------------------------------------------------------------------
对mathe()的佩服如滔滔江水
如果要解呢？
有何高招？
mathe 2006-01-06
- 打赏
- 举报
现在我们可以将36个数看成一个数列
a1,a2,a3,...,a36
对于其中任意一对数ai,aj
如果i<j, ai>aj,我们称这样的数为一对逆序
而一个数列所有逆序的数目称为这个数列的逆序数.
有下面的定理:
对于任意一个数字全不相等的数列,任意交换数列中两个数,将改变数列逆序数的奇偶性.
所以我们能够看出,数列
1,2,3,....,33,34,35,36
是无法通过偶数次交换变化到数列
1,2,3,....,33,35,34,36
的
所以上面情况的变化肯定无法达到.
更加进一步的证明可以得到,对于任意m*n的矩阵(m,n>1),在我们将空格用一个更大的数字替换后,如果目标状态和初始状态的逆序数的奇偶性相同,那么这个变化是可以存在的,不然,这样的变化是不存在的.
至于找一个变化的方案,也很简单,先将除了一个包含空格的2*3矩形位置的其他格子逐步调整好,最后就称为一个2*3矩阵的调整问题了,总共就没有几种情况,穷举就可以了
a1,a2,a3,...,a36
对于其中任意一对数ai,aj
如果i<j, ai>aj,我们称这样的数为一对逆序
而一个数列所有逆序的数目称为这个数列的逆序数.
有下面的定理:
对于任意一个数字全不相等的数列,任意交换数列中两个数,将改变数列逆序数的奇偶性.
所以我们能够看出,数列
1,2,3,....,33,34,35,36
是无法通过偶数次交换变化到数列
1,2,3,....,33,35,34,36
的
所以上面情况的变化肯定无法达到.
更加进一步的证明可以得到,对于任意m*n的矩阵(m,n>1),在我们将空格用一个更大的数字替换后,如果目标状态和初始状态的逆序数的奇偶性相同,那么这个变化是可以存在的,不然,这样的变化是不存在的.
至于找一个变化的方案,也很简单,先将除了一个包含空格的2*3矩形位置的其他格子逐步调整好,最后就称为一个2*3矩阵的调整问题了,总共就没有几种情况,穷举就可以了
mathe 2006-01-06
- 打赏
- 举报
这是一个群论问题.
我们知道,每次交换都是将空格移动到一个相邻的格子,可以看出,在上面过程中,空格返回原先的位置,容易证明,总共移动的次数必然为偶数次(将所有格子用黑白两色染色,黑白相间,每次总是将空格从黑格移动到白格,白格移动到黑格,所以从白格移动到白格必然移动偶数次).
然后我们现在将空格用数字36来替换,现在允许每次任意交换两个数字,但是必须交换偶数次,我们证明在这种情况下无法达到目的就可以了,这是群论中标准的问题
我们知道,每次交换都是将空格移动到一个相邻的格子,可以看出,在上面过程中,空格返回原先的位置,容易证明,总共移动的次数必然为偶数次(将所有格子用黑白两色染色,黑白相间,每次总是将空格从黑格移动到白格,白格移动到黑格,所以从白格移动到白格必然移动偶数次).
然后我们现在将空格用数字36来替换,现在允许每次任意交换两个数字,但是必须交换偶数次,我们证明在这种情况下无法达到目的就可以了,这是群论中标准的问题
