最短哈密顿回路算法

① 最短哈密顿回路！！！！！！！！！

你这个问题是NPC问题，不存在多项式时间的算法。

只有两种方法：
1，搜索：O(n!)
2，状态压缩的动态规划：O(n^2*2^n)

② 哈密顿回路的算法

哈密顿路径问题在上世纪七十年代初，终于被证明是“NP完备”的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。
从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。
要满足两个条件：
⒈封闭的环
⒉是一个连通图，且图中任意两点可达
经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。
经过图中所有顶点一次且仅一次的回路称为哈密顿回路。
具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。
平凡图是哈密顿图。
⒊若以1到2、2到3、3到4、4到5、5到1，为计数规律，则各点均出现两次；这种判断方法在计算机编程运算中显得尤为重要，其会精简很多运算过程。
⒋新出炉，有待检测的代码如下：
%-------输入的数据的原数据参照
% v1 v2 v3 v4 v5
%v1 0 20 1 11 2
%v2 0 0 9 1 3
%v3 0 0 0 13 8
%v4 0 0 0 0 6
%v5 0 0 0 0 0
%以上为输入数据的原数据参照
%建议所计算的数据矩阵长度为5，不会产生bug，且不会对任何计算机造成计算负担
%输入数据矩阵长度可以超过5，但是最初计算出的n个最小值中，重复次数超过2的点的种类只允许为一种
a=[0 20 1 11 2
0 0 9 1 3
0 0 0 13 8
0 0 0 0 6
0 0 0 0 0];
l=length(a)
s1=inf
zp=inf
n2=1
f=a
f(a==0)=inf
b=zeros(l)
i1=0
while i1<=l-1
[r c]=find(f==min(min(f)))
b(r⑴，c⑴)=f(r⑴，c⑴)
f(r⑴，c⑴)=inf
i1=i1+1
end
f1=f
[rz cz]=find(b>0)
pathz=[rz cz]
pz=[rz;cz]
p2z=zeros（2*l,1）
i2z=1
n2z=0
while i2z<=2*l
[r2z c2z]=find(pz==pz(i2z,1）)
k1z=size(r2z)
if k1z（1,1）>2
p2z(r2z,1）=pz(r2z,1）
n2z=n2z+1
end
i2z=i2z+1
end
if n2z==2
HHL=b
zp=sum(sum(b))
else
while min(min(f1）)~=inf
if n2>2
b=snh
end
[r1 c1]=find(b>0)
path1=[r1 c1]
p1=[r1;c1]
p2=zeros（2*l,1）
i2=1
n2=0
while i2<=2*l
[r2 c2]=find(p1==p1(i2,1）)
k1=size(r2）
if k1（1,1）>2
p2(r2,1）=p1(r2,1）
n2=n2+1
end
i2=i2+1
end
[r3 c3]=find(p2>0)
p3=zeros(l,2）
i3=0
while i3<=n2-1
if r3⑴<=l
p3(r3⑴，：)=path1(r3⑴，：)
else
p3(r3⑴-l,:)=path1(r3⑴-l,:)
end
r3⑴=[]
i3=i3+1
end
p3(p3==0)=[]
p3=reshape(p3,n2,2）
p8=p2
[r8 c8]=find(p8>0)
p9=p8
r9=r8
i4=1
while i4<=n2
f1(p9(r9⑴，1），：)=inf
f1(:,p9(r9⑴，1）)=inf
r9⑴=[]
i4=i4+1
end
[r4 c4]=find(f1==min(min(f1）))
f1(r4,c4）=inf
b1=b
b1(r4,c4）=a(r4,c4）
i5=1
p4=p3
while i5<=n2
b1=b
b1(r4⑴，c4⑴)=a(r4⑴，c4⑴)
b1(p4（1,1），p4（1,2）)=0
p4（1,:)=[]
[r5 c5]=find(b1>0)
p5=[r5;c5]
i6=1
n6=0
while i6<=2*l
[r6 c6]=find(p5==p5(i6,1）)
k6=size(r6）
if k6（1,1）>2
n6=n6+1
end
i6=i6+1
end
if n6>2
if sum(sum(b1）)<s1
snh=[]
s1=sum(sum(b1）)
snh=b1
end
else
if sum(sum(b1）)<zp
HHL=[]
zp=sum(sum(b1）)
HHL=b1
end
end
i5=i5+1
end
end
[rs cs]=find(HHL>0)
minpaths=[rs cs]
journeys=zp
注：这段代码采用分支定界法作为编写程序的依据，因此代码依旧局限在算法上；而且代码的使用对所要计算的数据是有要求的，如下：
⒈只要数据在开始计算出的n个最小值中，其重复次数超过2次的点的种类只能为一种，例如：代码段中的数据五个最小值中其重复次数超过2次的点只有v5。
⒉数据矩阵格式要求：只允许为上三角矩阵，不支持全矩阵以及下三角矩阵的运算。
⒊代码扩展方法请使用者独立思考，不唯一。
⒋运算数据扩展方法，请使用者独立思考，不唯一。
⒌此代码为本人毕设的附加产品，不会对使用此代码者，因理解不当或使用不当而造成的任何不良后果，付出任何责任。
⒍代码仅供交流。

③ 哈密尔顿回路问题具体指什么

1857年，英国数学家汉密尔顿(Hamilton)提出了着名的汉密尔顿回路问题，其后，该问题进一步被发展成为所谓的“货郎担问题”，即赋权汉密尔顿回路最小化问题：这两个问题成为数学史上着名的难题。而后者在工程优化、现场管理等现实生活中有重要作用：以电站建设为例，如何使若干供货点的总运费最小，施工现场如何使供货时间最短等等，最终都归结为赋权汉密尔顿问题，是电站建设中成本控制和进度优化的关键技术；因而，赋权汉密尔顿问题与主生产计划安排成为电站建设中成本控制和进度优化的两大技术难题。而且，主生产计划安排，又可以分解为有向图的赋权汉密尔顿问题进行解决；因此，赋权汉密尔顿问题在包括电站建设的大型工程建设项目占有重要的地位，具有重大的理论和现实意义。理论上讲，赋权汉密尔顿问题的最优解总可以用枚举法求出；但在实际工作中，枚举法的计算量巨大，对于n个点的问题存在(n－1)!条汉密尔顿回路，当n比较大时，枚举法显然是行不通的，为此，优化专家们提出了启发式算法[1]，以期求得该问题的近似最优解。而不同算法之目的是共同的，即在多项式的运算量内，尽可能提高其解的精度。其中应用比较广泛的有Clarke和Wright的C－W算法，Norback和Love的几何算法[2]，在此，称这些算法为经典启发式算法，简称经典算法，这些算法的一个共同特点就是非优化性。针对这一特点，本文提出一种局部优化的算法，对业已求得的汉密尔顿回路进行优化。这种算法的结果是以经典算法结果为起点的局部优化解，因此，该算法极大改进了经典启发式算法的性能，且在目前可考证的情况下，均能求得最优解；但是，是否在任何情况下都能求得最优解则尚待证明。