哈密頓迴路演算法

❶ 近似演算法的旅行售貨員問題近似演算法

問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負整數費用c(u,v)。要找出G的最小費用哈密頓迴路。
旅行售貨員問題的一些特殊性質：
比如，費用函數c往往具有三角不等式性質，即對任意的3個頂點u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。當圖G中的頂點就是平面上的點，任意2頂點間的費用就是這2點間的歐氏距離時，費用函數c就具有三角不等式性質。
對於給定的無向圖G，可以利用找圖G的最小生成樹的演算法設計找近似最優的旅行售貨員迴路的演算法。
void approxTSP (Graph g)
{
(1)選擇g的任一頂點r；
(2)用Prim演算法找出帶權圖g的一棵以r為根的最小生成樹T；
(3)前序遍歷樹T得到的頂點表L；
(4)將r加到表L的末尾，按表L中頂點次序組成迴路H，作為計 算結果返回；
}
當費用函數滿足三角不等式時，演算法找出的旅行售貨員迴路的費用不會超過最優旅行售貨員迴路費用的2倍。

(b)表示找到的最小生成樹T；(c)表示對T作前序遍歷的次序；(d)表示L產生的哈密頓迴路H；
(e)是G的一個最小費用旅行售貨員迴路。

❷ NP問題的簡述

首先需要介紹P(Polynomial,多項式)問題.P問題是可以在多項式時間內被確定機(通常意義的計算機)解決的問題.NP(Non-Deterministic Polynomial, 非確定多項式)問題,是指可以在多項式時間內被非確定機(他可以猜,他總是能猜到最能滿足你需要的那種選擇,如果你讓他解決n皇後問題,他只要猜n次就能完成----每次都是那麼幸運)解決的問題.這里有一個著名的問題----千禧難題之首,是說P問題是否等於NP問題,也即是否所有在非確定機上多項式可解的問題都能在確定機上用多項式時間求解.
這樣一來,只要我們找到一個NPC問題的多項式解,所有的NP問題都可以多項式時間內劃歸成這個NPC問題,再用多項式時間解決,這樣NP就等於P了.
換一種說法,如果一個問題的復雜度是該問題的一個實例規模n的多項式函數，則這種可以在多項式時間內解決的問題屬於P類問題.通俗地稱所有復雜度為多項式時間的問題為易解的問題類，否則為難解的問題。
有些問題很難找到多項式時間的演算法（或許根本不存在），例如「找出無向圖中哈密頓迴路」問題。但如果給了該問題的一個答案，可以在多項式時間內判斷這個答案是否正確。例如說對於哈密頓迴路問題，給一個任意的迴路，很容易判斷它是否是哈密頓迴路（只要看是不是所有的頂點都在迴路中就可以了）。這里給出NP問題的另一個定義,這種可以在多項式時間內驗證一個解是否正確的問題稱為NP問題，亦稱為驗證問題類。
簡單的說，存在多項式時間的演算法的一類問題，稱之為P類問題；在多項式時間內可由非確定機解決的一類問題，稱之為NP問題。另外，很多人相信P類問題是NP問題的一個子集，但既沒有人證明出有某個問題屬於NP但不屬於P，也沒有人證明所有NP問題都能在多項式時間內有解。

❸ matlab最短哈密頓迴路演算法

可以用蟻群演算法,當然Hopfield網路與退火我也試過,但還是蟻群的效果最好.

注意:哈密頓迴路問題(TSP問題)是NP-COMPLETE問題,問題規模比較大時無法求得最優解,只能通過啟發式演算法逼近其次優解.

把你的郵箱留下來吧.我這有一份C++寫的,不過封裝成MEX了,MATLAB里可以直接調用的,速度還不錯.純MATLAB的我也有,不過速度慢死.要不然我就不費事用C++重寫一份了.

留郵箱吧.

❹ hamilton圈演算法是什麼意思

哈密頓圖（哈密爾頓圖）（英語：Hamiltonian path，或Traceable path）是一個無向圖，由天文學家哈密頓提出，由指定的起點前往指定的終點，途中經過所有其他節點且只經過一次。在圖論中是指含有哈密頓迴路的圖，閉合的哈密頓路徑稱作哈密頓迴路（Hamiltonian cycle），含有圖中所有頂點的路徑稱作哈密頓路徑。

從圖中的任意一點出發，路途中經過圖中每一個結點當且僅當一次，則成為哈密頓迴路。
要滿足兩個條件：
⒈封閉的環
⒉是一個連通圖，且圖中任意兩點可達
經過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路稱為哈密頓通路。
經過圖中所有頂點一次且僅一次的迴路稱為哈密頓迴路。
具有哈密頓迴路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓迴路的圖稱為半哈密頓圖。
平凡圖是哈密頓圖。

❺ 數據結構——圖graph（基礎概念）

【各種東拼西湊來的】

圖(Graph)是由頂點和連接頂點的邊構成的離散結構。在計算機科學中，圖是最靈活的數據結構之一，很多問題都可以使用圖模型進行建模求解。例如：生態環境中不同物種的相互競爭、人與人之間的社交與關系網路、化學上用圖區分結構不同但分子式相同的同分異構體、分析計算機網路的拓撲結構確定兩台計算機是否可以通信、找到兩個城市之間的最短路徑等等。

圖的結構很簡單，就是由頂點$V$集和邊$E$集構成，因此圖可以表示成$G=(V, E)$。

注意： 頂點有時也稱為節點或者交點，邊有時也稱為鏈接。

無向圖

我們可以說這張圖中，有點集$V=\{1, 2, 3, 4, 5, 6\}$，邊集$E=\{(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)\}$。在無向圖中，邊$(u, v)$和邊$(v, u)$是一樣的，因此只要記錄一個就行了。簡而言之，對稱。

有向圖

也很好理解，就是加上了方向性，頂點$(u, v)$之間的關系和頂點$(v,u)$之間的關系不同，後者或許不存在。例如，地圖應用中必須存儲單行道的信息，避免給出錯誤的方向。

加權圖 ：

權：與圖的邊或弧相關的數叫做權。

與加權圖對應的就是無權圖，或叫等權圖。如果一張圖不含權重信息，我們就認為邊與邊之間沒有差別。不過，具體建模的時候，很多時候都需要有權重，比如對中國重要城市間道路聯系的建模，總不能認為從北京去上海和從北京去廣州一樣遠(等權)。

還有很多細化的概念，比如：無向圖中，任意兩個頂點間都有邊，稱為 無向完全圖 ；加權圖起一個新名字，叫 網(network) ……然而，如無必要，毋增實體。

鄰接(adjacency) ：鄰接是 兩個頂點之間 的一種關系。如果圖包含$(u,v)$，則稱頂點$v$與頂點$u$鄰接。當然，在無向圖中，這也意味著頂點$u$與頂點$v$鄰接。

關聯(incidence) ：關聯是 邊和頂點之間 的關系。在有向圖中，邊$(u,v)$從頂點$u$開始關聯到$v$，或者相反，從$v$關聯到$u$。注意，有向圖中，邊不一定是對稱的，有去無回是完全有可能的。細化這個概念，就有了頂點的 入度(in-degree) 和 出度(out-degree) 。無向圖中，頂點的度就是與頂點相關聯的邊的數目，沒有入度和出度。在有向圖中，我們以圖1-2為例，頂點10有2個入度，$3\rightarrow10$，$11\rightarrow10$，但是沒有從10指向其它頂點的邊，因此頂點10的出度為0。

路徑(path) ：依次遍歷頂點序列之間的邊所形成的軌跡。注意，依次就意味著有序，先1後2和先2後1不一樣。

簡單路徑 : 沒有重復頂點的路徑稱為簡單路徑。說白了，這一趟路里沒有出現繞了一圈回到同一點的情況，也就是沒有 環 。

環/迴路 ：包含相同的頂點兩次或者兩次以上。圖1-3中的頂點序列$<1,2,4,3,1>$，1出現了兩次，當然還有其它的環，比如$<1,4,3,1>$。

簡單迴路/簡單環： 除了第一個頂點和最後一個頂點之外，其餘頂點不重復出現的迴路

無環圖 ：沒有環的圖，其中， 有向無環圖 有特殊的名稱，叫做 DAG(Directed Acyline Graph) （最好記住，DAG具有一些很好性質，比如很多動態規劃的問題都可以轉化成DAG中的最長路徑、最短路徑或者路徑計數的問題）。

兩個連通分支：

連通的 ：無向圖中每一對不同的頂點之間都有路徑。如果這個條件在有向圖里也成立，那麼就是 強連通 的。

連通分量 ：無向圖中的極大連通子圖。

兩點強連通：在有向圖G中，如果兩點互相可達

強連通圖： 如果有向圖G的每兩個頂點都強連通（任意兩點互相可達），稱G是一個 強連通圖 。

強連通分量： 非強連通有向圖的極大強連通子圖，稱為強連通 分量 (strongly connected components)。

關節點(割點) ：某些特定的頂點對於保持圖或連通分支的連通性有特殊的重要意義。如果 移除某個頂點 將使圖或者分支 失去連通性 ，則稱該頂點為 關節點 。（在某圖中，若刪除頂點V以及V相關的邊後，圖的一個連通分量分割為兩個或兩個以上的連通分量，則稱頂點V為該圖的一個關節點）。

橋(割邊) ：和關節點類似，刪除一條邊，就產生比原圖更多的連通分支的子圖，這條邊就稱為 割邊 或者 橋 。

雙連通圖 ：在無向連通圖中，如果刪除該圖的任何一個結點都不能改變該圖的連通性，則該圖為雙連通的無向圖。個人理解就是一個雙連通圖沒有割點，沒有橋的圖。

1.2 一些有趣的圖概念

這一部分屬於圖論的內容，基礎圖演算法不會用到，但是我覺得挺有意思的，小記如下。【這部分我沒看，照搬過來了】

同構 4 ：圖看起來結構不一樣，但它是一樣的。假定有$G_1$和$G_2$，那麼你只要確認對於$G_1$中的所有的兩個 相鄰點 $a$和$b$，可以通過某種方式$f$映射到$G_2$，映射後的兩個點$f(a)$、$f(b)$也是相鄰的。換句話說，當兩個簡單圖同構時，兩個圖的頂點之間保持相鄰關系的一一對應。

圖1-7就展示了圖的同構，這里頂點個數很少判斷圖的同構很簡單。我們可以把v1看成u1，自然我們會把u3看出v3。用數學的語言就是$f(u_1)=v_1$，$f(u_3)=v_3$。u1的另外一個連接是到u2，v1的另外一個連接是到v4，不難從相鄰頂點的關系驗證$f(u_2)=v_4$，$f(u_4)=v_2$。

歐拉迴路(Euler Circuit) ：小學數學課本上的哥尼斯堡七橋問題，能不能從鎮里的某個位置出發 不重復的經過所有橋(邊)並且返回出發點 。這也就小學的一筆畫問題，歐拉大神解決里這個問題，開創了圖論。結論很簡單：至少2個頂點的連通多重圖存在歐拉迴路的充要條件是 每個頂點的度都是偶數 。證明也很容易，大家有興趣可以閱讀相關資料。結論也很好理解，從某個起點出發，最後要回起點，中間無論路過多少次起點，都會再次離開，進、出的數目必然相等，故一定是偶數。

哈密頓迴路(Hamilton Circuit) ：哈密頓迴路條件就比歐拉迴路嚴格一點， 不能重復經過點 。你可能會感到意外，對於歐拉迴路，我們可以輕而易舉地回答，但是 我們卻很難解決哈密頓迴路問題，實際上它是一個NP完全問題 。這個術語源自1857年愛爾蘭數學家威廉·羅萬·哈密頓爵士發明的智力題。哈密頓的智力題用到了木質十二面體（如圖1-8(a)所示，十二面體有12個正五邊形表面）、十二面體每個頂點上的釘子、以及細線。十二面體的20個頂點用世界上的不同城市標記。智力題要求從一個城市開始，沿十二面體的邊旅行，訪問其他19個城市，每個恰好一次，最終回到第一個城市。

因為作者不可能向每位讀者提供帶釘子和細線的木質十二面體，所以考慮了一個 等價的問題 ：對圖1-8(b)的圖是否具有恰好經過每個頂點一次的迴路？它就是對原題的解，因為這個平面圖 同構 於十二面體頂點和邊。

著名的 旅行商問題(TSP) 要求旅行商訪問一組城市所應當選取的最短路線。這個問題可以歸結為求完全圖的哈密頓迴路，使這個迴路的邊的權重和盡可能的小。同樣，因為這是個NP完全問題，最直截了當的方法就檢查所有可能的哈密頓迴路，然後選擇權重和最小的。當然這樣效率幾乎難以忍受，時間復雜度高達$O(n!)$。在實際應用中，我們使用的啟發式搜索等 近似演算法 ，可以完全求解城市數量上萬的實例，並且甚至能在誤差1%范圍內估計上百萬個城市的問題。

關於旅行商問題目前的研究進展，可以到 http://www.math.uwaterloo.ca/... 。

1.3 小結

以為可以一帶而過，結果寫了那麼多。也沒什麼好總結的了，當然這些也至是圖論概念的一小部分，還有一些圖可能我們以後也會見到，比如順著圖到網路流，就會涉及二分圖，不過都很好理解，畢竟有圖。

1、數組（鄰接矩陣）

2、鄰接表

3、十字鏈表

4、鄰接多種表

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

你這個問題是NPC問題，不存在多項式時間的演算法。

只有兩種方法：
1，搜索：O(n!)
2，狀態壓縮的動態規劃：O(n^2*2^n)

❼ 什麼是哈密頓路徑問題

也叫哈密頓迴路:在圖中找出一條包含所有結點的閉路，並且，出來起點和重點重合外，這條閉路所含結點是互不相同的 可以在多項式時間類判斷一個迴路是否是哈密頓迴路 但目前沒有演算法直接解出哈密頓迴路

天文學家哈密頓(William Rowan Hamilton) 提出，在一個有多個城市的地圖網路中，
尋找一條從給定的起點到給定的終點沿 途恰好經過所有其他城市一次的路徑。
這個問題和著名的過橋問題的不同之處在於，某些城市之間的旅行不 一定是雙向的。比如A→B,但B→A是不允許的。
換一種說法，對於一個給定的網路，確定起點和終點後，如果存在一條路徑，穿過這個網路，我們就說這個網路存在哈密頓路徑。哈密頓路徑問題在上世紀七十年代初，終於被證明是「NP完備」的。據說具有這樣性質的問題，難於找到一個有效的演算法。實際上對於某些頂點數不到100的網路，利用現有最好的演算法和計算機也需要比較荒唐的時間（比如幾百年）才能確定其是否存在一條這樣的路徑。

❽ 求matlab解決哈密頓迴路

可以用蟻群演算法, 當然Hopfield網路與退火我也試過, 但還是蟻群的效果最好.
注意: 哈密頓迴路問題(TSP問題)是NP-COMPLETE問題, 問題規模比較大時無法求得最優解, 只能通過啟發式演算法逼近其次優解.
把你的郵箱留下來吧. 我這有一份C++寫的, 不過封裝成MEX了, MATLAB里可以直接調用的, 速度還不錯. 純MATLAB的我也有, 不過速度慢死. 要不然我就不費事用C++重寫一份了.

❾ 哈密爾頓迴路問題具體指什麼

1857年，英國數學家漢密爾頓(Hamilton)提出了著名的漢密爾頓迴路問題，其後，該問題進一步被發展成為所謂的「貨郎擔問題」，即賦權漢密爾頓迴路最小化問題：這兩個問題成為數學史上著名的難題。而後者在工程優化、現場管理等現實生活中有重要作用：以電站建設為例，如何使若干供貨點的總運費最小，施工現場如何使供貨時間最短等等，最終都歸結為賦權漢密爾頓問題，是電站建設中成本控制和進度優化的關鍵技術；因而，賦權漢密爾頓問題與主生產計劃安排成為電站建設中成本控制和進度優化的兩大技術難題。而且，主生產計劃安排，又可以分解為有向圖的賦權漢密爾頓問題進行解決；因此，賦權漢密爾頓問題在包括電站建設的大型工程建設項目佔有重要的地位，具有重大的理論和現實意義。理論上講，賦權漢密爾頓問題的最優解總可以用枚舉法求出；但在實際工作中，枚舉法的計算量巨大，對於n個點的問題存在(n－1)!條漢密爾頓迴路，當n比較大時，枚舉法顯然是行不通的，為此，優化專家們提出了啟發式演算法[1]，以期求得該問題的近似最優解。而不同演算法之目的是共同的，即在多項式的運算量內，盡可能提高其解的精度。其中應用比較廣泛的有Clarke和Wright的C－W演算法，Norback和Love的幾何演算法[2]，在此，稱這些演算法為經典啟發式演算法，簡稱經典演算法，這些演算法的一個共同特點就是非優化性。針對這一特點，本文提出一種局部優化的演算法，對業已求得的漢密爾頓迴路進行優化。這種演算法的結果是以經典演算法結果為起點的局部優化解，因此，該演算法極大改進了經典啟發式演算法的性能，且在目前可考證的情況下，均能求得最優解；但是，是否在任何情況下都能求得最優解則尚待證明。

❿ 哈密頓迴路的演算法

哈密頓路徑問題在上世紀七十年代初，終於被證明是「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。
⒉數據矩陣格式要求：只允許為上三角矩陣，不支持全矩陣以及下三角矩陣的運算。
⒊代碼擴展方法請使用者獨立思考，不唯一。
⒋運算數據擴展方法，請使用者獨立思考，不唯一。
⒌此代碼為本人畢設的附加產品，不會對使用此代碼者，因理解不當或使用不當而造成的任何不良後果，付出任何責任。
⒍代碼僅供交流。