发布时间 : 2024/7/16 13:47:20 星期二 文章9、回溯法求解哈密尔顿回路更新完毕开始阅读75e5ae290066f5335a812146

回溯法求解一般哈密顿尔回路

{

if(k>n-1 && c[x[k-1]][0]==1)

{ }

output(x); flag=1;

else

for(int i=k;i

swap(x[k],x[i]);

if ( c[x[k-1]][x[k]]==1)

hamilton(k+1);

swap(x[i],x[k]); }

}

2.2非递归回溯法求解哈密顿尔回路算法

2.2.1非递归回溯法求图的所有哈密顿尔回路算法

假定图G=(V, E)的顶点集为V={1, 2, ?, n}，则哈密顿回路的可能解表示为n元组X=(x1, x2, ?, xn)，其中，xi∈{1, 2, ?, n} ，并有如下约束条件：

(xi, xi+1)∈E (1≤i≤n－1) (xn, x1)∈E xi≠xj (1≤i, j≤n，i≠j) 由此可得以下算法：

1．将顶点数组x[n]初始化为0，标志数组visited[n]初始化为0； 2．k=1; visited[1]=1; x[1]=1; 从顶点1出发构造哈密顿回路；

2

回溯法求解一般哈密顿尔回路

3．while (k>=1)

3.1 x[k]=x[k]+1，搜索下一个顶点; 3.2 若(n个顶点没有被穷举) 执行下列操作

3.2.1 若(顶点x[k]不在哈密顿回路上&&(x[k-1],x[k])∈E)， 转步骤3.3;

3.2.2 否则，x[k]=x[k]+1，搜索下一个顶点；

3.3 若数组x[n]已形成哈密顿路径，则输出数组x[n]，算法结束； 3.4 否则，

3.4.1 若数组x[n]构成哈密顿路径的部分解， 则k=k+1，转步骤3；

3.4.2 否则，重置x[k]，k=k-1，取消顶点x[k]的访问标志， 转步骤3；

3 设计方案

3.1整体设计方案

这两个算法是通过C++语言编程实现的，在主菜单栏可以分成三块：1、递归求图的所有哈密顿回路2、非递归求图的所有哈密顿回路0、退出程序。

3.2 程序递归算法的主要代码

void hamilton(int k ) {//递归算法

if(k>n-1 && c[x[k-1]][0]==1)

{ }

output(x); flag=1;

else

for(int i=k;i

3

回溯法求解一般哈密顿尔回路

swap(x[k],x[i]);

if ( c[x[k-1]][x[k]]==1)

hamilton(k+1);

swap(x[i],x[k]); }

}

3.3程序非递归算法的主要代码

void hamilton(int n, int x[N], bool c[N][N]) {//非递归算法 int i, k;

bool*visited = new bool[n]; for(i =0; i

x[i] = 0;

visited[i] = false; }

visited[0]=1;

x[0]=0;//默认以第一个城市开始

k =1; //搜索解空间树（子集树形式）直接从第二层开始 while(k >=1) {

x[k]++;

while(x[k] < n)

if(visited[x[k]]==0 && c[x[k - 1]][x[k]]==1) break; else

x[k]++;

if(x[k]

4

回溯法求解一般哈密顿尔回路

for(k=0;k

{

cout<

}

cout<

else if (x[k]

visited[x[k]]=1;

k++; } else }

}

{

x[k]=0; k--;

visited[x[k]]=0;

}

3.4程序的其他函数

3.4.1输出函数主要代码 void output(int x[]) {//输出函数 }

5

for(int i=0;i

cout<

cout<