谁能给我相关的资料和算法

0 0

谁能给我相关的资料和算法30

亚瑟王打算请150明骑士参加宴会，但是有些骑士相互之间会有口角，而亚瑟王知道谁和谁不和。亚瑟王希望能让他的客人围着一张圆桌坐下，而所有不和的骑士相互之间不会挨着坐。回答下列问题：
1.哪一个经典问题能够作为亚瑟王问题的模型？
2.请证明，如果与每一个骑士不和的人数不超过75，则该问题有解。
3.设计回溯算法求解亚瑟王问题。

数据结构

2014年5月27日 20:43

Still_Java
0
0 0 3

1.哪一个经典问题能够作为亚瑟王问题的模型？
   个人认为应该是8皇后问题（如果不知道什么是8皇后问题的话google下）
   共同之处在于摆放N个位置，N个位置需要满足一定的条件，只不过皇后的攻击条件是固定的，而骑士的条件是一个矩阵中获得，但是算法实际上是相同的。

2.请证明，如果与每一个骑士不和的人数不超过75，则该问题有解。
    可以使用数学归纳法证明：假定N为骑士的个数，在N大于等于2的情况下，如果任意一个骑士不和的人数小于N/2（奇数情况下取地板运算）的情况下，都是有解的，方式如下：
    N = 2的及N=3的情况下，冲突的个数小于1，因此命题整理（没有冲突，当然随意摆放了）；
    假设N=K的情况下成立，现在证明N=K+1时成立：
    从K+1个骑士中拿掉一人X，试图让K个人先坐下，这时显然是有解的（依据假设）
    对于X，由于与X冲突的人数小于N/2, 因此一定可以找到一个位置i, 使得骑士i和骑士i+1都不与X冲突（否则任意相邻的两个人至少有一个人与X冲突的话，与X冲突的人数将会> N>2），这时将X置于i与i+1中间，证明完毕。

3.设计回溯算法求解亚瑟王问题。
    既然是8皇后问题是相近的，使用8皇后问题的解法即可，略。

2014年5月28日 14:51

鳄鱼旭
248
0 0 17