東北大學(xué)數(shù)學(xué)建模-圖論模型朱和貴8月1日.ppt

1、數(shù)學(xué)模型,圖論模型,朱和貴,1. 圖論的基本概念,2. 最短路問題及算法,第二講 圖論模型,3. 最小生成樹及算法,4.網(wǎng)絡(luò)流問題及算法,5. 行遍性問題及算法,18,最短路徑問題是圖論中十分重要的最優(yōu)化問題之一，它作為一個(gè)經(jīng)常被用到的基本工具，可以解決生產(chǎn)實(shí)際中的許多問題，比如城市中的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問題。,2. 最短路問題及算法,19,例 如下圖所示的單行線交通網(wǎng)，每個(gè)弧旁邊的數(shù)字表示這條單行線的長度。現(xiàn)在有一個(gè)人要從V1出發(fā)，經(jīng)過這個(gè)交通網(wǎng)到達(dá)V6， 要尋求總路程最短的 線路。,從v1到v6的路線是很多的。比如從V1出發(fā)，經(jīng)過V2 ,

2、V4到達(dá)V6或者從V1出發(fā)，經(jīng)過V2，V3，V5到達(dá)V6等等。但不同的路線，經(jīng)過的總長度是不同的。例如，按照第一個(gè)線路，總長度是3+6+3=12單位，按照第二個(gè)路線，總長度是3+1+1+6=11單位。,20,定義2 若P0 是D 中連接vs到vt的路徑, 它的權(quán)是D 中連接vs到vt的所有路徑P中最小的，即： 則稱P0 是D 中從vs到vt的最短路，其權(quán)稱為這兩點(diǎn)間的距離，記為d(vs,vt),21,重要性質(zhì)： 如果P是D中從vs到vj的最短路，vi是P中的一個(gè)點(diǎn)，那么，從vs沿P到vi的路是從vs到vi的最短路。,22,求非負(fù)賦權(quán)圖G中某一點(diǎn)到其它各點(diǎn)最短路，一般用Dijkstra (迪克斯

3、特拉)標(biāo)號算法；求非負(fù)賦權(quán)圖上任意兩點(diǎn)間的最短路，一般用Floyd(弗洛伊德)算法。這兩種算法均適用于有向非負(fù)賦權(quán)圖（Floyd算法也適應(yīng)于負(fù)賦權(quán)圖）。,25,例6 求v1到v6的最短路,（1）首先給v1以P標(biāo)號：（0，V1),（0，V1),標(biāo)號以（ ）形式標(biāo)在結(jié)點(diǎn)旁邊 0：表示從V1到該點(diǎn)的最短距離 V1：表示從V1到該點(diǎn)的最短路中上一個(gè)頂點(diǎn)。,26,（2） S：V1 S：V2，V3，V4， V5，V6 求出（S S）所有弧，分別計(jì)算： S12 =0 + 3=3, S13 =0 + 5=5, Min Sij=S12 給V2 標(biāo)號（3，V1）,（3，V1),（0，V1),27,（3） S：V1

4、，V2 S：V3，V4，V5，V6 求出（S S）所有弧，分別計(jì)算： S13 =0 + 5=5 S23 =3 + 1=4 S24 =3 + 6=9 Min Sij=S23 給V3 標(biāo)號（4，V2）,（3，V1),（4，V2),（0，V1),28,（4） S：V1，V2，V3 S：V4，V5，V6 求出（S S）所有弧，分別計(jì)算： S24 =3 + 6=9 S34 =4 + 4=8 S35 =4 + 1=5 Min Sij=S35 給V5 標(biāo)號（5，V3）,（3，V1),（4，V2),（5，V3),（0，V1),29,（0，V1),（5） S：V1，V2，V3，V5 S：V4，V6 求出（S S

5、）所有弧，分別計(jì)算： S24 =3 + 6=9 S34 =4 + 4=8 S54 =5 + 2=7 S56=5 + 6=11 Min Sij=S54 給V4 標(biāo)號（7，V5）,（3，V1),（4，V2),（5，V3),（7，V5),30,（6） S：V1，V2，V3，V4，V5 S：V6 求出（S S）所有弧，分別計(jì)算： S46 =7 + 3=10 S56= 5 + 6=11 Min Sij=S46 給V6 標(biāo)號（10，V4）,（3，V1),（4，V2),（5，V3),（7，V5),（10，V4),（0，V1),31,(7) 標(biāo)出最短路 最短路徑是： V1V2V3V5V4V6 路長10。同時(shí)得

6、到起點(diǎn)到其余各點(diǎn)的最短路。,注意： 雙標(biāo)號法只適用于所有wij 0的情形，當(dāng)賦權(quán)有向圖中存在負(fù)權(quán)時(shí)，則算法失效。,(10),32,求天然氣管道最優(yōu)路徑,籌建中的天然氣管道網(wǎng)設(shè)計(jì)如圖所示：,解為：,表示壓縮機(jī)站，流動主向用箭 頭表示，每個(gè)管道旁的數(shù)字表示管段長度，現(xiàn)需要 求該網(wǎng)絡(luò)從起點(diǎn)A到終點(diǎn)L的最短通道，并確定沿最 優(yōu)路徑相應(yīng)的壓縮機(jī)站所處的節(jié)點(diǎn)。, 例:,33,應(yīng)用：設(shè)備更新問題,某企業(yè)每年年初,都要作出決定,如果繼續(xù)使用舊設(shè)備,要付維修費(fèi)；若購買一臺新設(shè)備,要付購買費(fèi).試制定一個(gè)5年更新計(jì)劃,使總支出最少。 已知設(shè)備在每年年初的購買費(fèi)分別為11,11, 12,12,13。使用不同時(shí)間設(shè)備所

7、需的維修費(fèi)分別為5,6,8,11,18（萬元）。,34,解 設(shè)bi 表示設(shè)備在第i 年年初的購買費(fèi),ci 表示設(shè)備使用i 年后的維修費(fèi), V=v1, v2, , v6,點(diǎn)vi表示第i 年年初購進(jìn)一臺新設(shè)備,虛設(shè)一個(gè)點(diǎn)v6表示第5年年底。 E =vivj | 1ij6。,35,這樣上述設(shè)備更新問題就變?yōu)椋涸谟邢蛸x權(quán)圖G = (V, E, F )(圖解如下)中求v1到v6的最短路問題。,36,從上圖中容易得到v1到v6有兩條最短路：,v1v3v6和v1v4v6。,每對頂點(diǎn)間的最短路算法 尋求賦權(quán)圖中各對頂點(diǎn)之間最短路，顯然可以調(diào)用 Dijkstra 算法。具體方法是：每次以不同的頂點(diǎn)作為起點(diǎn)，用

8、Dijkstra 算法求出從該起點(diǎn)到其余頂點(diǎn)的最短路徑，反復(fù)執(zhí)行次這樣的操作，就可得到每對頂點(diǎn)之間的最短路。但這樣做需要大量重復(fù)計(jì)算，效率不高。R. W. Floyd（弗洛伊德）另辟蹊徑，提出了比這更好的算法，操作方式與 Dijkstra 算法截然不同。,Floyd 算法的基本思想是：從圖的帶權(quán)鄰接矩陣 A = a(i, j)nn 開始，在 A 中用插入頂點(diǎn)的方法依次構(gòu)造出 n 個(gè)矩陣 D(1)、D(2)、D(n)，使最后得到的矩陣 D(n) 成為圖的距離矩陣，即矩陣 D(n) 的 i 行 j 列元素便是 i 號頂點(diǎn)到 j 號頂點(diǎn)的距離。構(gòu)造 D(i) 的同時(shí)，也引入一個(gè)路由矩陣 P(i) 來

9、記錄兩點(diǎn)間的最短路徑。,構(gòu)造矩陣 D(k)，k = 1, 2, , n，采用如下的遞推公式： D(0) = dij(0)nn = A：是帶權(quán)鄰接矩陣，dij(0) 表示從 vi 到 vj 的、中間不插入任何點(diǎn)的路徑，即邊 vivj 的權(quán)值； D(1) = dij(1)nn，其中 dij(1) = mindij(0)，di1(0) d1j(0)：dij(1) 表示從 vi 到 vj 的、中間最多只允許 v1 作為插入點(diǎn)的路徑中最短路的長度；,D(2) = dij(2)nn，其中 dij(2) = mindij(1)，di2(1) d2j(1)：dij(2) 表示從 vi 到 vj 的、中間最多只

10、允許 v1 和 v2 作為插入點(diǎn)的路徑中最短路的長度； D(n) = dij(n)nn，其中 dij(n) = mindij(n1)， di, n1(n1) dn1, j(n1)：dij(n) 表示從 vi 到 vj 的、中間最多只允許 v1, v2, , vn1 作為插入點(diǎn)的路徑中最短路的長度，即 vi 和 vj 之間的距離。,（II）求路徑矩陣的方法.,在建立距離矩陣的同時(shí)可建立路徑矩陣R,（III）查找最短路路徑的方法.,然后用同樣的方法再分頭查找若：,（IV）Floyd算法：求任意兩頂點(diǎn)間的最短路.,例 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑.,插入點(diǎn) v1，得：,矩陣中帶“=”的項(xiàng)為

11、經(jīng)迭代比較以后有變化的元素.,插入點(diǎn) v2，得：,矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后有變化的元素.,插入點(diǎn) v3，得：,插入點(diǎn) v4，得：,插入點(diǎn) v5，得：,插入點(diǎn) v6，得：,故從v5到v2的最短路為8,由v6向v5追溯:,由v6向v2追溯:,所以從到的最短路徑為：,Kruskal (克魯斯卡爾)算法的基本思想 設(shè) T 和 C(T) 分別為圖 G 的最小生成樹的邊集及其權(quán)值，初始狀態(tài)均為空，算法結(jié)束時(shí) T包含最小生成樹的所有邊，C(T) 表示最小生成樹的權(quán)值。令 VS是一個(gè)不相交的節(jié)點(diǎn)的集合，初始狀態(tài)時(shí) VS = v1, v2, , vn。算法的主要步驟是每次從邊集 E 中選出一條未處理的

12、有最小權(quán)值的邊 (u, v) 進(jìn)行分析，如果 u 和 v 同屬于 VS 的一個(gè)元素集，則將邊 (u, v) 刪除，如果 u 和 v 分屬于 VS 的兩個(gè)元素集，則將邊 (u, v) 加入到 T 中，并將這兩個(gè)元素集合并為一個(gè)元素集，然后再從 E 中另選權(quán)值最小的邊進(jìn)行處理，直至找到一棵最小生成樹為止。,Kruskal 算法的步驟 第一步 把圖G = (V, E，W)中所有邊按其權(quán)數(shù)大小排列，將權(quán)數(shù)最小的邊取進(jìn)生成樹T中。 第二步 從剩下的邊中按第一步的方法取下一條邊，若該邊與前面所取的邊形成回路，則舍去該邊，將這條邊放進(jìn)樹T中。 第三步重復(fù)這一過程，直到邊數(shù)比節(jié)點(diǎn)數(shù)目少1。,例n個(gè)城市,各城市

13、之間的距離如下，從一個(gè)城市出發(fā)走遍各個(gè)城市,如何選擇最優(yōu)的旅行路線.,用 Kruskal 算法求上圖給出的賦權(quán)圖的最小生成樹。 解：將圖的邊按照權(quán)值從小到大進(jìn)行排列：,2求最小生成樹的 Prim 算法 Prim (普里姆)算法的直觀描述 假設(shè) T是賦權(quán)圖 G 的最小生成樹。任選一個(gè)頂點(diǎn)將其涂紅，其余頂點(diǎn)為白點(diǎn)；在一個(gè)端點(diǎn)為紅色，另一個(gè)端點(diǎn)為白色的邊中，找一條權(quán)最小的邊涂紅，把該邊的白端點(diǎn)也涂成紅色；如此，每次將一條邊和一個(gè)頂點(diǎn)涂成紅色，直到所有頂點(diǎn)都成紅色為止。最終的紅色邊便構(gòu)成最小生成樹 T的邊集合。,例如，上一小節(jié)給出的賦權(quán)圖，按照上面的描述，容易求出其最小生成樹。,在實(shí)際應(yīng)用中，還會遇到

14、求一個(gè)賦權(quán)圖的最大生成樹的問題。比如，某圖的邊權(quán)代表的是利潤或效益，則最終的問題很可能就是求其最大生成樹。事實(shí)上，從上面兩個(gè)算法可以看出，只要邊權(quán)的選擇改為從大到小，求最小生成樹的算就可以用來求最大生成樹了,Prim 算法的基本思想 設(shè) T 和 C(T) 分別為圖 G 的最小生成樹的邊集及其權(quán)值，初始狀態(tài)均為空，算法結(jié)束時(shí)T包含最小生成樹的所有邊，C(T) 表示最小生成樹的權(quán)值。先指定一個(gè)頂點(diǎn)為初始訪問點(diǎn)，記做 v0，將 v0 加到“通過點(diǎn)”的集合 V 中，然后找出跨接在“通過點(diǎn)”集合V 與“未通過點(diǎn)”集合 VV 之間權(quán)最小的邊 e 作為“通過邊”加入 T中，并將 e 在 VV 中的端點(diǎn)轉(zhuǎn)到

15、V 中。重復(fù)上述過程直至 V = V 為止。,解：為簡便起見，將操作 Prim 算 法的步驟列于下表，,68,例：有一項(xiàng)工程，要埋設(shè)電纜將中央控制室與12個(gè)控制點(diǎn)連通。圖中的各線段標(biāo)出了允許挖電纜溝的地點(diǎn)和距離（單位：百米）。若電纜線每米20元，挖電纜溝（深1米，寬0.6米）土方每立方米5元，請作該項(xiàng)工程預(yù)算，回答最少需要多少元？,102,實(shí)際問題中,一個(gè)網(wǎng)絡(luò)會出現(xiàn)下面兩種情況： 發(fā)點(diǎn)和收點(diǎn)都不止一個(gè)。 解決的方法是再虛設(shè)一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt ,發(fā)點(diǎn)vs到所有原發(fā)點(diǎn)邊的容量都設(shè)為無窮大, 所有原收點(diǎn)到收點(diǎn)vt 邊的容量都設(shè)為無窮大。 網(wǎng)絡(luò)中除了邊有容量外,點(diǎn)也有容量。 解決的方法是將所有

16、有容量的點(diǎn)分成兩個(gè)點(diǎn),如點(diǎn)v有容量Cv ,將點(diǎn)v分成兩個(gè)點(diǎn)v和v,令 C(vv ) = Cv .,2020/8/4,南京信息工程大學(xué)數(shù)理學(xué)院 費(fèi)文龍,103,最小費(fèi)用流問題,這里我們要進(jìn)一步探討不僅要使網(wǎng)上的流達(dá)到最大,或者達(dá)到要求的預(yù)定值,而且還要使運(yùn)輸流的費(fèi)用是最小的,這就是最小費(fèi)用流問題.,最小費(fèi)用流問題的一般提法： 已知網(wǎng)絡(luò)G = (V, E, C ),每條邊vivjE 除了已給容量Cij外,還給出了單位流量的費(fèi)用bij(0). 所謂最小費(fèi)用流問題就是求一個(gè)總流量已知的可行流 f = f ij 使得總費(fèi)用,最小.,2020/8/4,南京信息工程大學(xué)數(shù)理學(xué)院 費(fèi)文龍,104,特別地,當(dāng)要

17、求 f 為最大流時(shí), 即為最小費(fèi)用最大流問題.,設(shè)網(wǎng)絡(luò)G = (V, E, C), 取初始可行流 f 為零流, 求解最小費(fèi)用流問題的迭代步驟： 構(gòu)造有向賦權(quán)圖Gf =(V, Ef , F),對于任意的vivjE,Ef ,F 的定義如下： 當(dāng) f ij = 0時(shí),vivjEf ,F(vivj )= bij ; 當(dāng) f ij = Cij時(shí),vjviEf ,F(vjvi )= - bij ; 當(dāng)0 f ijCij時(shí),vivjEf ,F(vivj )= bij ,vjviEf , F(vjvi ) = - bij . 然后轉(zhuǎn)向.,2020/8/4,南京信息工程大學(xué)數(shù)理學(xué)院 費(fèi)文龍,105, 求出含有負(fù)

18、權(quán)的有向賦權(quán)圖Gf =(V, Ef , F)中發(fā)點(diǎn)vs到收點(diǎn)vt的最短路 ,若最短路 存在轉(zhuǎn)向; 否則f是所求的最小費(fèi)用最大流,停止., 增流.,vivj與相同, vivj與相反.,令 = min ij|vivj , 重新定義流 f = f ij為,其它情況不變.,如果Wf 大于或等于預(yù)定的流量值,則適當(dāng)減少 值,使Wf 等于預(yù)定的流量值,那么 f 是所求的最小費(fèi)用流, 停止; 否則轉(zhuǎn)向.,行 遍 性 問 題,一、中 國 郵 遞 員 問 題,二、推 銷 員 問 題,三、建模案例：最佳災(zāi)情巡視路線,（一） 歐 拉 圖,（二） 中 國 郵 遞 員 問 題,（一） 哈 密 爾 頓 圖,（二） 推 銷

19、 員 問 題,G的邊e是割邊的充要條件是e不含在G的圈中,割邊的定義：設(shè)G連通，e E(G),若從G中刪除邊e后，圖G-e不連通，則稱邊e為圖G的割邊,歐 拉 圖,巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1,歐拉道路：v1e1v2e2v3e5v1e4v4e3v3,歐拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1,歐拉圖,非歐拉圖,返回,中國郵遞員問題-定義,中國郵遞員問題-算法,Fleury算法-基本思想：從任一點(diǎn)出發(fā)，每當(dāng)訪問 一條邊時(shí)，先要進(jìn)行檢查如果可供訪問的邊不只 一條，則應(yīng)選一條不是未訪問的邊集的導(dǎo)出子圖的 割邊作為訪問邊，直到?jīng)]有邊可選擇為止.,若G不

20、是歐拉圖，則G的任何一個(gè)巡回經(jīng)過某些邊必定多于一次,解決這類問題的一般方法是，在一些點(diǎn)對之間 引入重復(fù)邊（重復(fù)邊與它平行的邊具有相同的權(quán)）， 使原圖成為歐拉圖，但希望所有添加的重復(fù)邊的 權(quán)的總和為最小,（）求出G1的最小權(quán)理想匹配M，得到奇次頂點(diǎn)的最佳配對,返回,哈 密 爾 頓 圖,返回,推銷員問題-定義,流動推銷員需要訪問某地區(qū)的所有城鎮(zhèn)，最后回到出發(fā)點(diǎn)問如何安排旅行路線使總行程最小這就是推銷員問題,若用頂點(diǎn)表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)的路，邊上的權(quán)表示距離（或時(shí)間、費(fèi)用），于是推銷員問題就成為在加權(quán)圖中尋找一條經(jīng)過每個(gè)頂點(diǎn)至少一次的最短閉通路問題,定義在加權(quán)圖G=(V,E)中， （）權(quán)最小的

21、哈密爾頓圈稱為最佳H圈 （）經(jīng)過每個(gè)頂點(diǎn)至少一次的權(quán)最小的閉通路稱為最佳推銷員回路,一般說來，最佳哈密爾頓圈不一定是最佳推銷員回路，同樣最佳推銷員回路也不一定是最佳哈密爾頓圈,H回路，長22,最佳推銷員回路，長4,推銷員問題近似算法：二邊逐次修正法：,定義 若對于某一對i和j，有,則圈Cij將是圈C的一個(gè)改進(jìn).,二邊逐次修正法:,在接連進(jìn)行一系列修改之后,最后得一個(gè)圈,不能,再用此方法改進(jìn)了，這個(gè)最后的圈可能不是最優(yōu)的,但是它是比較好的，為了得到更高的精度，這個(gè),程序可以重復(fù)幾次，每次都以不同的圈開始. 這種,方法叫做二邊逐次修正法.,例對下圖16的K6,用二邊逐次修正法求較優(yōu)H圈.,較優(yōu)H圈

22、:,其權(quán)為W(C3)=192,例 98年全國大學(xué)生數(shù)學(xué)建模競賽B題“最佳災(zāi),今年(1998年)夏天某縣遭受水災(zāi). 為考察災(zāi)情、,組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到,全縣各鄉(xiāng)（鎮(zhèn)）、村巡視. 巡視路線指從縣政府,所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政,府所在地的路線.,情巡視路線”中的前兩個(gè)問題是這樣的：,1）若分三組（路）巡視，試設(shè)計(jì)總路程最,短且各組盡可能均衡的巡視路線.,2）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2,小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車行駛速度V,=35公里/小時(shí). 要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分,幾組；給出這種分組下最佳的巡視路線.,公路邊的數(shù)字為該路段的公里

23、數(shù).,2) 問題分析：,本題給出了某縣的公路網(wǎng)絡(luò)圖，要求的是在不,同的條件下，災(zāi)情巡視的最佳分組方案和路線.,將每個(gè)鄉(xiāng)（鎮(zhèn)）或村看作一個(gè)圖的頂點(diǎn)，各鄉(xiāng),鎮(zhèn)、村之間的公路看作此圖對應(yīng)頂點(diǎn)間的邊，各條,再回到點(diǎn)O，使得總權(quán)（路程或時(shí)間）最小.,公路的長度（或行駛時(shí)間）看作對應(yīng)邊上的權(quán)，所,給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化圖論中,一類稱之為旅行售貨員問題，即在給定的加權(quán)網(wǎng)絡(luò),圖中尋找從給定點(diǎn)O出發(fā)，行遍所有頂點(diǎn)至少一次,如第一問是三個(gè)旅行售貨員問題，,本題是旅行售貨員問題的延伸,多旅行售貨員問題.,本題所求的分組巡視的最佳路線，也就是m條,眾所周知，旅行售貨員問題屬于NP完全問題，,顯然本問題

24、更應(yīng)屬于NP完全問題. 有鑒于此，,經(jīng)過同一點(diǎn)并覆蓋所有其他頂點(diǎn)又使邊權(quán)之和達(dá)到,最小的閉鏈（閉跡）.,即求解沒有多項(xiàng)式時(shí)間算法.,一定要針對問題的實(shí)際特點(diǎn)尋找簡便方法，想找到,解決此類問題的一般方法是不現(xiàn)實(shí)的，對于規(guī)模較大,的問題可使用近似算法來求得近似最優(yōu)解.,最佳旅行售貨員問題是NP完全問題,采用一種,近似算法求其一個(gè)近似最優(yōu)解，來代替最優(yōu)解.,算法一 求加權(quán)圖的最佳旅行售貨員回路近似算法:,1) 用圖論軟件包求出G中任意兩個(gè)頂點(diǎn)間的最短路,構(gòu)造出完全圖,2) 輸入圖 的一個(gè)初始H圈；,3) 用對角線完全算法生一個(gè)初始圈;,4) 隨機(jī)搜索出 中若干個(gè)H圈，例如2000個(gè)；,5) 對第2)

25、，3)，4)步所得的每個(gè)H圈，用二邊逐次,修正法進(jìn)行優(yōu)化，得到近似最優(yōu)H圈；,6) 在第5)步求出的所有H圈中，找出權(quán)最小的一個(gè),此即要找的最優(yōu)H圈的近似解.,因二邊逐次修正法的結(jié)果與初始圈有關(guān),故本算法,第2)，3)，4)步分別用三種方法產(chǎn)生初始圈，以保,證能得到較優(yōu)的計(jì)算結(jié)果.,問題一 若分為三組巡視，設(shè)計(jì)總路程最短且各,組盡可能均衡的巡視路線.,此問題是多個(gè)售貨員的最佳旅行售貨員問題.,4),此問題包含兩方面：a)對頂點(diǎn)分組, b)在每組中,求(單個(gè)售貨員)最佳旅行售貨員回路.,因單個(gè)售貨員的最佳旅行售貨員回路問題不存,存在多項(xiàng)式時(shí)間內(nèi)的精確算法.,故多售貨員的最佳旅行售貨員回路問題,也

26、不,而圖中節(jié)點(diǎn)數(shù)較多，為53個(gè)，我們只能去尋求,一種較合理的劃分準(zhǔn)則，對圖1進(jìn)行粗步劃分后,求,出各部分的近似最佳旅行售貨員回路的權(quán),再進(jìn)一,進(jìn)一步進(jìn)行調(diào)整，使得各部分滿足均衡性條件3).,從O點(diǎn)出發(fā)去其它點(diǎn)，要使路程較小應(yīng)盡量走,O點(diǎn)到該點(diǎn)的最短路.,故用軟件包求出O點(diǎn)到其余頂點(diǎn)的最短路.,這些最短路構(gòu)成一棵O為樹根的樹.,將從O點(diǎn)出發(fā)的樹枝稱為干枝.,從O點(diǎn)出發(fā)到其它點(diǎn)共有6條干枝，它們的名稱,分別為，.,在分組時(shí)應(yīng)遵從準(zhǔn)則：,準(zhǔn)則1 盡量使同一干枝上及其分枝上的點(diǎn)分在同一組.,準(zhǔn)則2 應(yīng)將相鄰的干枝上的點(diǎn)分在同一組；,準(zhǔn)則3 盡量將長的干枝與短的干枝分在同一組.,由上述分組準(zhǔn)則，我們找到兩種分組形式如下：,分組1:（，），（，），（，）,分組2:（，），（，），（，）,分組1極不均衡,故考慮分組2.,分組2:(,),(,),(,),對分組2中每組頂點(diǎn)的生成子圖,用算法一求出近似最優(yōu)解及相應(yīng)的巡視路線.,在每個(gè)子