哈密爾頓迴路

哈密爾頓迴路
“哈密爾頓迴路問題”問題是愛爾蘭著名學者威廉·哈密爾頓爵士（W.R.Hamilton）1859年提出的一個數學問題。其大意是：在任一給定的圖中，能不能找到這樣的路徑，即從一點出發不重複地走過所有的結點（不必通過圖中每一條邊），最後又回到原出發點。
關於漢密爾頓最短路徑的算法
趙禹驊1，任偉民1，李可柏2
(1.同濟大學經濟與管理學院，上海　200092；
2.南昌大學理學院，南昌　330047)
Arithmetic About the Shortest Route of Hamilton Loop
ZHAO Yu?hua1，REN Wei?min1，LI Ke?bo2
(1.Tongji Univ.,Shanghai 200092；2.Nanchang Univ.,330047)
Abstract：Discusses an arithmetic about how to find out a Hamilton loop,which possesses the minimum total weight.From the result of any classical arithmetic,the arithmetic can get its partial optimization,so it improves the ability of all classical arithmetic about Hamilton loop,And its workload can be expressed as polynomial.
Key words：Hamilton loop；Classical arithmetic；Optimization；Polynomial
摘　要：提出了一個對業已存在的賦權漢密爾頓迴路進行最佳化的算法。該算法以經典算法的解為起點，尋找其局部極值點，極大改進了經典啟發式算法的性能。該算法屬半多項式算法。圖8表1參2
關鍵字：漢密爾頓迴路；古典算法；最佳化；多項式
1　前言
1857年，英國數學家漢密爾頓(Hamilton)提出了著名的漢密爾頓迴路問題，其後，該問題進一步被發展成為所謂的“貨郎擔問題”，即賦權漢密爾頓迴路最小化問題：這兩個問題成為數學史上著名的難題。而後者在工程最佳化、現場管理等現實生活中有重要作用：以電站建設為例，如何使若干供貨點的總運費最小，施工現場如何使供貨時間最短等等，最終都歸結為賦權漢密爾頓問題，是電站建設中成本控制和進度最佳化的關鍵技術；因而，賦權漢密爾頓問題與主生產計畫安排成為電站建設中成本控制和進度最佳化的兩大技術難題。而且，主生產計畫安排，又可以分解為有向圖的賦權漢密爾頓問題進行解決；因此，賦權漢密爾頓問題在包括電站建設的大型工程建設項目占有重要的地位，具有重大的理論和現實意義。理論上講，賦權漢密爾頓問題的最優解總可以用枚舉法求出；但在實際工作中，枚舉法的計算量巨大，對於n個點的問題存在(n－1)!條漢密爾頓迴路，當n比較大時，枚舉法顯然是行不通的，為此，最佳化專家們提出了啟發式算法[1]，以期求得該問題的近似最優解。而不同算法之目的是共同的，即在多項式的運算量內，儘可能提高其解的精度。其中套用比較廣泛的有Clarke和Wright的C－W算法，Norback和Love的幾何算法[2]，在此，稱這些算法為經典啟發式算法，簡稱經典算法，這些算法的一個共同特點就是非最佳化性。針對這一特點，本文提出一種局部最佳化的算法，對業已求得的漢密爾頓迴路進行最佳化。這種算法的結果是以經典算法結果為起點的局部最佳化解，因此，該算法極大改進了經典啟發式算法的性能，且在目前可考證的情況下，均能求得最優解；但是，是否在任何情況下都能求得最優解則尚待證明。
2　算法及其特點分析
2.1　算法思想的提出
所謂賦權漢密爾頓迴路最小化問題是指，給定n個點及n個點兩兩之間的距離(或權數)，求一條迴路，使之經過所有的點，且經過每個點僅一次，而整條迴路(也稱路徑或邊界)的總距離(或總權數)最小。
這一問題總是可以通過枚舉法求出其解的，但由於枚舉法的計算量過大，達到(n－1)!的數量級，因而，不是可行的方法。由此，人們提出了啟發式算法來求解問題的近似解。所謂啟發式算法，一般地講，就是發現某些最優解所具備的特徵或不應具備的特徵，對應有特徵而言，求出含應有特徵的可行解；對不應有特徵而言，從解空間中剔除不應有特徵的解，再從剩餘空間中找一個解。因而，啟發式算法可以定義為：從最優解的必要條件出發，設計一個有效算法，使之求出的解滿足這些必要條件。
就一般算法的本質而言，它是提供一種規範的過程，經由該過程得出的解滿足問題最優解的充分條件，即算法應該是問題最優解的充分條件的一種規範實現過程；而算法設計本身要求，算法必須給出解，因此，算法實際上還要滿足最優解的必要條件，即算法可以定義為：算法是問題最優解的充分必要條件的一種規範實現過程。
啟發式算法只滿足了算法的必要性條件，而沒有滿足其充分性條件，就一般意義而言，其結果不是問題的最優解。基於這一思路，經典啟發式算法的做法就是從滿足必要條件的解空間中找出一個解，這就產生了一個問題：這樣的解是否還可以按某種規則改進?這就涉及局部極值或重疊套用啟發式算法的問題。如果存在局部極值或進一步最佳化的規則，那么，在已有解的基礎上繼續運用這些規則會極大改進算法的性能，這就是本算法的基本思路。
2.2　算法的規則分析
依據上述局部最佳化的算法思想，對賦權漢密爾頓最小化問題進行分析。對該問題的一般形式(包括平面和非平面)給出一條規則：最優路徑上各點在插入路徑時，其路徑變化量最小。
這是本文給出最佳化算法的基礎。關於該規則，用反證法可以簡單地證明，即若最優路徑上有某一點在插入路徑時，其路徑變化量不是最小，那么，至少還有一種插入法的路徑變化量更少，則以路徑變化量更小的插法來代替原插入方法，由此形成的迴路其路徑更短，而這與原路徑最短的假設矛盾，所以，規則成立。
依據上面的分析，給出相應的算法。
2.3　算法
算法設計分為兩步：(1)運用經典算法求出一條漢密爾頓迴路；(2)運用本文算法對該迴路進行最佳化。在此，不討論由經典算法找出一條迴路的方法，討論依據上面原則對已有迴路進行最佳化的算法。
2.3.1　最佳化方法
第0步，確定一個初始的循環起點。即以漢密爾頓迴路上的某一點作為循環的起點，以該起點為當前點，轉入第1步。
第1步，跨線切割形成孤立點。即在已形成的漢密爾頓迴路上，以當前點為跨線的起點，按路徑方向作跨線，用跨線切割中間點，使該中間點成為孤立點，而該跨線成為一條邊；此時，迴路的路徑上不包含全部點，故非然漢密爾頓迴路，轉入第2步。
第2步，將孤立點重新連入路徑中。按路徑變化量最小原則，將被切割下來的孤立點重新連入迴路中；連入之後，迴路的路徑中包括全部點，故又形成漢密爾頓迴路，轉入第3步。
第3步，如果產生了路徑的變化，則以新路逕取代舊路徑，但以原跨線的起點為循環的新起點，也為當前點，返回第1步，繼續計算；否則，走向下一點，以下一點為當前點，轉入第4步。
第4步，判斷一個循環是否完成，即當前點是否是循環的起點。如是，則算法結束；如不是，則轉入第1步。(算法描述完畢)
當算法結束時，迴路上的每一個點相對於其它點都是最優，即迴路達到其局部極值。
對平面問題，為簡化計算，當跨線為內連線時，不作變動，向下一點走；當跨線為外連線時，切割其中間點，然後再將被切掉的中間點重新連入路徑中。
2.3.2　幾個概念
跨線：在迴路中，連線兩個不相鄰點，且中間只有一個點，這箇中間點是該連線的起點和終點的相鄰點，該連線稱跨線。例如，在迴路A－B－C－D－E－F－G－A中，A與B、B與C等都是相鄰點，則連線AC連線了不相鄰點A和C，且其中間只有一個點B，而點B是A的相鄰點，也是C的相鄰點，故連線AC是跨線。
邊：兩個相鄰點之間的連線，如上面A與B的連線，B與C的連線都是邊。
路徑變化量：將某一點連入路徑中，就是要把該點與路徑中的某一條邊的起點和終點相連，以這兩條新的邊取代原來的邊；這樣，新的兩條邊長(權重)之和與原來邊長(權重)的差就是將該連入路徑後引入路徑長(總權重)的變化量，稱路徑變化量。例如，將點D插入迴路A－B－C－E－F－G－A的邊EF中，實際上就是將ED和DF相連，用新的邊ED和DF取代原來的邊EF，由此引起的路徑變化量，即迴路A－B－C－E－F－G－A與迴路A－B－C－E－D－F－G－A的總長度(總權重)之差等於兩條新邊的長度(權重)之和減原來邊的邊長(權重)，即等於ED+DF－EF。
路徑變化量最小原則：從上面路徑變化量的定義可以看出，將一個點插入路徑中，可以有多條邊供選擇，而插入不同的邊，所引起的路徑變化量各不相同；但其中有一條邊，當將要插入的點插入該邊時，其路徑的變化量最小，則選擇將該點插入該邊。
下面將運用一個實例來對算法進行更詳細的說明。
3　實例
給定問題如圖1所示，求過點A，B，C，D，E，F，G，每個點僅一次的迴路，且其路徑要最短。上述七點兩兩之間的距離如表1。
3.1　運用經典算法求出一條迴路
在此選用Clarke和Wright的C－W算法求得。
迴路：A－B－C－F－E－D－G－A，如圖2所示；
至此，經典啟發式算法對賦權漢密爾頓問題的求解過程結束。在此基礎上，進一步對路徑進行最佳化，以該解為起點，尋找其局部極值。
3.2　對業已形成的賦權漢密爾頓迴路進行最佳化
(1)由圖2從A點開始作第1次循環調整
此時，循環起點T=A，當前起點S=A，當前圖示號N=2。
(2)圖2中，由S=A點作跨線AC，AC是內連線，不切割點。向下點走，S=B。
(3)圖2中，由S=B點作跨線BF，BF是內連線，不切割點。向下點走，S=C。
(4)圖2中，由S=C點作跨線CE，CE是外連線，切割F點，得圖3。按規則（路徑變化量最小原則）重新將點F插入路徑中，計算F的路徑變化量如下：
因C點跨線引起了路徑變化，所以，T=C，且應對新圖再從S=C點繼續作跨線。由圖4，跨線為CD，CD是外連線，切割E點，得圖5。按規則重新將點E插入路徑中。計算E的路徑變化量如下。
則E點的最小路徑變化量為：DEF=0.31。
所以，將點E插入邊DF中，得圖6，N=6。
因C點跨線引起路徑變化，所以，T=C，圖6中，再從S=C點繼續作跨線。圖6中，跨線為CE，CE是內連線，不切割點。向下點走，S=D。
(4)圖6中，由S=D點作跨線DF，DF是外連線，切割點E，得圖5。可知，按規則將點E重新連入得圖6。因D點跨線未引起路徑變化。向下點走，S=E。
(5)S=D，由S=E點作跨線EG，EG是外連線，切割點F，得圖7。按規則將點F重新連入路徑。計算點F的路徑變化量如下。
則F的最小路徑變化量為EFG=0.24。
所以，將F再插回EG中，得圖6。所以，點E的跨線未引起路徑變化。向下點走，S=F。
(6)圖6中，由S=F點作跨線FA，FA是外連線，切割點G，得圖8。按規則重新將點G連入。計算點G的路徑變化量如下。
則點G的最小路徑變化量為：FGA=0.09。
所以，將點G再插回邊FA中，得圖6。G點的跨線未引起路徑變化。向下點走，S=G。
(7)圖6中，由S=G點作跨線GB，GB是內連線，不切割點。向下點走，S=A。
(8)圖6中，由S=A點作跨線AC，AC是內連線，不切割點。向下點走，S=B。
(9)圖6中，由S=B點作跨線BD，BD是半內連線，也不切割點。向下點走S=C。
此時，T=C=S，即循環起點等於當前點，算法結束，N=6。
此時的當前圖6是局部最優解。
路徑為：A－B－C－D－E－F－G－A
路徑長度為：14.14+13.04+20.10+8.25+2.83+4.12+13.00=75.48
事實上，可以用枚舉法驗證，圖6也是全局最優解。
4　幾點說明和補充
(1)某些經典啟發式算法的結果未進行必要的最佳化，這在局部最佳化規則可行的條件存在著解空間的浪費，對這些結果進行最佳化可以極大的改進算法的性能，本算法正是這一思想的體現。
(2)本文未對賦權漢密爾頓迴路最小化問題的解空間的極值數進行論證，只是給出了以經典算法為起點，求其局部極值的算法；因而，算法的結果未必總是問題的最優解。只有當解空間的極值點唯一時，才能保證本算法的結果是全局最優解；所以，本算法的解是否總能保證是全局最優解，尚需論證問題的解空間。
(3)即使問題的解空間有多個極值點，但是，如果原經典算法的解進入全局最優解的領域，本算法的解也是最優解。
(4)上面計算中，當跨線為外連線時切割點，為內連線時不切割點，減少了計算量。由經典幾何算法的規則[2]可知，任意內連線所引起的路徑變化均可由外連線完成，故，對平面的賦權漢密爾頓問題只選擇外連線兒為切割線是合理的；而當問題是非平面問題時，則不存在連線內外的概念，所有跨線均切割中間點，均需重做計算和連入。
(5)本算法是半多項式算法，即一個進步的計算量是多項式的，但算法的進步有多少與初始解有關，因而不可預知。一個進步指找到一個比當前解更優的解，本算法中，一個進步的計算量不超過n2。若設定進步數的上限為m次，則：或者極大改進了結果，計算量為(m×n2)；或者在小於(m×n2)的計算內達到局部極值而對原結果有所改進；或者因初始迴路即為極值而只做了1個循環，計算量為n2。因計算路徑是最佳化軌跡，即每一次循環至少有一個進步；所以，算法的收斂速度很快。
(6)本算法是以有向圖給出的，因而，在計算路徑變化量時運用了嚴格的符號順序，其方向為：左邊是線段的起點，右邊是線段的終點，例如，線A－B表示A為起點而B為終點。但算法也適用於無向圖，所給實例即為無向圖。
(7)算法的結束條件。算法過程自動保證了算法不會在兩個不同路徑長度的圖之間來回計算，當存在相同最小路徑變化量的不同路徑時，算法選取首次得到的路徑為最優(舊圖優先)，從而保證了算法不會產生抖動問題，即不會沒有終點。
(8)在極值點有多條路徑時，在極值點會出現路徑長度相同但路徑不同的情況；而上述算法結束時，最佳化路徑集中只有一條路徑。如果對上面算法略作修改，當存在相同最小路徑變化量的不同路徑時，記錄所有這些路徑，從這些路徑中剔除最佳化路徑集中已存在的路徑，剩餘路徑補進最佳化路徑集中；以此算法對上述算法的結果進行重新計算，當最佳化路徑集中的全部路徑計算完畢，而沒有路徑數目的增長時，就得到全部的極點解。