题目：亚瑟王打算请150明骑士参加宴会，但是有些骑士相互之间会有口角，而亚瑟王知道谁和谁不和。亚瑟王希望能让他的客人围着一张圆桌坐下，而所有不和的骑士相互之间不会挨着坐。回答下列问题：
1. 哪一个经典问题能够作为亚瑟王问题的模型？
2. 请证明，如果与每一个骑士不和的人数不超过75，则该问题有解。
3. 设计回溯算法求解亚瑟王问题。
解：
1、应用哈密顿模型来求解此问题
2、应该于每一个骑士不和的人数不超过74人，才有解，我们这里把自己和自己不和也算一个人，于是有了下面的分析模型；
3、分析如下：（简化模型，假设只有10个人，每个人和其它5人不和, 这里不和的人数可以自定义不一定是五个人）
const int n = 10;
int arc[n][n] = {
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{1,1,1,1,1,0,0,0,0,0}, 具体的C 实现程序如下：
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0}
};
#include
#define N 20
const int n = 10;
int arc[n][n] = {
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0}
};
void Hamiton(int x[ ], int n);
int main()
{
int x[n];
Hamiton(x, n) ;
return 0;
}
void Hamiton(int x[ ], int n)
{
int i, k;
int visited[N]; //假设图最多有N 个顶点
for (i = 0; i
x[i] = 0;
visited[i] = 0;
}
x[0] = 0; visited[0] = 1; //从顶点0出发
k = 1;
while (k >= 1)
{
x[k] = x[k] + 1; //搜索下一顶点
while (x[k]
{
if (visited[x[k]] == 0 && arc[x[k-1]][x[k]] == 1) break;
else x[k] = x[k] + 1;
}
if (x[k]
for (k = 0; k
cout
画出分析模型无向图
如下图所示（搜索是从点1开始的）
由于篇幅问题，这个例题解的哈密顿回路的搜索空间树请参考P185的示例
题目：亚瑟王打算请150明骑士参加宴会，但是有些骑士相互之间会有口角，而亚瑟王知道谁和谁不和。亚瑟王希望能让他的客人围着一张圆桌坐下，而所有不和的骑士相互之间不会挨着坐。回答下列问题：
1. 哪一个经典问题能够作为亚瑟王问题的模型？
2. 请证明，如果与每一个骑士不和的人数不超过75，则该问题有解。
3. 设计回溯算法求解亚瑟王问题。
解：
1、应用哈密顿模型来求解此问题
2、应该于每一个骑士不和的人数不超过74人，才有解，我们这里把自己和自己不和也算一个人，于是有了下面的分析模型；
3、分析如下：（简化模型，假设只有10个人，每个人和其它5人不和, 这里不和的人数可以自定义不一定是五个人）
const int n = 10;
int arc[n][n] = {
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{1,1,1,1,1,0,0,0,0,0}, 具体的C 实现程序如下：
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0}
};
#include
#define N 20
const int n = 10;
int arc[n][n] = {
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1},
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0},
{1,1,1,1,1,0,0,0,0,0}
};
void Hamiton(int x[ ], int n);
int main()
{
int x[n];
Hamiton(x, n) ;
return 0;
}
void Hamiton(int x[ ], int n)
{
int i, k;
int visited[N]; //假设图最多有N 个顶点
for (i = 0; i
x[i] = 0;
visited[i] = 0;
}
x[0] = 0; visited[0] = 1; //从顶点0出发
k = 1;
while (k >= 1)
{
x[k] = x[k] + 1; //搜索下一顶点
while (x[k]
{
if (visited[x[k]] == 0 && arc[x[k-1]][x[k]] == 1) break;
else x[k] = x[k] + 1;
}
if (x[k]
for (k = 0; k
cout
画出分析模型无向图
如下图所示（搜索是从点1开始的）
由于篇幅问题，这个例题解的哈密顿回路的搜索空间树请参考P185的示例