哈密尔顿回路问题.docx
- 文档编号:12747412
- 上传时间:2023-06-07
- 格式:DOCX
- 页数:18
- 大小:97.52KB
哈密尔顿回路问题.docx
《哈密尔顿回路问题.docx》由会员分享,可在线阅读,更多相关《哈密尔顿回路问题.docx(18页珍藏版)》请在冰点文库上搜索。
哈密尔顿回路问题
哈密尔顿回路算法比较
一、贪心法
贪心法通常用来解决具有最大值或最小值的优化问题。
通常从某一个初始状态出发,根据当前局部而非全局的最优决策,以满足约束方程为条件,以使得目标函数的值增加最快或最慢为准则,选择一个最快地达到要求的输入元素,以便尽快地构成问题的可行解。
贪心法通过一系列选择得到问题的解。
其所做出的每一个选择都是当前状态下的局部最好选择,即贪心选择。
贪心法并不总能得到问题的最优解。
利用贪心法解哈密尔顿回路的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 { if(W[i+1].value { W[0].x=W[i+1].x; W[0].y=W[i+1].y; W[0].value=W[i+1].value; } } returnW[0]; } voidShortPath()//寻找最短路径 { inti,j,s=0; P[s]=0;//起始点设为V0 Weightw_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((temp { S[i][j+1]=S[i][j]; j--; } S[i][j+1]=m; if(p gotol1; } voidsort_v()//对各顶点调用sort_adj()方法 { inti; for(i=1;i<=n;i++) sort_adj(i); } TypeBTSP(intvv[]) { Typec; 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 gotoL0; if(c+G[S[V[l-1]][j]][1] { for(i=1;i<=n;i++) VV[i]=V[i]; Cmin=c+G[S[V[l-1]][j]][1]; } l++; L2: 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++算法如下: #include usingnamespacestd; 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(intm) { if(m>7)return; L: NextValue(m); if(x[m]==0) return; if(m==7&&road[0][x[7]-1]) display(); else HaMiTonian(m+1); gotoL; } voidNextValue(intk) { 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 if(x[j]==x[k])gotol; return; } elsegotol; } voiddisplay() { for(inti=0;i<8;i++) cout< cout< } 调试成功,如下图: 时间复杂度为O(n) 四、穷举法 #include #include #include #definemin(a,b)(a)<(b)? (a): (b) #defineV5 intLength[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 printf("[%d,%d]=%d,",ArrE[p].fromV,ArrE[p].toV,ArrE[p].dist); } printf("\n"); } voidprintPath(){ for(intp=0;p printf("[%d,%d]=%d,",Path[p].fromV,Path[p].toV,Path[p].dist); } printf("\n"); } voidcheckResult(){ printPath(); for(inti=0;i for(intj=i+1;j if(Path[i].fromV==Path[j].toV&&Path[i].toV==Path[j].fromV)return; } } intsum[V]={0}; for(ints=0;s sum[Path[s].fromV]++; sum[Path[s].toV]++; } if(sum[0]==2&&sum[1]==2&&sum[2]==2&&sum[3]==2&&sum[4]==2){ printf("Thebestpathis: "); printPath(); exit(0); } } #definex1000 boolcheckDuplicate(intc){ intF[V]={x,x,x,x,x}; intT[V]={x,x,x,x,x}; for(inti=0;i intj=0; do{ if(Path[i].fromV==F[j]||Path[i].toV==T[j]){ returntrue; } else{ F[j]=Path[i].fromV; T[j]=Path[i].toV; break; } ++j; }while(j<=i); } returnfalse; } voidreplace(intc){//replace"count"elementsatPath'stail printPath(); if(checkDuplicate(c))return; for(intk=V-c;k if(c==0){ checkResult(); return; } intstart=V-c; for(inti=start+1;i Path[start]=ArrE[i]; replace(c-1); } } intmain(){ inttmp=V-1; while(tmp){ Asum+=tmp; --tmp; }//Forasolution,from/tovertexsummaryshouldbeAsum printf("Asum=%d\n",Asum); intidx=0; for(intr=0;r for(intc=0;c if(r==c)continue; ArrE[idx++].set(r,c,D[r][c]); } } qsort(ArrE,len,sizeof(edge),comp); printArrE(); for(inti=0;i memcpy(Path,ArrE,sizeof(edge)*V); replace(i); } printf("Nocirclefound\n"); return0; } 调试成功,如下图: 时间复杂度为(n! )
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈密尔顿 回路 问题