哈密顿回路问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
的回溯算法
? 哈密顿回路问题:
? 解空间:
A={ (x, x, …, x)| x=1, 2<= x<=n, i= 2, …, n} 12n1i
其中～x, x, …, xn
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示G中的顶点序列。 12
? 解的约束条件:,设图G用邻接矩阵graph表示,
(x, x, …, x)为哈密顿回路当且仅当 12n
graph[x, x]=1, k=2, 3, …, n 且grapg[x, x]=1k-1kn1且x?x (i?j) ij
? 回溯算法:
设置一个标记数组tag[1..n]表示顶点是否
在当前生成的路径上:
tag[i]=1, 顶点i在当前路径上
tag[i]=0, 顶点i不在当前路径上
注意:当一个顶点退出当前路径时～该顶点的标记应复原为0。
算法 HAMILTONIAN
输入:正整数n和含n个顶点的连通图G的邻接矩阵graph。
输出:图G的所有哈密顿回路, 若无哈密顿回路则输出no solution。
x[1]=1 ; x[2..n]=0 //用x[1..n]表示搜索路径, 从顶点1开始。
tag[1]=1; for i=2 to n tag[i]=0 //设顶点标记初值。
flag=hamilton( 2 )
if not flag then output “no solution” //输出无解
end HAMILTONIAN
过程 hamilton(k)
//在已得到当前路径x[1..k-1]的情况下～求图G
的所有哈密
//顿回路并输出～有解则返回true, 否则返回f
alse。
t=false //用t标志是否有解。
for i=2 to n
x[k]=i //试将顶点i作为当前路径上的第k个顶点。
if route(k) then //当前顶点可作为当前路径的下一顶点。
tag[x[k]]=1 //当前顶点加入当前路径。
if k=n then //找到一条哈密顿回路。
t=true,output x[1..n] //输出当前找
到的哈密顿回路。
else //x[1..k]是部分路径。
t1= hamilton (k+1) //递归求后面所
有的哈密顿回路
if t1 then t=true
end if
tag[x[k]]=0 //顶点x[k]退出当前路径。
end if
end for
return t
end hamilton
过程 route(k)
//判断当前顶点x[k]是否可作为当前路径x
[1..k-1]的下一顶点, //是则返回true, 否则返
回false。
if (graph[x[k-1], x[k]]=1)and
(tag[x[k]]=0)and(k
本文档为【哈密顿回路问题的回溯算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483