哈密尔顿回路问题.docx

哈密尔顿回路问题.docx

《哈密尔顿回路问题.docx》由会员分享，可在线阅读，更多相关《哈密尔顿回路问题.docx（4页珍藏版）》请在冰点文库上搜索。

哈密尔顿回路问题

哈密尔顿回路算法比拟一、贪心法贪心法通常用来解决具有最大值或最小值的优化问题。

通常从某一个初始状态出发，根据当前局部而非全局的最优决策，以满足约束方程为条件，以使得目标函数的值增加最快或最慢为准那么，选择一个最快地到达要求的输入元素，以便尽快地构成问题的可行解。

贪心法通过一系列选择得到问题的解。

其所做出的每一个选择都是当前状态下的局部最好选择，即贪心选择。

贪心法并不总能得到问题的最优解。

利用贪心法解哈密尔顿回路的C++算法如下：

#include"stdio.h"intG[8][8]={{0,2,8,1,9},{2,0,5,10,9},{8,5,0,5,3},{1,10,5,0,5},{9,9,3,5,0}};

structEdge{

//记录边的信息

intx;inty;intvalue;

//边的权值

};

typedefstructEdgeWeight;intT[5]={0};//用于标识节点是否被遍历过intP[6]={0};//存放路径intsum_value=0;//计算总路径长度Weightmin_value（intr）//找出当前节点具有最小权值的相邻边{inti,j=0,min;WeightW[5];//用于存放相邻边的信息for（i=0;i<5;i++）{if（（T[i]==0）&&（i!

=r））//当节点未被遍历且不是自己到自己{W[j].x=r;W[j].y=i;W[j].value=G[r][i];//记录相邻边的信息

j++;}}min=W[0].value;for（i=0;i

voidShortPath（）{

//寻找最短路径

inti,j,s=0;P[s]=0;//起始点设为V0Weightw_next;//存放路径上的下一结点for（i=1;i<5;i++）//有n个节点循环n次即可{

w_next=min_value（s）;//根据当前节点找出路径上的下一节点T[w_next.x]++;//标识参加路径中的节点T[w_next.y]++;sum_value+=w_next.value;P[i]=w_next.y;//记录参加路径的节点s=w_next.y;//推移当前节点}P[i]=0;//回到起始点sum_value+=G[s][0];printf（"无向图为:

\n"）;for（i=0;i<5;i++）{for（j=0;j<5;j++）printf（"%d",G[i][j]）;printf（"\n"）;

}printf（"\n用贪心算法求得的哈密顿回路为：

"）;for（i=0;i<6;i++）{printf（"V%d",P[i]）;if（i!

=5）printf（"->"）;}printf（"\n\n哈密顿回路的总路径长度为：

%d\n",sum_value）;}调试成功，如下列图所示：

时间复杂度为O（n2）二、贪心+分支限界分支限界法常以广度优先或以最小消耗〔最大效益〕优先的方式搜索问题的解空间树。

在分支限界法中，每一个活结点只有一次时机成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被参加活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所需的解或活结点表为空时为止。

#include"stdio.h"#include"stdlib.h"#definen5//结点个数为5#defineNoEdge99999//结点之间没有路径的标志

typedefintType;intG[n+1][n+1];//图的权值矩阵intS[n+1][n+1];//每个顶点的连接边按序排列放入此矩阵intVV[n+1];//存放在哈密尔顿回路上的顶点voidsort_adj（inti）//将各个顶点邻接的边按大小顺序存入{

S中

intj,p,m,k;Typetemp;for（j=1;j<=n;j++）{S[i][j]=j;}p=1;l1:

for（j=p,k=j+1;G[i][S[i][j]]<=G[i][k];j=k,k++）;

p=k;temp=G[i][k];m=k;while（（temp0））{S[i][j+1]=S[i][j];j--;}S[i][j+1]=m;if（p

intU[n+1];intV[n+1];TypeCmin;inti,j,l;sort_v（）;for（i=1;i<=n;i++）U[i]=0;U[1]=1;c=0;Cmin=NoEdge;l=1;V[1]=1;L0:

l++;j=0;L1:

j++;if（j>n）gotoL2;if（U[S[V[l-1]][j]]）gotoL1;U[S[V[l-1]][j]]=1;if（c+G[V[l-1]][S[V[l-1]][j]]>Cmin）gotoL1;c+=G[V[l-1]][S[V[l-1]][j]];V[l]=S[V[l-1]][j];if（l

l--;if（l>=2）{j=V[l];U[j]=0;

c-=G[V[l-1]][j];gotoL1;}elseif（Cmin!

=NoEdge）returnCmin;elsereturnNoEdge;}voidmain（）{inti;G[1][1]=NoEdge;G[1][2]=1;G[1][3]=3;G[1][4]=4;G[1][5]=10;G[2][1]=1;G[2][2]=NoEdge;G[2][3]=2;G[2][4]=2;G[2][5]=1;G[3][1]=3;G[3][2]=2;G[3][3]=NoEdge;G[3][4]=4;G[3][5]=1;G[4][1]=4;G[4][2]=2;G[4][3]=4;G[4][4]=NoEdge;G[4][5]=11;G[5][1]=10;G[5][2]=1;G[5][3]=1;G[5][4]=11;G[5][5]=NoEdge;if（BTSP（VV）!

=NoEdge）{

printf（"最优值为:

%d",BTSP（VV））;printf（"最优解为:

"）;for（i=1;i<=n;i++）printf（"%d-->",VV[i]）;printf（"1\n"）;}else{printf（"无回路"）;printf（"\n"）;}}调试成功:

时间复杂度为O〔n2〕。

三、回溯法回溯法是一种按照深度优先的策略从根结点开始搜索解空间树的算法，该算法既带有系统性又带有跳跃性，它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。

算法搜索至解空间树的任一节点时，总是先判定该节点是否肯定不包含问题的解，如果肯定不包含，那么跳过对以该节点为跟的子树的系统搜索，逐层向其祖先节点回溯。

否那么，进入该子树，继续按深度优先的策略进行探索。

这种以深度优先的方式系统地搜索问题的解的算法称为回溯法。

回溯法可以用来求出问题的全部解，也可以在求出问题的一个解之后停止对问题的求解，即只求该问题是否有解。

它适用于解一些组合数较大的问题。

利用回溯法解哈密尔顿回路存在性的C++算法如下：

#includeusingnamespacestd;boolroad[8][8]={{0,1,0,0,1,0,0,0},{1,0,1,0,0,0,1,0}

{0,1,0,1,0,1,0,0},{0,0,1,0,0,0,0,1},{1,0,0,0,0,1,0,0},{0,0,1,0,1,0,1,0},{0,1,0,0,0,1,0,1},{0,0,0,1,0,0,1,0}};intx[8]={0};voidHaMiTonian（int）;voidNextValue（int）;voiddisplay（）;intmain（）{x[0]=1;HaMiTonian

（1）;return0;}

voidHaMiTonian（int{

m）

if（m>7）return;NextValue（m）;if（x[m]==0）return;if（m==7&&road[0][x[7]-1]）display（）;

elseHaMiTonian（m+1）;

goto}

L;

void

NextValue（int

k）

{

intj;l:

x[k]=（x[k]+1）%9;if（x[k]==0）return;if（road[x[k-1]-1][x[k]-1]）{

for（j=0;j

void{

display（）

for（inti=0;i<8;i++）cout<

调试成功，如下列图：

时间复杂度为O（n）四、穷举法#include#include#include#definemin（a,b）（a）<（b）?

（a）:

（b）#defineV5intLength[V]={0};intD[V][V]={{0,6,4,5,8},

{6,0,3,2,7},{4,3,0,3,1},{5,2,3,0,2},{8,7,1,2,0}};structedge{intfromV;inttoV;intdist;voidset（intf,intt,intd）{fromV=f;toV=t;dist=d;}voidoperator=（constedge&e）{set（e.fromV,e.toV,e.dist）;}};staticintcomp（constvoid*e1,constvoid*e2）{if（（（edge*）e1）->dist<（（edge*）e2）->dist）return-1;elseif（（（edge*）e1）->dist==（（edge*）e2）->dist）return0;elsereturn1;}constintlen=16;intAsum=0;edgePath[V];edgeArrE[len];voidprintArrE（）{for（intp=0;p

printPath（）;for（inti=0;i

"）;printPath（）;exit（0）;}}#definex1000boolcheckDuplicate（intc）{intF[V]={x,x,x,x,x};intT[V]={x,x,x,x,x};for（inti=0;i

voidreplace（intc）{//replace"count"elementsatPath'stailprintPath（）;if（checkDuplicate（c））return;for（intk=V-c;k

时间复杂度为〔n!

〕