長(zhǎng)江水污染-數(shù)學(xué)建模期末作業(yè)

2010年數(shù)學(xué)建模

機(jī)電工程學(xué)院08機(jī)械

上課時(shí)間周五下午一二節(jié)

組員：陳燕毫200800840009

郭玉柱200800840038

張千里200800840224

最優(yōu)線路設(shè)計(jì)的數(shù)學(xué)模型

一.問(wèn)題的重述和分析

最優(yōu)線路設(shè)計(jì)

某貨運(yùn)公司，倉(cāng)庫(kù)地點(diǎn)見(jiàn)圖1中的紅色小圓圈，某送貨員需將一批貨物從倉(cāng)

庫(kù)送至城市內(nèi)各目的地。76個(gè)位置的坐標(biāo)見(jiàn)表3,編號(hào)為1的點(diǎn)是出發(fā)點(diǎn)，編

號(hào)2-76的點(diǎn)是目的地，散點(diǎn)圖見(jiàn)圖1：紅色*號(hào)的是編號(hào)2-41目的地。藍(lán)色*號(hào)

是剩下的目的地。

1.如果76個(gè)位置之間的任意連線都是通路，請(qǐng)?jiān)O(shè)計(jì)送貨線路，使送貨距離

最短，并用畫(huà)圖的方式展示所求結(jié)果。

2.如果相互通路信息如圖2所示，請(qǐng)?jiān)O(shè)計(jì)送貨線路，使送貨距離最短，并用

畫(huà)圖的方式展示所求結(jié)果。

3.在第2問(wèn)的基礎(chǔ)上，如果每次最多帶40個(gè)目的地貨物，而且排序在前面

的目的地必須優(yōu)先送貨，請(qǐng)?jiān)O(shè)計(jì)送貨路線，使送貨距離最短，并用畫(huà)圖的

方式展示所求結(jié)果。

4.如果要求算法在普通PC上求結(jié)果不超過(guò)兩分鐘，請(qǐng)給出你的算法代碼。

圖一送貨示意圖

圖二相互聯(lián)系信息

序號(hào)X坐標(biāo)Y坐標(biāo)

136002300

231003300

347005750

454005750

556087103

644937102

736006950

831007250

947008450

1054008450

11561010053

12449210052

16540011650

1973007250

2066506950

2173003300

2266502300

2354001600

2483502300

2578503300

2694505750

27101505750

28103587103

2992437102

3083506950

3178507250

3294508450

33101508450

341036010053

35924210052

36835010800

37785010950

38945011650

391015011650

401140010800

411205010950

42120507250

43114006950

44120503300

45114002300

46101501600

47131002300

48126003300

49142005750

50149005750

51151087103

52139937102

53131006950

54126007250

55142008450

56149008450

571511010053

581399210052

591310010800

601260010950

611420011650

621490011650

631615010800

641680010950

65168007250

66161506950

67168003300

68161502300

69149001600

7019800800

711980010000

721980011900

731980012200

7420012200

752001100

76200800

表三：坐標(biāo)信息

二、模型的分析

最短路問(wèn)題是最重要的最優(yōu)化問(wèn)題之一，也是圖論研

究中的一個(gè)經(jīng)典算法問(wèn)題。最短路問(wèn)題在現(xiàn)實(shí)生活和生產(chǎn)中

有著廣泛的應(yīng)用。例如各種管道的鋪設(shè)，線路的安排，廠區(qū)

的選擇和布局，設(shè)備的更新等。它還經(jīng)常被作為一種基本工

具，用于解決其他的最優(yōu)化問(wèn)題以及預(yù)測(cè)和決策問(wèn)題。歷史

上曾經(jīng)出現(xiàn)過(guò)各種各樣的最短路問(wèn)題，例如上世紀(jì)60年代

中國(guó)數(shù)學(xué)家管梅谷提出的“中國(guó)郵遞員問(wèn)題”，還有數(shù)學(xué)家

Hamilton在1859年提出的“環(huán)球航行”問(wèn)題，“旅行售貨員

問(wèn)題”。

該問(wèn)題要求設(shè)計(jì)三種不同情況下的最短送貨線路。實(shí)質(zhì)

是在滿(mǎn)足題目要求的可以遍歷所有76點(diǎn)的通路中通過(guò)數(shù)學(xué)

建模求解出最短的一條。問(wèn)題一給定一個(gè)點(diǎn)，要求從該點(diǎn)開(kāi)

始，遍歷所有其余75個(gè)點(diǎn)，并選擇出距離最短的路線，其

中題目中給定的76個(gè)點(diǎn)之中的任意兩個(gè)點(diǎn)都可以形成通路。

題目二與題目一得區(qū)別在于，題目二中的每個(gè)點(diǎn)只與有限個(gè)

剩余點(diǎn)之間可以形成通路。題目三中規(guī)定每次送貨時(shí)最多只

能攜帶40個(gè)目的地的貨物，并且排序在前面的目的地必須

優(yōu)先送貨。

三、模型假設(shè)和符號(hào)說(shuō)明

⑴規(guī)定題目中所用的的點(diǎn)用符號(hào)i(；1,2,3,….)來(lái)表示。

用d(i,j)表示第i和第j個(gè)點(diǎn)之間的距離。當(dāng)i,j兩個(gè)點(diǎn)之

間連通時(shí)，則兩點(diǎn)之間的距離即為兩點(diǎn)間的實(shí)際距離；當(dāng)兩

點(diǎn)不連通時(shí)，則距離為無(wú)窮大。

⑵為求解最短距離的通路，從;1的點(diǎn)出發(fā)，從剩余的75

個(gè)點(diǎn)中間選擇距離最近的一點(diǎn)，記該距離為S1。然后從該點(diǎn)

出發(fā)，按上述方法尋找下一個(gè)最短距離，記為s2o依次進(jìn)行,

求得S3,S4,S5,…,S75o則最短距離為S1+S2+S3+…+S75,

記為SUM。則SUM為所求。

⑶假設(shè)任意兩點(diǎn)之間的通路都為直線。

⑷在求解過(guò)程中，從i點(diǎn)執(zhí)行之后，訪問(wèn)第i+1點(diǎn)時(shí)，不

考慮i+1點(diǎn)之后的點(diǎn)對(duì)i+1點(diǎn)的選擇。

四、模型的建立和求解

(一)問(wèn)題1.如果76個(gè)位置之間的任意連線都是通路，請(qǐng)?jiān)O(shè)計(jì)送

貨線路，使送貨距離最短，并用畫(huà)圖的方式展示所求結(jié)果。

從i=l的點(diǎn)也就是第一個(gè)點(diǎn)，尋找與之距離最近的下一

個(gè)點(diǎn)，記該距離為S1。然后尋找與該點(diǎn)距離最近的下一個(gè)點(diǎn),

求得距離S2,依照此步驟，求得S3,S4,…，S75。

具體方法：首先建立一個(gè)表示第i點(diǎn)到任一點(diǎn)之間距離的矩

陣，記為然后從第一個(gè)點(diǎn)開(kāi)始，依次遍歷其余75

個(gè)點(diǎn)取與第一個(gè)點(diǎn)距離最小的點(diǎn)k,并把第k點(diǎn)的橫坐標(biāo)保

存在x矩陣，把縱坐標(biāo)保存在y矩陣，同時(shí)把其它點(diǎn)與第一

個(gè)點(diǎn)的距離置無(wú)窮大。然后從第k個(gè)點(diǎn)開(kāi)始依次遍歷剩余75

個(gè)點(diǎn)則最短距離SUM即為SUM=S1+S2+S3+….+S75。求解該問(wèn)

題的算法如下，

用Matlab軟件的該最短路徑如下：

基本路徑為：

1-2-23-22-21-25-24-46-45-44-48-47-69-68-67-50-49-52

-53-54-42-43-28-29-30-31-19-20-5-6-7-8-9-10-11-12-1

3-14-15-16-17-18-37-36-35-34-40-41-60-59-58-57-63-6

4-62-61-55-56-52-51-66-65-71-72-73-39-38-32-33-27-2

6-43-75-76-74-70o

最短距離為1.3719e+005o

模型分析：根據(jù)以上方法求得的Matlab圖形，可以看出路

徑存在交叉，明顯不構(gòu)成歐拉回路，因此此算法求得的路徑

并非最短，有待改進(jìn)。由上圖可以看出，對(duì)最短路徑影響較

大的點(diǎn)是位于邊緣上的第70-76點(diǎn)。

模型改進(jìn)：

方法一：可以通過(guò)適當(dāng)修改路徑，當(dāng)?shù)竭_(dá)邊緣附近的點(diǎn)時(shí)，

由邊緣點(diǎn)距離較近的點(diǎn)直接訪問(wèn)邊緣上的點(diǎn)，然后從該邊緣

點(diǎn)繼續(xù)向下執(zhí)行。

基本路徑大致與原圖相似。

方法改進(jìn)后最短路徑為1.0053e+005o

方法二：可以通過(guò)對(duì)所有的點(diǎn)分布圖進(jìn)行分區(qū)。如可以對(duì)整

個(gè)圖分成若干區(qū)，運(yùn)輸路徑先將第一區(qū)所有點(diǎn)訪問(wèn)完之后，

再進(jìn)入下一區(qū)，依次遍歷所有的點(diǎn)。這種方法可以有效縮小

邊緣點(diǎn)對(duì)最短路徑的影響。

把所有點(diǎn)分成7個(gè)區(qū)之后，效果可見(jiàn)下圖：

基本路徑大致為由第1點(diǎn)開(kāi)始依次順序執(zhí)行到76點(diǎn)。

最短路徑為1.4835e+005o

路徑變大的原因可能是分區(qū)不合適。

（二）如果相互通路信息如圖2所示，請(qǐng)?jiān)O(shè)計(jì)送貨線路，使送貨距離

最短，并用畫(huà)圖的方式展示所求結(jié)果

每個(gè)點(diǎn)與有限個(gè)點(diǎn)連通。首先建立一個(gè)表示第i個(gè)點(diǎn)

到第j個(gè)點(diǎn)是否有通路的矩陣。例如第一行

c={l,2,22,23,75,76}表示第一個(gè)點(diǎn)與第2、22、23、75、76

之間有通路，依舊采用與問(wèn)題一相同的方法，分別比較第1

個(gè)點(diǎn)與第2、22、23、75、76點(diǎn)之間的距離，取最小值，如

22點(diǎn),然后從22點(diǎn)依次比較與22點(diǎn)有通路的點(diǎn)，取得與其

距離最短的點(diǎn)。按照同樣的方法直到所有點(diǎn)都比較完畢，構(gòu)

成一個(gè)循環(huán)回路。用Matlab繪制的圖形如下：

開(kāi)始遍歷執(zhí)行到第55點(diǎn)時(shí)，出現(xiàn)了死點(diǎn)，即與第55點(diǎn)有通

路的所有點(diǎn)都已經(jīng)遍歷。第55點(diǎn)找不到下一點(diǎn)。分析其原

因可能是只考慮最短路徑，沒(méi)有考慮第i點(diǎn)的選擇對(duì)以后點(diǎn)

選擇的影響。

模型改進(jìn):

方法一：可以采用分區(qū)的方法，根據(jù)死點(diǎn)的位置進(jìn)行合理

的分區(qū)，可以有效避免死點(diǎn)的出現(xiàn)，但是這種方法用程序?qū)?/p>

現(xiàn)比較困難，因此這種方法并非一種實(shí)際的方法。

方法二：分析死點(diǎn)出現(xiàn)的原因，主要是由于采用“貪

心法”時(shí)對(duì)路徑的選擇不考慮可持續(xù)性。因此，在“貪心法”

的基本框架下，可以采用設(shè)置優(yōu)先訪問(wèn)權(quán)的辦法，即到達(dá)死

點(diǎn)附近時(shí)優(yōu)先訪問(wèn)死點(diǎn)！止匕外，考慮到問(wèn)題一中邊緣點(diǎn)對(duì)最

短路徑的影響，在設(shè)置死點(diǎn)優(yōu)先訪問(wèn)權(quán)的同時(shí)，也對(duì)邊緣點(diǎn)

設(shè)置優(yōu)先訪問(wèn)權(quán)。

用Matlab繪制的圖形如下：

此時(shí)的訪問(wèn)順序：

1-2-23-22-21-25-24-46-45-44-48-47-69-68-70-67-50-51

-66-65-56-55-52-49-53-54-42-43-27-28-33-32-29-26-30

-31-19-20-4-3-6-5-10-9-7-8-12-11-17-18-37-36-35-34-

40-41-60-59-58-57-63-64-71-72-73-62-61-39-38-16-15-

74-75-76o

改進(jìn)后路徑距離為：1.3725e+005

（三）在第2問(wèn)的基礎(chǔ)上，如果每次最多帶40個(gè)目的地貨物,

而且排序在前面的目的地必須優(yōu)先送貨，請(qǐng)?jiān)O(shè)計(jì)送貨路線，

使送貨距離最短，并用畫(huà)圖的方式展示所求結(jié)果。

按照題目要求，每次最多攜帶40個(gè)目的地的貨物，即

1-40點(diǎn)的目的地。為了實(shí)現(xiàn)此路徑，可采用問(wèn)題一的改進(jìn)方

法，即采用分區(qū)的方法，將前40個(gè)點(diǎn)列在第一區(qū)，其余的

點(diǎn)放在第二區(qū)。首先由1點(diǎn)出發(fā)，依舊采用“貪心法”，依

次遍歷前40個(gè)點(diǎn)后，回到出發(fā)點(diǎn)，獲得最小路徑。然后，

再由原點(diǎn)攜帶剩余36個(gè)點(diǎn)的貨物，依次遍歷剩余36個(gè)點(diǎn)，

再次得到一個(gè)最小路徑。最終，將兩次最小路徑求和，便得

到總的最小路徑。用Matlab繪制圖形如下：

分步路徑一：

12000

0-----------------------!-----------!-----------1--------!--------!--------1--------1--------

3000400050006000700080009000100001100012000

分步路徑二:

分步路徑組合:

模型分析：在程序編寫(xiě)過(guò)程中出現(xiàn)多處死點(diǎn)，在程序編寫(xiě)過(guò)

程中有較大困難，可以通過(guò)下面的方法對(duì)算法進(jìn)行改進(jìn)。

在原題假設(shè)基礎(chǔ)上，再添加如下假設(shè)：1、路徑由原點(diǎn)

出發(fā)到達(dá)下一點(diǎn)時(shí)，不考慮原點(diǎn)與此點(diǎn)的通路限制。2、由

最終一點(diǎn)返回原點(diǎn)時(shí)，忽略通路限制，直接返回原點(diǎn)。3、

在Matlab繪圖過(guò)程中，如出現(xiàn)死點(diǎn)，則在死點(diǎn)附近一點(diǎn)設(shè)

置對(duì)死點(diǎn)的優(yōu)先訪問(wèn)權(quán)。

改進(jìn)之后，不再出現(xiàn)死點(diǎn)，并且得到的路徑較優(yōu)。

模型改進(jìn)：依舊可以采用分區(qū)和設(shè)置優(yōu)先路徑的方法對(duì)模型

進(jìn)行改進(jìn)。但是程序編寫(xiě)有較大難度。還可以采用其它求解

最短路徑的方法。

結(jié)束語(yǔ)：本次模型的建立采用的主要方法是“貪心法”和

圖論中關(guān)于求解最短路徑的方法。模型建立時(shí)首先采用依次

尋找最近點(diǎn)的貪心法，但是此方法存在較大的不足。這種方

法只考慮下一點(diǎn)的選擇，而忽略下一點(diǎn)后其它點(diǎn)對(duì)此點(diǎn)選擇

的影響，這也是造成第二，三問(wèn)中出現(xiàn)死點(diǎn)的原因。針對(duì)此

問(wèn)題，對(duì)模型進(jìn)行了適當(dāng)?shù)母倪M(jìn)，方法主要是分區(qū)和設(shè)置優(yōu)

先訪問(wèn)路徑。

參考書(shū)目：《數(shù)學(xué)建模的實(shí)踐》高教版

《應(yīng)用運(yùn)籌學(xué)》浙江大學(xué)出版社

《圖論簡(jiǎn)明教程》清華大學(xué)出版社

《圖論及其應(yīng)用》高教版

《圖論》北京理工大學(xué)出版社

《中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽》高教版

《matlab與數(shù)學(xué)建?；A(chǔ)教程》高教版

《matlab繪圖基礎(chǔ)》

附錄

注：由于問(wèn)題要求不同，有些程序根據(jù)要求進(jìn)行了相應(yīng)修改,

可能有重復(fù)現(xiàn)象。

其中fun_create_b(),fun_shorway()是問(wèn)題二三均調(diào)用到

的子程序，funcheck(),funmodify_all_b()是問(wèn)題二中使

用到的子程序。

問(wèn)題一原代碼

functiony=funl(c)

%此程序由坐標(biāo)陣a生成距離陣b,經(jīng)過(guò)路徑選擇生成%

最小路徑圖

a=[3600,2300;3100,3300;4700,5750;5400,5750;5608,710

3;4493,7102;3600,6950;3100,7250;4700,8450;5400,8450

;5610,10053;4492,10052;3600,10800;3100,10950;4700,1

1650;5400,11650;6650,10800;7300,10950;7300,7250;665

0,6950;7300,3300;6650,

2300;5400,1600;8350,2300;7850,3300;9450,5750;

10150,5750;10358,7103;9243,7102;8350,6950;

7850,7250;9450,8450;10150,8450;10360,10053;

9242,10052;8350,10800;7850,10950;9450,

11650;10150,11650;11400,10800;12050,

10950;12050,7250;11400,6950;12050,3300;

11400,2300;10150,1600;13100,2300;12600,

3300;14200,5750;14900,5750;15108,7103;

13993,7102;13100,6950;12600,7250;14200,

8450;14900,8450;15110,10053;13992,10052;

13100,10800;12600,10950;14200,

11650;14900,11650;16150,10800;16800,

10950;16800,7250;

16150,6950;16800,3300;16150,2300;14900,

1600;

19800,800;19800,10000;19800,11900;19800,

12200;200,12200;200,1100;200,800]

b二zeros(76);

fori=1:76

for尸i:76

b(i,j)=((a(i,1)-a(j,1)廠2+(a(i,2)-a(j,2)廠2)-0.5;

b(j,i)=b(i,j);

b(i,i)=inf;

end

end

n=1;

k=1；

sum1=0;

temp二zeros(1,76);

x二zeros(1,76);

y二zeros(1,76);

fori=1:75

temp(1,i)=inf;

for戶(hù)1:76

iftemp(1,i)>b(k,j)

temp(1,i)二b(k,j)

n-j；

end

iftemp(1,i)>b(j,k)

temp=b(j,k)

n=j；

end

end

sum1=suml+temp(1,i)

x(i)=a(n,1);

y⑴二a(n,2);

form=1:76

b(m,k)=inf;%

b(k,m)=inf;

end

k二n;

end

plot(x,y)

改進(jìn)方法一

functiony=gaijin(c)

%設(shè)置路徑權(quán)限

a=[3600,2300;3100,3300;。。。。200,1100;200,800]

注：方框中坐標(biāo)省略

b二zeros(76);

fori=1:76

for尸i:76

b(i,j)=((a(i,1)-a(j,1))^2+(a(i,2)-a(j,2))^2)^0.5;

b(j,i)=b(i,j);

b(i,i)=inf;

end

end

n=1;

k=1;

sum1=0;

temp=zeros(1,76);

x二zeros(1,76);

y=zeros(1,76);

x(1)=a(1,1);

y(1)=a(1,2);

fori=1:75

ifk=14

n=74;

eIseifk==62

n=73;

eIseifk-67

n=70;

eIseifk=35

n二38;

eIseifk=59

n=61;

eIsetemp(1,i)=inf;

forj=1:1:76

iftemp(1,i)>b(k,j)

temp(1,i)=b(k,j)

n=j;

end

iftemp(1,i)>b(j,k)

temp=b(j,k)

"j；

end

end

end

sum1=sum1+temp(1,i)

x(i+1)=a(n,1);

y(i+1)=a(n,2);

form=1:76

b(m,k)=inf;%

b(k,m)=inf;

end

k=n

end

plot(x,y)

改進(jìn)方法二

%此程序?qū)仃嘼進(jìn)行分塊求最短路徑

function[xx,yy]=fun_rem_a(d)

Ientt=0;

sum=0;

a=[3600,2300;3100,3300;.200,1100;200,800]

注：方框中坐標(biāo)省略

xx二zeros(1,lentt);

yy二zeros(1,lentt);

d=17

b=fun_create_b(a,d);

[x,y,sum1]un_shorway(a,b);

fori=1:d

xx⑴二x⑴；

yy⑴二y⑴；

end

fori=1:Iength(a)-d+1

a(i,1)=a(i+d-1,1);

a(i,2)=a(i+d-1,2);

end

sum=sum+suml

lentt=lentt+d;

d=7

b=fun_create_b(a,d);

[x,y,sum11un_shorway(a,b);

fori=1:d

xx(lentt+i-1)=x(i);

yy(lentt+i-1)=y(i);

end

fori=1:Iength(a)-d+1

a(i,1)=a(i+d-1,1);

a(i,2)=a(i+d-1,2);

end

sum=sum+sum1

lentt=lentt+d;

d二15

b=fun_create_b(a,d);

[x,y,sum1]=fun_shorway(a,b);

fori=1:d

xx(lentt+i-1)=x(i);

yy(lentt+i-1)=y(i);

end

fori=1:Iength(a)-d+1

a(i,1)=a(i+d-1,1);

a(i,2)=a(i+d—1,2);

end

sum=sum+suml

lentt=lentt+d;

d二9

b=fun_create_b(a,d);

[x,y,sum1]un_shorway(a,b);

fori=1:d

xx(lentt+i-D=x(i);

yy(lentt+i-1)=y(i);

end

fori=1:length(a)-d+1

a(i,1)=a(i+d-1,1);

a(i,2)=a(i+d—1,2);

end

sum=sum+sum1

lentt=lentt+d;

d=19

b=fun_create_b(a,d);

[x,y,sum1]un_shorway(a,b);

fori=1:d

xx(lentt+i-D=x(i);

yy(lentt+i-1)=y(i);

end

fori=1:length(a)-d+1

a(i,1)=a(i+d-1,1);

a(i,2)=a(i+d—1,2);

end

sum=sum+suml

lentt=lentt+d;

d二8

b=fun_create_b(a,d);

[x,y,sum1]un_shorway(a,b);

fori=1:d

xx(Ientt+i-1)=x(i);

yy(lentt+i-1)=y(i);

end

fori=1:Iength(a)-d+1

a(i,1)=a(i+d-1,1);

a(i,2)=a(i+d-1,2);

end

sum=sum+suml

lentt=lentt+d;

d=7

b=fun_create_b(a,d);

[x,y,sum11un_shorway(a,b);

fori=1:d

xx(lentt+i-1)=x(i);

yy(lentt+i-1)=y(i);

end

fori=1:Iength(a)-d+1

a(i,1)=a(i+d-1,1);

a(i,2)=a(i+d-1,2);

end

lentt=lentt+d;

sum=sum+suml

plot(xx,yy);

end

子程序1

function[b]=fun_create_b(a,d)

%此程序由矩陣a生成距離陣b,在問(wèn)題一二三中均有使用，％

此處作為獨(dú)立函數(shù)寫(xiě)出，方便運(yùn)算過(guò)程中主程序調(diào)用

Ien二d

b二zeros(Ien);

fori=1:Ien

forj=i:len

b(i,j)=((a(i,1)-a(J,1))”+(a(i,2)-a(j,2))”)".5;

b(j,i)=b(i,j);

b(i,i)=inf;

end

end

b=fun_aII(1,b);

end

子程序2

function[x,y,sum1]=fun_shorway(a,b)

%此程序由矩陣a及相應(yīng)的距離陣b,求出最短路徑，并輸出％

圖形

%此處作為獨(dú)立函數(shù)寫(xiě)出，方便運(yùn)算過(guò)程中主程序調(diào)用

Ient二length(b)%定義lent記錄矩陣b的長(zhǎng)度

n=1;%定義變量n記錄每個(gè)點(diǎn)的最短距離點(diǎn)

k=1;%定義變量k作為路徑尋找中的指示器

sum1=0;%定義路徑長(zhǎng)度記錄器sum1

x二zeros(1,lent);%定義行矩陣x記錄路徑中每

個(gè)%點(diǎn)的橫坐標(biāo)

y=zeros(1,lent);%定義行矩陣y記錄路徑中每個(gè)點(diǎn)的縱

%坐標(biāo)

x(1,1)=a(1,1)%定義起始點(diǎn)橫坐標(biāo)

y(1,1)=a(1,2)%定義起始點(diǎn)縱坐標(biāo)

fori=1:(Ient-1)

replace=inf;%定義replace作為

尋%找最近距離點(diǎn)的暫存器

forj=1:1:Ient%循環(huán)lent次，遍歷剩余點(diǎn)與當(dāng)

%前點(diǎn)的所有距離

ifrepIace>b(k,j)%如果j與當(dāng)前點(diǎn)k的

%距離小于repIace,用

repIace=b(k,j);%b(k,j)替換replace

n=j；

end

ifrepIace>b(j,k)

repIace=b(j,k);%同上

n=j；

end

end

sum1=sum1+repIace;%路徑疊加

x(1,i+1)=a(n,1);%記錄最近距離點(diǎn)的行坐標(biāo)

y(1,i+D=a(n,2);%記錄最近距離點(diǎn)的縱坐標(biāo)

form=1:Ient

b(m,k)=inf;%如果路徑已通過(guò)該點(diǎn)，那么把該點(diǎn)

%與其他所有

b(k,m)=inf;%點(diǎn)的距離設(shè)為inf,防止路徑重復(fù)。

end

k-n;%把尋找到的點(diǎn)作為路徑出發(fā)點(diǎn)，開(kāi)始尋找下一

end

plot(x,y)%輸出圖形

問(wèn)題二：

源程序：

functiony=fun_path2(f)

a二[3600,2300;31....200,12200;200,1100;200,

800]注：方框中坐標(biāo)省略

[b]=fun_create_b(a,76)%由矩陣a創(chuàng)建距離矩

陣b

[b]=fun_modify_aIl_b(b)%根據(jù)題中第二問(wèn)給出路

%徑限制修改b中距離信息

fun_shorway(a,b)%生成最小路徑圖

end

子程序1

function[b]=fun_create_b(a,d)

Ien=d

b二zeros(Ien);

fori=1:Ien

forj二i:len

b(i,j)二((a(i,1)-a(j,1)廠2+(a(i,2)-a(j,2)12)-0.5;

b(j,i)=b(i,j);

b(i,i)=inf;

end

end

%b=fun_aII(1,b);

End

子程序2

function[b]un_modify_aII_b(b)

%此程序根據(jù)問(wèn)題二中的條件，對(duì)矩陣b中的路徑進(jìn)行限制

%無(wú)路徑的點(diǎn)與點(diǎn)之間的距離將被修改為無(wú)窮大。

%調(diào)用fun_check的函數(shù)逐行修改b中的距離。

C=[1,2,22,23,75,76];

[b]=fun_check(c,b);

c=[2,1,3,4,7,8,22,23,75];

[b]=fun_check(c,b);

c=[3,2,4,6,7];

[b]=fun_check(c,b);

c=[4,2,3,5,6,20,21,22];

[b]=fun_check(c,b);

c=[5,4,6,9,10,20];

[b]=fun_check(c,b);

c=[6,3,4,5,7,9];

[b]=fun_check(c,b);

c=[7,2,3,6,8,9];

[b]=fun_check(c,b);

c=[8,2,7,9,12,13,14,74,75];

[b]=fun_check(c,b);

c=[9,5,6,7,8,10,12];

[b]二千un_check(c,b);

c=[10,5,9,11,12,19,20];

[b]=fun_check(c,b);

c=[11,10,12,16,17,19];

[b]=fun_check(c,b);

C二[12,8,9,10,11,13,15,16];

[b]=fun_check(c,b);

c二[13,8,12,14,15];

[b]=fun_check(c,b);

c二[14,8,13,15,74];

[b]=fun_check(c,b);

c二『5,12,13,14,16,74];

[b]=fun_check(c,b);

c=[16,11,12,15,17,18,19,38,74];

[b]=fun_check(c,b);

c=[17,11,16,18,19];

[b]=fun_check(c,b);

c=[18,16,17,19,36,37,38];

[b]=fun_check(c,b);

c=[19,10,11,17,18,20,30,31,36];

[b]=fun_check(c,b);

c=[20,4,5,10,19,21,30];

[b]=fun_check(c,b);

c二⑵，4,20,22,24,25,30];

[b]=fun_check(c,b);

c=[22,l,2,4,21,23,24];

[b]=fun_check(c,b);

c=[23,l,22,24,46,76];

[b]=fun_check(c,b);

c=[24,21,22,23,25,45,46];

[b]=fun_check(c,b);

c=[25,21,24,26,27,30,45];

[b]=fun_check(c,b);

c=[26,25,27,29,30];

[b]=fun_check(c,b);

c=[27,25,26,28,29,44,45];

[b]=fun_check(c,b);

c=[28,27,29,32,33,43];

[b]=fun_check(c,b);

c=[29,26,27,28,30,32]；

[b]=fun_check(c,b);

c=[30,l9,20,21,25,26,29,31,32]；

[b]=fun_check(c,b);

c=[31,19,30,32,35,36]；

[b]=fun_check(c,b);

c=[32,28,29,30,31,33,35];

[b]=fun_check(c,b);

c=[33,28,32,34,35,42,43];

[b]=fun_check(c,b);

c=[34,33,35,39,40,42];

[b]=fun_check(c,b);

c=[35,31,32,33,34,36,38,39];

[b]=fun_check(c,b);

C=[36,18,19,31,35,37,38];

[b]=fun_check(c,b);

c=[37,18,36,38];

[b]=fun_check(c,b);

c=[38,l8,35,36,37,39,74];

[b]=fun_check(c,b);

c=[39,34,35,38,40,41,61,73,74];

[b]=fun_check(c,b);

c=[40,34,42,60,61];

[b]=fun_check(c,b);

c=[41,39,40,42,59,60,61];

[b]=fun_check(c,b);

c=[42,33,34,40,41,43,53,54,59];

[b]=fun_check(c,b);

c=[43,27,28,33,42,44,53];

[b]=fun_check(c,b);

c=[44,27,43,45,47,48,53];

[b]=fun_check(c,b);

c=[45,24,25,27,44,46,47];

[b]=fun_check(c,b);

c=[46,23,24,45,47,69,70,76];

[b]=fun_check(c,b);

C=[47,44,45,46,48,68,69];

[b]=fun_check(c,b);

C=[48,44,47,49,50,53,68];

[b]=fun_check(c,b);

c=[49,48,50,52,53];

[b]=fun_check(c,b);

c=[50,48,49,51,52,66,67,68];

[b]=fun_check(c,b);

c=[51,50,52,55,56,66];

[b]=fun_check(c,b);

c=[52,49,50,51,53,55];

[b]=fun_check(c,b);

c=[53,42,43,44,48,49,52,54,55];

[b]=fun_check(c,b);

c=[54,42,53,55,58,59];

[b]=fun_check(c,b);

c=[55,51,52,53,54,56,58];

[b]=fun_check(c,b);

c=[56,51,55,57,58,65,66];

[b]=fun_check(c,b);

c=[57,56,58,62,63,65];

[b]=fun_check(c,b);

c=[58,54,55,57,59,61,62];

[b]=fun_check(c,b);

C=[59,41,42,54,58,60,61];

[b]=fun_check(c,b);

c=[60,41,59,61];

[b]=fun_check(c,b);

C=[61,39,41,58,59,60,62,73];

[b]=fun_check(c,b);

c=[62,57,58,61,63,64,73];

[b]=fun_check(c,b);

c=[63,57,62,64,65];

[b]=fun_check(c,b);

c=[64,62,63,65,71,72,73];

[b]=fun_check(c,b);

c=[65,56,57,63,64,66,67,70,71];

[b]=fun_check(c,b);

c=[66,50,51,56,65,67];

[b]=fun_check(c,b);

c=[67,50,65,66,68,70];

[b]=fun_check(c,b);

c=[68,47,48,50,67,69,70];

[b]=fun_check(c,b);

c=[69,46,47,68,70];

[b]=fun_check(c,b);

c=[70,46,65,67,68,69,71,76];

[b]=fun_check(c,b);

c=[71,64,65,70,72];

[b]=fun_check(c,b);

c=[72,64,70,73];

[b]=fun_check(c,b);

c=[73,39,61,62,64,71,74];

[b]=fun_check(c,b);

C=[74,8,14,15,16,38,73,75];

[b]=fun_check(c,b);

c=[75,l,2,8,74,76];

[b]=fun_check(c,b);

c=[76,l,23,46,70,75];

[b]=fun_check(c,b);

End

子程序2

fun_check()

function[bj=fun_check(c,b)%此函數(shù)fun_check修改矩

陣％b,根據(jù)問(wèn)題2使沒(méi)有路徑的兩點(diǎn)之間距離設(shè)為無(wú)窮大

(inf)

len=length(c);

iflen<9

fori=len+l:9

c(i)=0;

end

end

t=c(l);

fori=l:76

ifi==c(9)Ii==c(2)Ii==c(3)Ii==c(4)Ii==c(5)Ii==c(6)

Ii==c(7)Ii==c(8)

b(t,i)=b(t,i);

else

b(t,i)=inf;

end

end

end

子程序3

function[x,y,suml]=fun_shorway(a,b)

%此函數(shù)實(shí)現(xiàn)給定坐標(biāo)陣a,距離陣b的最小路徑，并輸出

%圖形

lent=length(b)%定義lent記錄矩陣b的

長(zhǎng)度

n=l;%定義變量n記錄每

個(gè)％點(diǎn)的最短距離點(diǎn)

k=l;%定義變量k作為路

徑％尋找中的指示器

suml=O;%定義路徑長(zhǎng)度記錄器

suml

x=zeros(l,lent);%定義行矩陣X記錄路徑中

每％個(gè)點(diǎn)的橫坐標(biāo)

y=zeros(l,lent);%定義行矩陣y記錄路徑中

每％個(gè)點(diǎn)的縱坐標(biāo)

x(l,l)=a(l,l)%定義起始點(diǎn)橫坐標(biāo)

y(l,l)=a(l,2)%定義起始點(diǎn)縱坐標(biāo)

fori=l:(lent-l)

replace=inf;%定義replace作為尋找

最%近距離點(diǎn)的暫

存器

forj=l:l:lent%循環(huán)lent次，遍歷剩余點(diǎn)

與％當(dāng)前點(diǎn)的所有距離

ifreplace>b(k,j)%如果j與當(dāng)前點(diǎn)k的距離小于

replace,用

replace=b(k,j);%b(k,j)替換replace

n=j；

end

ifreplace>b(j,k)

replace=b(j,k);%同上

n=j；

end

end

sum1=suml+replace;%路徑疊加

x(l,i+l)=a(n,l);%記錄最近距離點(diǎn)的行坐標(biāo)

y(l,i+l)=a(n,2);%記錄最近距離點(diǎn)的縱坐標(biāo)

form=l:lent

b(m,k)=inf;%如果路徑已通過(guò)該點(diǎn)，那么把

該％點(diǎn)與其他所有

b(k,m)=inf;%點(diǎn)的距離設(shè)為inf,防止路徑重復(fù)。

end

k=n;%把尋找到的點(diǎn)作為路徑出發(fā)點(diǎn)，開(kāi)始尋找下一點(diǎn)

end

plot(x,y)%輸出圖形

改進(jìn)程序

function[suml]=fun_path2(f)

a=[3600,23001100.......200,800]注：方框中坐標(biāo)省略

[b]=fun_create_b(a,76)%由矩陣a創(chuàng)建距離矩陣

b

[b]=fun_modify_all_b(b)%根據(jù)題中第二問(wèn)給出路徑

限％制修改b中距離信息

[x,y,suml]=fun_shorway(a,b)%生成最小路徑

圖

End

子程序3

function[x,y,suml]=fun_shorway(a,b)

lent=length(b)%定義lent記錄矩陣b的長(zhǎng)度

n=l;%定義變量n記錄每個(gè)點(diǎn)的最短距離點(diǎn)

k=l;%定義變量k作為路徑尋找中的指示器

suml=0;%定義路徑長(zhǎng)度記錄器suml

x=zeros(l,lent);%定義行矩陣x記錄路徑中每個(gè)點(diǎn)的橫坐標(biāo)

y=zeros(l,lent);%定義行矩陣y記錄路徑中每個(gè)點(diǎn)的縱坐標(biāo)

x(l,l)=a(l,l)%定義起始點(diǎn)橫坐標(biāo)

y(l,l)=a(l,2)%定義起始點(diǎn)縱坐標(biāo)

fori=l:(lent-l)

replace=inf;%定義replace作為尋找最近距離點(diǎn)

的％暫存器

ifk==50

n=51;

elseifk==52

n=49;

elseifk==43

n=27;

elseifk==27

n=28;

elseifk==28

n=33;

elseifk==29

n=26;

elseifk==20

n=4;

elseifk==6

n=5;

elseifk==9

n=7;

elseifk==64

n=71;

elseifk==68

n=70;

else

forj=l:l:lent%循環(huán)lent次，遍歷剩余點(diǎn)與當(dāng)前

點(diǎn)％的所有距離

ifreplace>b(k,j)

replace=b(k,j);%b，j)替換replace

n=j;%

end

ifreplace>b(j,k)

replace=b(j,k);%同上

n=j；

end

end

end

sum1=sum1+replace;%路徑疊加

x(l,i+l)=a(n,l);%記錄最近距離點(diǎn)的行坐標(biāo)

y(l,i+l)=a(n,2);%記錄最近距離點(diǎn)的縱坐標(biāo)

form=l:lent

b(m,k)=inf;%如果路徑已通過(guò)該點(diǎn)，那么把

%點(diǎn)與其他所有

b(k,m)=inf;%點(diǎn)的距離設(shè)為inf,防止路徑重復(fù)。

end

k=n;

end%把尋找到的點(diǎn)作為路徑出發(fā)點(diǎn)，開(kāi)始尋找下一點(diǎn)

plot(x,y)%輸出圖形

問(wèn)題三

分步一

functiony=fun_path3_pre40(d)

a=[3600,2300;3100,3300;4700,5750;200,12200;200,1100;

200,800]注：方框中坐標(biāo)省略

[b]=fun_create_b(a,76)%由矩陣a創(chuàng)建距離矩陣b

[b]=fun_modify_all_b(b)%根據(jù)題中第二問(wèn)給出路徑

限％制修改b中距離信息

lent=40%定義lent記錄矩陣b的長(zhǎng)度

n=l;%定義變量n記錄每個(gè)點(diǎn)的最短距離點(diǎn)

k=l;%定義變量k作為路徑尋找中的指示器

suml=0;%定義路徑長(zhǎng)度記錄器

suml

x=zeros(l,lent);%定義行矩陣x記錄路徑中每個(gè)點(diǎn)的橫坐標(biāo)

y=zeros(l,lent);%定義行矩陣y記錄路徑中每個(gè)點(diǎn)的縱坐標(biāo)

x(l,l)=a(l,l)%定義起始點(diǎn)橫坐標(biāo)

y(l,l)=a(l,2)%定義起始點(diǎn)縱坐標(biāo)

fori=l:lent-l

replace=inf;%定義replace作為尋找最近距離點(diǎn)的暫存器

ifk==22

n=24;

elseifk==29

n=26;

elseifk==34

n=40;

else

forj=l:l:lent-l%循環(huán)lent次，遍歷剩余點(diǎn)

與％當(dāng)前點(diǎn)的所有距離

ifreplace>b(k,j)%如果j與當(dāng)前點(diǎn)k的距

%小于replace,用

replace=b(k,j);%b(k,j)替換replace

n=j；

end

ifreplace>b(j,k)

replace=b(j,k);%同上

n=j；

end

end

end

suml=sum1+replace;%路徑疊加

x(l,i+l)=a(n,l);%記錄最近距離點(diǎn)的行坐標(biāo)

y(l,i+l)=a(n,2);%記錄最近距離點(diǎn)的縱坐標(biāo)

form=l:lent

b(m,k)=inf;%如果路徑已通過(guò)該點(diǎn)，那么

把％該點(diǎn)與其他所有

b(k,m)=inf;%點(diǎn)的距離設(shè)為inf,防止路徑重復(fù)。

end

k=n;%把尋找到的點(diǎn)作為路徑出發(fā)點(diǎn)，開(kāi)始尋找下一點(diǎn)

end

plot(x,y)

分步二

functiony=fun_aft36(d)

a=[3600,2300;3100,3300;..........1100;200,800]注：方框中坐

標(biāo)省略

[b]=fun_create_b(a,76)%由矩陣a創(chuàng)建距離矩陣b

[b]=fun_modify_all_b(b)%根據(jù)題中第二問(wèn)給出路徑

限％制修改b中距離信息

x=zeros(l);%定義行矩陣x記錄路徑中每個(gè)點(diǎn)的橫坐標(biāo)

y=zeros(l);%定義行矩陣y記錄路徑中每個(gè)點(diǎn)的縱坐標(biāo)

lent=40

sum1=0

k=l

x(l,l)=a(l,l);

y(l,l)=a(l,2);

fori=lent:76

replace=inf;

ifk==53

n=43;

elseifk==64

n=73;

else

forj=lent:1:76

ifreplace>b(k,j)

replace=b(k,j);

n=j；

end

ifreplace>b(j,k)

replace=b(j,k);

n=j；

end

end

end

sum1=sum1+replace;

x(l,i-38)=a(n,l);

y(l,i-38)=a(n,2);

form=lent:76

b(m,k)=inf;

b(k,m)=inf;

end

k=n；

end

plot(x,y)

分步路徑組合：

function[x,y,suml]=fun_shorway4(d)

a=[3600,2300;3100,3300.............4700,1100;200,800];%方

框％中76坐標(biāo)省略。

len=76

b=zeros(len);

fori=l:len

forj=i:len

b(i,j)=((a(