最短哈密頓迴路演算法

① 最短哈密頓迴路！！！！！！！！！

你這個問題是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]，在此，稱這些演算法為經典啟發式演算法，簡稱經典演算法，這些演算法的一個共同特點就是非優化性。針對這一特點，本文提出一種局部優化的演算法，對業已求得的漢密爾頓迴路進行優化。這種演算法的結果是以經典演算法結果為起點的局部優化解，因此，該演算法極大改進了經典啟發式演算法的性能，且在目前可考證的情況下，均能求得最優解；但是，是否在任何情況下都能求得最優解則尚待證明。