哈密尔顿回路问题.docx
《哈密尔顿回路问题.docx》由会员分享，可在线阅读，更多相关《哈密尔顿回路问题.docx（11页珍藏版）》请在冰点文库上搜索。
哈密尔顿回路问题
海南大学硕士研究生2010—2011学年度第一学期
算法设计与分析课程考试论文
学院（中心、所）：
信息科学技术学院专业：
计算机应用技术
研究方向班级
学生姓名王磊学生证号10081203210008
课程名称：
算法设计与分析
论文题目：
哈密尔顿回路问题
任课老师：
钟声
（以上由学生填写）
教师评阅：
阅卷教师（签名）：
年月日
哈密尔顿回路问题
一前言
1857年，英国数学家汉密尔顿（Hamilton）提出了著名的汉密尔顿回路问题，其后，该问题进一步被发展成为所谓的“货郎担问题”，即赋权汉密尔顿回路最小化问题：
这两个问题成为数学史上著名的难题。
所谓赋权汉密尔顿回路最小化问题是指，给定n个点及n个点两两之间的距离（或权数），求一条回路，使之经过所有的点，且经过每个点仅一次，而整条回路（也称路径或边界）的总距离（或总权数）最小。
理论上讲，这一问题总是可以通过枚举法求出其解的，但由于枚举法的计算量过大，达到（n－1）!
的数量级，因而，不是可行的方法。
二哈密尔顿回路问题的最优解
回朔法求解哈密尔顿回路的最优解：
有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。
这种方法适用于解一些组合数相当大的问题。
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。
如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
2.1思想
本问题采用回溯法求解最优解：
回溯法求解：
首先把回路中的所有顶点的编号初始化为0，然后，把顶点1当作回路中的第1个顶点，即x0=1，搜索与1邻接的编号最小的顶点，作为它的后续顶点，判断是否满足约束条件，是则到达该顶点，x1取值为满足条件的顶点编号。
然后再同样的方式搜索下面的顶点。
依次继续下去。
假设在搜索过程中已经生成了通路l=x0x1,…,xi-1，在继续搜索某个顶点作为通路中的xi顶点时，根据约束条件，在V中选择与xi-1邻接的并且不属于l的编号最小的顶点。
如果搜索成功，则把该顶点作为通路中的顶点xi，然后继续搜索通路中的下一个顶点。
如果搜索失败，就把l中的xi-1删去（回溯），从xi-1的顶点编号加1的位置开始，继续搜索与xi-2相邻接的且不属于l的编号最小的顶点。
这个过程一直继续下去。
当搜索到l中的顶点xn-1时，如果xn-1与x0相邻接，就得到了一条哈密尔顿回路；否则，把l中的顶点xn-1删去，继续回溯。
最后，在回溯过程中，l中只剩下一个顶点x0，则表明图不存在哈密尔顿回路。
2.2回溯算法
boolean[]s;//记录n个顶点的使用与否
//初始化解向量x[]，使用向量s[]
for（inti=0;ix[i]=-1;//x[]记录路径
s[i]=false;
}
s[0]=true;
x[0]=0;//从序号为0的顶点开始搜索
intk=1;//初始深度是1，因为有n个结点，且第一个结点已给出（k=0），故空间搜索树深度为n-1（1至n-1）
while（k>=0）{
x[k]=x[k]+1;//搜索下一个顶点编号
while（x[k]if（（!
s[x[k]]）&&（c[x[k-1]][x[k]]==1））{//如果顶点x[k]未被使用，而且与前一结点x[k-1]之间有连线~
break;
}else
x[k]=x[k]+1;//否则寻找下一个顶点
}
if（（x[k]=n-1））{//搜索成功,深度加1
s[x[k]]=true;
k=k+1;
}elseif（（x[k]break;
}else{//搜索失败，回溯到前一结点，并将原结点复位
x[k]=-1;
k=k-1;
s[x[k]]=false;
}
}
算法效率：
O（n!
）
2.2源代码
//哈密尔顿回路问题/
publicclassHamilton{
//图中顶点个数为n，图的邻接矩阵为c[][]，存放回路的顶点序号x[]，在这里，n个顶点的标号是:
0，1，2，...，n-1
publicvoidhamilton（intn,intx[],intc[][]）{
boolean[]s=newboolean[n];//记录n个顶点的使用与否
//初始化解向量x[]，使用向量s[]
for（inti=0;ix[i]=-1;
s[i]=false;
}
s[0]=true;
x[0]=0;//从序号为0的顶点开始搜索
intk=1;//初始深度是1，因为有n个结点，且第一个结点已给出（k=0），故空间搜索树深度为n-1（1至n-1）
while（k>=0）{
x[k]=x[k]+1;//搜索下一个顶点编号
while（x[k]if（（!
s[x[k]]）&&（c[x[k-1]][x[k]]==1））{//如果顶点x[k]未被使用，而且与前一结点x[k-1]之间有连线~
break;
}else
x[k]=x[k]+1;//否则寻找下一个顶点
}
if（（x[k]=n-1））{//搜索成功,深度加1
s[x[k]]=true;
k=k+1;
}elseif（（x[k]break;
}else{//搜索失败，回溯到前一结点，并将原结点复位
x[k]=-1;
k=k-1;
s[x[k]]=false;
}
}
}
publicstaticvoidmain（Stringargs[]）{
Hamiltonhl=newHamilton（）;
intc[][]={{1,1,1,0,1,0},{1,1,1,1,0,0},
{1,1,1,1,1,1},{0,1,1,1,0,1},
{1,0,1,0,1,1},{0,0,1,1,1,1}};
intn=6;//6个顶点
intx[]=newint[n];
hl.hamilton（n,x,c）;
System.out.println（"哈密尔顿回路是：
"）;
for（inti=0;iSystem.out.println（"x["+i+"]="+x[i]）;
}
}
运行结果为：
哈密尔顿回路是：
0，1，2，3，5，4，
三哈密尔顿回路问题的近似解
贪心算法求解哈密尔顿回路的近似解:
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。
也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心法求解哈密尔顿回路的策略：
从任意结点出发，每次在没有到过的结点中选择最近的一个，求一条回路，使之经过所有的点，且经过每个点仅一次，而整条回路（也称路径或边界）的总距离（或总权数）最小。
3.1算法
P={};//对应解集合S
V=V-{u0};u=u0;//从顶点u0出发
循环直到集合P中包含n-1条边
找与顶点u邻接的最小代价边（u,v）,并且v属于集合V；
P=P+{（u,v）};
V=V-{v};
u=v;//从顶点v出发继续求解
时间复杂度：
时间性能为O（n^2），因为共进行n-1次贪心选择，每一次选择都需要查找满足贪心条件的最短边。
3.2源程序
importjava.util.ArrayList;
importjava.util.Date;
importjava.util.List;
importjava.util.Scanner;
publicclassHamilton{
staticint[][]citys=null;
publicstaticintgettheFirst（intdistance[]）{
intminNum=distance[1];
inttheDingDian=1;
for（inti=1;iif（distance[i]{
minNum=distance[i];
theDingDian=i;
}
}
returntheDingDian;//返回输入数所在阶乘数的最小整数
}
publicstaticvoidmain（String[]args）{
intn=5;
int[]initDistance=newint[n];
citys=newint[n][n];
citys[0][0]=0;
citys[0][1]=3;
citys[0][2]=3;
citys[0][3]=2;
citys[0][4]=6;
citys[1][0]=3;
citys[1][1]=0;
citys[1][2]=7;
citys[1][3]=3;
citys[1][4]=1;
citys[2][0]=3;
citys[2][1]=7;
citys[2][2]=0;
citys[2][3]=2;
citys[2][4]=5;
citys[3][0]=2;
citys[3][1]=3;
citys[3][2]=4;
citys[3][3]=0;
citys[3][4]=3;
citys[4][0]=6;
citys[4][1]=2;
citys[4][2]=5;
citys[4][3]=3;
citys[4][4]=0;
int[]part=newint[3];
part[0]=1;
part[1]=2;
part[2]=1;
intresult[]=part;
intflag=2;
while（flagresult=getResult（result,n）;
flag++;
}
System.out.print（"哈密尔顿回路：
"）;
for（inti=0;iSystem.out.print（result[i]+","）;
}
}
privatestaticint[]getResult（int[]result,intn）{
//TODOAuto-generatedmethodstub
intlength=result.length;//要插入的数据
int[]partresult=newint[length+1];
partresult=gettheBestArray（result,length）;
returnpartresult;
}
privatestaticint[]gettheBestArray（int[]part,intlength）{
//TODOAuto-generatedmethodstub
int[]bestresult=newint[length];
ListmidList=newArrayList（）;
for（inti=1;iint[]partresult=newint[length+1];
for（intj=0;jpartresult[j]=part[j];
}
for（intj=length;j>i;j--）{
partresult[j]=partresult[j-1];
}
partresult[i]=length;
midList.add（partresult）;
}
bestresult=gettheMidArray（midList）;
returnbestresult;
}
privatestaticint[]gettheMidArray（ListmidList）{
//TODOAuto-generatedmethodstub
int[]bestresult=（int[]）midList.get（0）;
inttotaldistance=getthedistance（bestresult）;
for（inti=1;i{
int[]temp=（int[]）midList.get（i）;
inttempdis=getthedistance（temp）;
if（tempdistotaldistance=tempdis;
bestresult=temp;
}
}
returnbestresult;
}
privatestaticintgetthedistance（int[]temp）{
//TODOAuto-generatedmethodstub
intdistance=0;
for（inti=0;idistance=distance+citys[temp[i]-1][temp[i+1]-1];
}
returndistance;
}
}
运行结果为：
哈密尔顿回路：
1,3,4,5,2,
升级会员 