用探索（窮舉）法求解貨郎擔問題

沒明確的解答過程 路線是1-2-4-3-1

成都創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設、高性價比廣水網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式廣水網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設找我們，業(yè)務覆蓋廣水地區(qū)。費用合理售后完善，十年實體公司更值得信賴。

2,3,4中3到1最短

2,4中4到3短

2到4比2到其他數(shù)短

成立

類似反證

其他自己搞定吧

貨郎擔問題算法(哈密爾頓回路算法) pascal 程序

資料：

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

所謂賦權漢密爾頓回路最小化問題是指，給定n個點及n個點兩兩之間的距離(或權數(shù))，求一條回路，使之經(jīng)過所有的點，且經(jīng)過每個點僅一次，而整條回路(也稱路徑或邊界)的總距離(或總權數(shù))最小。

這一問題總是可以通過枚舉法求出其解的，但由于枚舉法的計算量過大，達到(n－1)!的數(shù)量級，因而，不是可行的方法。由此，人們提出了啟發(fā)式算法來求解問題的近似解。所謂啟發(fā)式算法，一般地講，就是發(fā)現(xiàn)某些最優(yōu)解所具備的特征或不應具備的特征，對應有特征而言，求出含應有特征的可行解；對不應有特征而言，從解空間中剔除不應有特征的解，再從剩余空間中找一個解。因而，啟發(fā)式算法可以定義為：從最優(yōu)解的必要條件出發(fā)，設計一個有效算法，使之求出的解滿足這些必要條件。

就一般算法的本質而言，它是提供一種規(guī)范的過程，經(jīng)由該過程得出的解滿足問題最優(yōu)解的充分條件，即算法應該是問題最優(yōu)解的充分條件的一種規(guī)范實現(xiàn)過程；而算法設計本身要求，算法必須給出解，因此，算法實際上還要滿足最優(yōu)解的必要條件，即算法可以定義為：算法是問題最優(yōu)解的充分必要條件的一種規(guī)范實現(xiàn)過程。

啟發(fā)式算法只滿足了算法的必要性條件，而沒有滿足其充分性條件，就一般意義而言，其結果不是問題的最優(yōu)解。基于這一思路，經(jīng)典啟發(fā)式算法的做法就是從滿足必要條件的解空間中找出一個解，這就產(chǎn)生了一個問題：這樣的解是否還可以按某種規(guī)則改進?這就涉及局部極值或重疊應用啟發(fā)式算法的問題。如果存在局部極值或進一步優(yōu)化的規(guī)則，那么，在已有解的基礎上繼續(xù)運用這些規(guī)則會極大改進算法的性能，這就是本算法的基本思路。

依據(jù)上述局部優(yōu)化的算法思想，對賦權漢密爾頓最小化問題進行分析。對該問題的一般形式(包括平面和非平面)給出一條規(guī)則：最優(yōu)路徑上各點在插入路徑時，其路徑變化量最小。

這是本文給出優(yōu)化算法的基礎。關于該規(guī)則，用反證法可以簡單地證明，即若最優(yōu)路徑上有某一點在插入路徑時，其路徑變化量不是最小，那么，至少還有一種插入法的路徑變化量更少，則以路徑變化量更小的插法來代替原插入方法，由此形成的回路其路徑更短，而這與原路徑最短的假設矛盾，所以，規(guī)則成立。

依據(jù)上面的分析，給出相應的算法。

算法：

算法設計分為兩步：(1)運用經(jīng)典算法求出一條漢密爾頓回路；(2)運用本文算法對該回路進行優(yōu)化。在此，不討論由經(jīng)典算法找出一條回路的方法，討論依據(jù)上面原則對已有回路進行優(yōu)化的算法。

優(yōu)化方法：

第0步，確定一個初始的循環(huán)起點。即以漢密爾頓回路上的某一點作為循環(huán)的起點，以該起點為當前點，轉入第1步。

第1步，跨線切割形成孤立點。即在已形成的漢密爾頓回路上，以當前點為跨線的起點，按路徑方向作跨線，用跨線切割中間點，使該中間點成為孤立點，而該跨線成為一條邊；此時，回路的路徑上不包含全部點，故非然漢密爾頓回路，轉入第2步。

第2步，將孤立點重新連入路徑中。按路徑變化量最小原則，將被切割下來的孤立點重新連入回路中；連入之后，回路的路徑中包括全部點，故又形成漢密爾頓回路，轉入第3步。

第3步，如果產(chǎn)生了路徑的變化，則以新路徑取代舊路徑，但以原跨線的起點為循環(huán)的新起點，也為當前點，返回第1步，繼續(xù)計算；否則，走向下一點，以下一點為當前點，轉入第4步。

第4步，判斷一個循環(huán)是否完成，即當前點是否是循環(huán)的起點。如是，則算法結束；如不是，則轉入第1步。(算法描述完畢)

當算法結束時，回路上的每一個點相對于其它點都是最優(yōu)，即回路達到其局部極值。

對平面問題，為簡化計算，當跨線為內(nèi)連線時，不作變動，向下一點走；當跨線為外連線時，切割其中間點，然后再將被切掉的中間點重新連入路徑中。

概念：

跨線：在回路中，連線兩個不相鄰點，且中間只有一個點，這個中間點是該連線的起點和終點的相鄰點，該連線稱跨線。例如，在回路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。

路徑變化量最小原則：從上面路徑變化量的定義可以看出，將一個點插入路徑中，可以有多條邊供選擇，而插入不同的邊，所引起的路徑變化量各不相同；但其中有一條邊，當將要插入的點插入該邊時，其路徑的變化量最小，則選擇將該點插入該邊。

幾點說明和補充：

(1)某些經(jīng)典啟發(fā)式算法的結果未進行必要的優(yōu)化，這在局部優(yōu)化規(guī)則可行的條件存在著解空間的浪費，對這些結果進行優(yōu)化可以極大的改進算法的性能，本算法正是這一思想的體現(xiàn)。

(2)本文未對賦權漢密爾頓回路最小化問題的解空間的極值數(shù)進行論證，只是給出了以經(jīng)典算法為起點，求其局部極值的算法；因而，算法的結果未必總是問題的最優(yōu)解。只有當解空間的極值點唯一時，才能保證本算法的結果是全局最優(yōu)解；所以，本算法的解是否總能保證是全局最優(yōu)解，尚需論證問題的解空間。

(3)即使問題的解空間有多個極值點，但是，如果原經(jīng)典算法的解進入全局最優(yōu)解的領域，本算法的解也是最優(yōu)解。

(4)上面計算中，當跨線為外連線時切割點，為內(nèi)連線時不切割點，減少了計算量。由經(jīng)典幾何算法的規(guī)則[2]可知，任意內(nèi)連線所引起的路徑變化均可由外連線完成，故，對平面的賦權漢密爾頓問題只選擇外連線兒為切割線是合理的；而當問題是非平面問題時，則不存在連線內(nèi)外的概念，所有跨線均切割中間點，均需重做計算和連入。

(5)本算法是半多項式算法，即一個進步的計算量是多項式的，但算法的進步有多少與初始解有關，因而不可預知。一個進步指找到一個比當前解更優(yōu)的解，本算法中，一個進步的計算量不超過n2。若設定進步數(shù)的上限為m次，則：或者極大改進了結果，計算量為(m×n2)；或者在小于(m×n2)的計算內(nèi)達到局部極值而對原結果有所改進；或者因初始回路即為極值而只做了1個循環(huán)，計算量為n2。因計算路徑是優(yōu)化軌跡，即每一次循環(huán)至少有一個進步；所以，算法的收斂速度很快。

(6)本算法是以有向圖給出的，因而，在計算路徑變化量時運用了嚴格的符號順序，其方向為：左邊是線段的起點，右邊是線段的終點，例如，線A－B表示A為起點而B為終點。但算法也適用于無向圖，所給實例即為無向圖。

(7)算法的結束條件。算法過程自動保證了算法不會在兩個不同路徑長度的圖之間來回計算，當存在相同最小路徑變化量的不同路徑時，算法選取首次得到的路徑為最優(yōu)(舊圖優(yōu)先)，從而保證了算法不會產(chǎn)生抖動問題，即不會沒有終點。

(8)在極值點有多條路徑時，在極值點會出現(xiàn)路徑長度相同但路徑不同的情況；而上述算法結束時，優(yōu)化路徑集中只有一條路徑。如果對上面算法略作修改，當存在相同最小路徑變化量的不同路徑時，記錄所有這些路徑，從這些路徑中剔除優(yōu)化路徑集中已存在的路徑，剩余路徑補進優(yōu)化路徑集中；以此算法對上述算法的結果進行重新計算，當優(yōu)化路徑集中的全部路徑計算完畢，而沒有路徑數(shù)目的增長時，就得到全部的極點解。

求貨郎擔問題的matlab算法

貨郎擔問題有很多解法，模擬退火，遺傳算法，動態(tài)規(guī)劃等。

基于matlab TSP問題遺傳算法的實現(xiàn)

%TSP問題（又名：旅行商問題，貨郎擔問題）遺傳算法通用matlab程序

%D是距離矩陣，n為種群個數(shù),建議取為城市個數(shù)的1~2倍，

%C為停止代數(shù)，遺傳到第 C代時程序停止,C的具體取值視問題的規(guī)模和耗費的時間而定

%m為適應值歸一化淘汰加速指數(shù) ,最好取為1,2,3,4 ,不宜太大

%alpha為淘汰保護指數(shù),可取為0~1之間任意小數(shù),取1時關閉保護功能,最好取為0.8~1.0

%R為最短路徑,Rlength為路徑長度

function [R,Rlength]=geneticTSP(D,n,C,m,alpha)

[N,NN]=size(D);

farm=zeros(n,N);%用于存儲種群

for i=1:n

farm(i,:)=randperm(N);%隨機生成初始種群

end

R=farm(1,:);%存儲最優(yōu)種群

len=zeros(n,1);%存儲路徑長度

fitness=zeros(n,1);%存儲歸一化適應值

counter=0;

while counterc

for i=1:n

len(i,1)=myLength(D,farm(i,:));%計算路徑長度

end

maxlen=max(len);

minlen=min(len);

fitness=fit(len,m,maxlen,minlen);%計算歸一化適應值

rr=find(len==minlen);

R=farm(rr(1,1),:);%更新最短路徑

FARM=farm;%優(yōu)勝劣汰，nn記錄了復制的個數(shù)

nn=0;

for i=1:n

if fitness(i,1)=alpha*rand

nn=nn+1;

FARM(nn,:)=farm(i,:);

end

end

FARM=FARM(1:nn,:);

[aa,bb]=size(FARM);%交叉和變異

while aan

if nn=2

nnper=randperm(2);

else

nnper=randperm(nn);

end

A=FARM(nnper(1),:);

B=FARM(nnper(2),:);

[A,B]=intercross(A,B);

FARM=[FARM;A;B];

[aa,bb]=size(FARM);

end

if aan

FARM=FARM(1:n,:);%保持種群規(guī)模為n

end

farm=FARM;

clear FARM

counter=counter+1

end

Rlength=myLength(D,R);

function [a,b]=intercross(a,b)

L=length(a);

if L=10%確定交叉寬度

W=1;

elseif ((L/10)-floor(L/10))=randL10

W=ceil(L/10);

else

W

網(wǎng)頁名稱：貨郎擔問題java代碼,貨郎擔問題例題
路徑分享：http://jinyejixie.com/article46/hsioeg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導航、、軟件開發(fā)、自適應網(wǎng)站、網(wǎng)站設計公司、網(wǎng)站建設

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)