求貨郎擔(dān)問題的matlab算法

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

十余年的監(jiān)利網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對設(shè)計(jì)、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都營銷網(wǎng)站建設(shè)的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整監(jiān)利建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)建站從事“監(jiān)利網(wǎng)站設(shè)計(jì)”,“監(jiān)利網(wǎng)站推廣”以來，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

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

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

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

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

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

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

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

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

[N,NN]=size(D);

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

for i=1:n

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

end

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

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

fitness=zeros(n,1);%存儲(chǔ)歸一化適應(yīng)值

counter=0;

while counterc

for i=1:n

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

end

maxlen=max(len);

minlen=min(len);

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

rr=find(len==minlen);

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

FARM=farm;%優(yōu)勝劣汰，nn記錄了復(fù)制的個(gè)數(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

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

資料：

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

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

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

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

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

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

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

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

算法：

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

優(yōu)化方法：

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

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

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

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

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

當(dāng)算法結(jié)束時(shí)，回路上的每一個(gè)點(diǎn)相對于其它點(diǎn)都是最優(yōu)，即回路達(dá)到其局部極值。

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

概念：

跨線：在回路中，連線兩個(gè)不相鄰點(diǎn)，且中間只有一個(gè)點(diǎn)，這個(gè)中間點(diǎn)是該連線的起點(diǎn)和終點(diǎn)的相鄰點(diǎn)，該連線稱跨線。例如，在回路A－B－C－D－E－F－G－A中，A與B、B與C等都是相鄰點(diǎn)，則連線AC連接了不相鄰點(diǎn)A和C，且其中間只有一個(gè)點(diǎn)B，而點(diǎn)B是A的相鄰點(diǎn)，也是C的相鄰點(diǎn)，故連線AC是跨線。

邊：兩個(gè)相鄰點(diǎn)之間的連線，如上面A與B的連線，B與C的連線都是邊。

路徑變化量：將某一點(diǎn)連入路徑中，就是要把該點(diǎn)與路徑中的某一條邊的起點(diǎn)和終點(diǎn)相連，以這兩條新的邊取代原來的邊；這樣，新的兩條邊長(權(quán)重)之和與原來邊長(權(quán)重)的差就是將該連入路徑后引入路徑長(總權(quán)重)的變化量，稱路徑變化量。例如，將點(diǎn)D插入回路A－B－C－E－F－G－A的邊EF中，實(shí)際上就是將ED和DF相連，用新的邊ED和DF取代原來的邊EF，由此引起的路徑變化量，即回路A－B－C－E－F－G－A與回路A－B－C－E－D－F－G－A的總長度(總權(quán)重)之差等于兩條新邊的長度(權(quán)重)之和減原來邊的邊長(權(quán)重)，即等于ED＋DF－EF。

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

幾點(diǎn)說明和補(bǔ)充：

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

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

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

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

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

(6)本算法是以有向圖給出的，因而，在計(jì)算路徑變化量時(shí)運(yùn)用了嚴(yán)格的符號順序，其方向?yàn)椋鹤筮吺蔷€段的起點(diǎn)，右邊是線段的終點(diǎn)，例如，線A－B表示A為起點(diǎn)而B為終點(diǎn)。但算法也適用于無向圖，所給實(shí)例即為無向圖。

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

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

什么是商旅問題啊？用c語言設(shè)計(jì)，是關(guān)于圖的程序。最好能給出代碼

旅行商問題（Traveling Saleman Problem，TSP）又譯為旅行推銷員問題、貨郎擔(dān)問題，簡稱為TSP問題，是最基本的路線問題，該問題是在尋求單一旅行者由起點(diǎn)出發(fā)，通過所有給定的需求點(diǎn)之后，最后再回到原點(diǎn)的最小路徑成本。字面上的理解是：有一個(gè)推銷員，要到n個(gè)城市推銷商品，他要找出一個(gè)包含所有n個(gè)城市的具有最短路程的環(huán)路。

解決TSP問題的思想有回溯法、貪心法、動(dòng)態(tài)規(guī)劃法等。

如果動(dòng)態(tài)規(guī)劃法解決TSP問題，可以參考程序代碼：

#include list

#include iostream

using namespace std ;

typedef listint LISTINT;

LISTINT listAnother;

LISTINT list_result;

int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}};

int matrix_length=4;

int getPath(int n,LISTINT list_org)

{

LISTINT::iterator i;

int minValue;

if(n==1)

{

i=list_org.begin();

minValue= d[*i-1][0];

if(list_org.size()==matrix_length-1)

{

list_result=list_org;

}

}

else

{

int temp;

i=list_org.begin();

temp=*i;

list_org.erase(i);

i=list_org.begin();

minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org);

if(list_org.size()==matrix_length-1)

{

list_result=list_org;

}

for(int j=2;jn;j++)

{

i=list_org.begin();

for(int k=1;kj;k++)

{

i++;

}

int tempvalue=*i;

list_org.erase(i);

list_org.push_front(tempvalue);

i=list_org.begin();

tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org);

if(tempvalueminValue)

{

if(list_org.size()==matrix_length-1)

{

list_result=list_org;

}

minValue=tempvalue;

}

}

}

return minValue;

}

int main(int argc, char* argv[])

{

LISTINT list_org;

LISTINT::iterator h;

list_org.push_front(4);

list_org.push_front(3);

list_org.push_front(2);

list_org.push_front(1);

cout"旅行商問題動(dòng)態(tài)規(guī)劃算法"endl;

cout"路線長度的矩陣表示如下 （-1表示無限大）"endl;

for(int j=0;jmatrix_length;j++){

coutendl;

for(int k=0;kmatrix_length;k++){

cout" "d[j][k];

}

}

coutendl;

cout"計(jì)算結(jié)果:"getPath(4,list_org)endl;

list_result.push_front(1);

list_result.push_back(1);

cout"要走的路徑:----:";

for (h = list_result.begin(); h != list_result.end(); ++h)

cout *h " ";

cout endl;

int i;

cini;

return 0;

}

用貪婪法求解“貨郎擔(dān)問題”

//用貪心法實(shí)現(xiàn)TSP問題如下：

#include iostream.h

int c[5][5]; //保存權(quán)值

int cp[5]; //保存路徑

bool arrived[5]; // 判斷是否經(jīng)過點(diǎn)

void main()

{

int i,j,p=0,w=0;

int tmp;

cout"請輸入鄰接矩陣"endl;

for(i=0;i5;i++)

for(j=0;j5;j++)

cinc[i][j]; //輸入鄰接矩陣

for(i=0;i5;i++)

{

for(j=0;j5;j++)

cout" "c[i][j];

coutendl;

} //輸出鄰接矩陣

arrived[0]=true;

cp[0]=1;

for(i=1;i5;i++)

arrived[i]=false;

for(i=1;i5;i++)

{

for(int k=0;(arrived[k]);k++)

tmp=c[p][k+1];

for(j=k+1;j5;j++)

if((!arrived[j])(tmpc[p][j]))

{

k=j;

tmp=c[p][j];

}

cp[i]=k+1;

arrived[k]=true;

p=k;

w=w+tmp;

}

w=w+c[p][0];

cout"w="wendl;

for(i=0;i5;i++)

cout" "cp[i];

cout" "cp[0]endl;

}

本文標(biāo)題：貨郎問題java代碼,貨郎擔(dān)問題c語言
網(wǎng)頁網(wǎng)址：http://chinadenli.net/article46/dsgjgeg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、商城網(wǎng)站、搜索引擎優(yōu)化、服務(wù)器托管、動(dòng)態(tài)網(wǎng)站、手機(jī)網(wǎng)站建設(shè)

廣告

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