哈密尔顿回路问题

《哈密尔顿回路问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、哈密尔顿回路算法比较一、贪心法贪心法通常用来解决具有最大值或最小值的优化问题。通常从某一个初始状态出发，根据当前局部而非全局的最优决策，以满足约束方程为条件，以使得目标函数的值增加最快或最慢为准则，选择一个最快地达到要求的输入元素，以便尽快地构成问题的可行解。贪心法通过一系列选择得到问题的解。其所做出的每一个选择都是当前状态下的局部最好选择，即贪心选择。贪心法并不总能得到问题的最优解。利用贪心法解哈密尔顿回路的C++算法如下：#include"stdio.h"intG[8][8]={{0,2,8,1,9},{2,0,5,1

2、0,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

3、;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

4、短路径{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

5、];printf("无向图为:");for(i=0;i<5;i++){for(j=0;j<5;j++)printf("%d",G[i][j]);printf("");}printf("用贪心算法求得的哈密顿回路为：");for(i=0;i<6;i++){printf("V%d",P[i]);if(i!=5)printf("->");}printf("哈密顿回路的总路径长度为：%d",sum_value);}调试成功，如下图所示：时间复杂度为O(n2)二、贪心+分支限界分支限界法常以广度优先或以最小耗

6、费（最大效益）优先的方式搜索问题的解空间树。　　在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。#include"stdio.h"#include"stdlib.h"#definen5//结点个数为5#defineNoEdge99999//结点之间没有路径

7、的标志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;w

8、hile((temp0)){S[i][j+1]=S[i][j];j--;}S[i][j+1]=m;if(p