條弧與線性表之間的最短路徑上的最短路徑

條弧與線性表之間的最短路徑上的最短路徑

在這項(xiàng)工作中，我們使用了文獻(xiàn)的符號(hào)和定義。在文件圖1中，每個(gè)點(diǎn)v（pt）上使用該圖，以表示旅行社能夠避開(kāi)從城市訪問(wèn)pn到k的所有最短路徑。根據(jù)文獻(xiàn)提供的最短路徑的要求，確定k列圖，重復(fù)此步驟，并在第列圖中找到第二面圖。顯然,這涉及動(dòng)態(tài)規(guī)劃的思想.Bellman等運(yùn)用動(dòng)態(tài)規(guī)劃原理討論了旅行商的路徑優(yōu)化問(wèn)題.Clientsov等研究了路徑問(wèn)題中的離散?連續(xù)優(yōu)化方法的應(yīng)用.Chentsov等分析了動(dòng)態(tài)規(guī)劃應(yīng)用于TSP路徑優(yōu)化的過(guò)程.以上提及的動(dòng)態(tài)規(guī)劃在TSP方面的應(yīng)用基于Bellman的最優(yōu)性原理,而本文探討的TSP算法依據(jù)文獻(xiàn).1圖和圓弧中的線條1.1v用圖G(v(pk)?r1,r2,…,rg)來(lái)表示旅行商避開(kāi)城市r1,r2,…,rn到v(pk)的全部最短路徑,定義它為2個(gè)符號(hào)集合:頂點(diǎn)的集合Ω(v(pk)?r1,r2,…,rg)和弧的集合A(v(pk)?r1,r2,…,rg),即G(v(pk)?r1?r2???rg)=(Ω(v(pk)?r1?r2???rg)?A(v(pk)?r1?r2???rg))(1)同理,定義由經(jīng)過(guò)指定頂點(diǎn)v(qk-1)到v(pk)的全部最短路徑的圖:G(v(pk)/v(qk-1)?r1???rg)=(Ω(v(pk)/v(qk-1)?r1???rg)?A(v(pk)/v(qk-1)?r1???rg))(2)僅當(dāng)v(pj-1)和v(pj)是圖G(v(pk)?r1,r2,…,rg)中同一路徑上的2個(gè)相鄰的頂點(diǎn)時(shí),才存在一條從v(pj)到v(pj-1)的弧[v(pj),v(pj-1)],v(pj)稱之弧尾,v(pj-1)稱之為弧頭.頂點(diǎn)v(pk)和v(0)分別稱之為圖G(v(pk)?r1,r2,…,rg)的源點(diǎn)(Source)和終點(diǎn)(Destination).用η(v(pk)?r1,r2,…,rg)表示G(v(pk)?r1,r2,…,rg)的權(quán),它等于到v(pk)的最短路徑的權(quán).1.2面元公式[vqjpn在G(v(pk)?pn)上的每一弧上定義一個(gè)線性表,用以記錄它所屬的圖,從而將判斷某條弧和某個(gè)頂點(diǎn)是否應(yīng)該存在于某個(gè)子圖中的最短路徑上的問(wèn)題轉(zhuǎn)化為線性表的相關(guān)操作.在文獻(xiàn)的圖1中,依次對(duì)第一行和第一列上的頂點(diǎn)到第n行和第n列上的頂點(diǎn)進(jìn)行編號(hào):1,2,…,n2.這樣,第i行和第j列上的頂點(diǎn)的編號(hào)為(j-1)n+i.為G(v(qk-1)?pn)上的每一條弧[v(qj),v(qj-1)]建立一個(gè)線性表,記作L(v(qj),v(qj-1)),線性表中數(shù)據(jù)元素為該弧所屬子圖源點(diǎn)的編號(hào),按升序排列.對(duì)于G(v(qk-1)?pn)上頂點(diǎn)v(qx),用π(qx)表示它的編號(hào).頂點(diǎn)的編號(hào)和頂點(diǎn)存在一一對(duì)應(yīng)的關(guān)系,有時(shí)為表示方便,用編號(hào)π(qx)代表頂點(diǎn)v(qx).設(shè)G(v(q(χ)i)?pn)為G(v(qk-1)?pn)上第i列上的第χ個(gè)包含弧[v(qj),v(qj-1)]的子圖,i∈[j,k-1],χ∈[1,a(i)],a(i)∈[1,n-2],亦即[v(qj),v(qj-1)]∈A(v(q(χ)i)?pn),則[v(qj),v(qj-1)]上的線性表為L(zhǎng)(v(qj),v(qj-1))=(π(q(1)j),π(q(1)j+1),…,π(q(a(j+1))j+1),…,π(q(1)k-2),…,π(q(a(k-2))k-2),π(q(1)k-1)),這里,π(q(1)j)=π(qj),π(q(1)k-1)=π(qk-1).令Li(v(qi),v(qi-1))={π(q(1)i),…,π(q(a(i))i)},則L(v(qj),v(qj-1))可劃分成以下子集:L(v(qj)?v(qj-1))=Lj(v(qj)?v(qj-1))∪Lj+1(v(qj)?v(qj-1))∪?∪Lk-1(v(qj)?v(qj-1))(3)注意到線性表中數(shù)據(jù)元素兩兩相異,因此Lj(v(qj)?v(qj-1))∪Lj+1(v(qj)?v(qj-1))∪?∪Lk-1(v(qj)?v(qj-1))=?(4)2[vqjvqjv.1pn定理1GR(v(qk-1)?pn)上的任意一條弧[v(qj-1),v(qj-2)]在到v(qk-1)的最短路徑上的充分必要條件:當(dāng)j∈[2,k-1]時(shí),L(v(qj)?v(qj-1))?L(v(qj-1)?v(qj-2))(5)j∈[1,k-2]時(shí),存在弧[v(q(1)j+1),v(qj)],[v(q(2)j+1),v(qj)],…,[v(q(a(j+1))j+1),v(qj)],且L(v(qj)?v(qj-1))={π(qj)}∪L(v(q(1)j+1)?v(qj))∪L(v(q(2)j+1)?v(qj))∪?∪L(v(q(a(j+1))j+1)?v(qj))(6)這里,a(j+1)∈[1,n-2].證明:a.必要性.假設(shè)GR(v(qk-1)?pn)上的每條弧都在最短路徑上,而[v(qk-1),v(qk-2)]為GR(v(qk-1)?pn)中的弧.對(duì)于任一包含弧[v(qj),v(qj-1)]的最短路徑<v(q0),v(q1),…,v(qk-1)?pn>,v(qj+1),v(qj+2),…,v(qk-1)為包含[v(qj),v(qj-1)]和[v(qj-1),v(qj-2)]的圖的源點(diǎn),但v(qj-1)為包含[v(qj-1),v(qj-2)]而不包含[v(qj),v(qj-1)]的圖的源點(diǎn),因此,式(5)成立.因?yàn)閇v(qj),v(qj-1)]在到v(qk-1)的最短路徑上,[v(qj),v(qj-1)]必須屬于第k+1列上的一個(gè)或數(shù)個(gè)子圖GR(v(q(1)j+1)?pn),GR(v(q(2)j+1)?pn),…,GR(v(q(a(j+1))j+1)?pn),因而弧[v(q(1)j+1),v(qj)],[v(q(2)j+1),v(qj)],…,[v(q(a(j+1))j+1),v(qj)]存在.對(duì)于每一μ∈[1,a(j+1)],包含[v(q(μ)j+1),v(qj)]的圖也包含[v(qj),v(qj-1)],而[v(qj),v(qj-1)]在以v(qj)為源點(diǎn)的圖上,但[v(q(μ)j+1),v(qj)]不在,因此,式(6)成立.b.充分性.令[v(qj),v(qj-1)]為GR(v(qk-1)?pn)上的滿足式(5)和式(6)的弧,要證明存在最短路徑<v(q0),v(q1),…,v(qk-1)?pn>.GR(v(qk-1)?pn)上所有弧都滿足式(5),因此存在弧[v(qj-1),v(qj-2)],[v(qj-2),v(qj-3)],…,[v(q1),v(q0)],且L(v(qj)?v(qj-1))?L(v(qj-1)?v(qj-2))???L(v(q1)?v(q0))(7)GR(v(qk-1)?pn)上所有弧都滿足式(6),因此存在源點(diǎn)[v(qk-1),v(qk-2)],[v(qk-2),v(qk-3)],…,[v(qj+1),v(qj)],且L(v(qk-1)?v(qk-2))?L(v(qk-2)?v(qk-3))???L(v(qj)?v(qj-1))(8)式(5)和式(6)產(chǎn)生最短路徑<v(q0),v(q1),…,v(qk-1)?pn>.在GR(v(qk-1)?pn)中,假設(shè)以v(qj)為弧頭的弧為[v(q(β)j+1),v(qj)],β∈[1,t];以v(qj)為弧尾的弧為[v(qj),v(q(α)j-1)],α∈[1,s].為每條以v(qj)為弧尾的弧[v(qj),v(q(α)j-1)]建立一個(gè)參照表并初始化:L′(v(qj),v(q(α)j-1))=?,α∈[1,s].對(duì)于每一[v(q(β)j+1),v(qj)],檢查是否存在弧[v(qj),v(q(α)j-1)]使L(v(q(β)j+1),v(qj))?L(v(qj),v(q(α)j-1)).若存在,則將L(v(q(β)j+1),v(qj))并入相應(yīng)的L′(v(qj),v(q(α)j-1));若不存在,則刪除[v(q(β)j+1),v(qj)].每條以v(qj)為弧頭的弧必須與所有以v(qj)為弧尾的弧進(jìn)行比較,以確定它是否并入后者對(duì)應(yīng)的參照表.完成比較后,檢查每一L′(v(qj),v(q(α)j-1))是否仍為空集.若為空集,則刪除[v(qj),v(q(α)j-1)];若不為空集,則使L(v(qj),v(q(α)j-1))=L′(v(qj),v(q(α)j-1)).3qk-1第1條線性表的生成依次生成G(v(p1)?pn),G(v(p2)?pn),…,G(v(pn-1)?pn).首先生成第一列上頂點(diǎn)的圖G(v(p1)?pn).當(dāng)d(0,p1)<+∞時(shí),對(duì)于每一pn∈[1,n],只要pn≠p1,則<v(0),v(p1)?pn>為最短路徑,其權(quán)重w(0,p1)=d(0,p1).在這種情況下,Ω(v(p1)?pn)={v(0),v(p1)};A(v(p1)?pn)={[v(p1),v(0)]};η(v(p1)?pn)=w(0,p1);L(v(p1),v(0))=(π(p1)).若d(0,p1)=+∞,則η(v(p1)?pn)=+∞,這時(shí),G(v(p1)?pn)不存在.當(dāng)k∈[2,n-1]時(shí),現(xiàn)給定第(k-1)列上頂點(diǎn)的所有的圖G(v(qk-1)?pn).當(dāng)pk≠qk-1且0<d(qk-1,pk)<+∞時(shí),應(yīng)用上一節(jié)提出的方法,刪除G(v(qk-1)?pn)上第pk行上的頂點(diǎn)以及由此導(dǎo)致的那些不在最短路徑上的頂點(diǎn)和弧,從而獲得G(v(qk-1)?pn)的一個(gè)子圖GR(v(qk-1)?pn).如果v(qk-1)在G(v(qk-1)?pn)上仍與v(0)連通,則G(v(pk)/v(qk-1)?pn)生成如下:Ω(v(pk)/v(qk-1)?pn)={v(pk)}∪ΩR(v(qk-1)?pn)(9)A(v(pk)/v(qk-1)?pn)={[v(pk)?v(qk-1)]}∪AR(v(qk-1)?pn)(10)η(v(pk)/v(qk-1)?pn)=η(v(qk-1)?pk)+d(qk-1?pk)(11)L(v(pk)?v(qk-1))=(π(pk))(12)完成G(v(pk)/v(qk-1)?pn)后,初始化G(v(pk)?pn):Ω(v(pk)?pn)=?,A(v(pk)?pn)=?.置η(v(pk)?pn)=min{η(v(pk)/v(qk-1)?pn)/v(qk-1)∈Γk-1}.若η(v(pk)/v(qk-1)?pn)=η(v(pk)?pn),則將G(v(pk)/v(qk-1)?pn)并入G(v(pk)?pn):Ω(v(pk)?pn)∪Ω(v(pk)/v(qk-1)?pn)?Ω(v(pk)?pn)(13)A(v(pk)?pn)∪A(v(pk)/v(qk-1)?pn)?A(v(pk)?pn)(14)對(duì)于每一[v(qj),v(qj-1)]∈A(v(pk)/v(qk-1)?pn),若它已存在于A(v(pk)?pn),則將這2條相同的弧上的2個(gè)線性表的并集作為A(v(pk)?pn)中該弧的線性表;若它不存在于A(v(pk)?pn),則[v(qj),v(qj-1)]在A(v(pk)/v(qk-1)?pn)中的線性表就是它在A(v(pk)?pn)中的線性表.當(dāng)η(v(pk)?pn)=+∞時(shí),G(v(pk)?pn)不存在.重復(fù)以上步驟,生成到第n-1列上的圖G(v(pn-1)?pn).4最佳解決方案4.1和弧的集合avqn用<v(p0),v(p1),…,v(pn)>表示到第n列上頂點(diǎn)v(pn)的路徑.當(dāng)w(p0,p1,…,pn)=min{w(q0,q1,…,qn-1,pn)/<v(q0),v(q1),…,v(qn-1)?pn>∈Sn-1}時(shí),定義<v(p0),v(p1),…,v(pn)>為最短路徑.圖G(v(qn))由到v(qn)的全部最短路構(gòu)成,它定義為2個(gè)符號(hào)集合:頂點(diǎn)的集合Ω(v(qn))和弧的集合A(v(qn)),亦即G(v(qn))=(Ω(v(qn)),A(v(qn))).用圖G(v(qn)/v(rn-1))表示經(jīng)過(guò)v(rn-1)到v(qn)的全部最短路徑.當(dāng)d(rn-1,qn)<+∞時(shí),生成G(v(qn)/v(rn-1))如下:Ω(v(qn)/v(rn-1))={v(qn)}∪Ω(v(rn-1)?qn)(15)A(v(qn)/v(rn-1))={[v(qn)?v(rn-1)]}∪A(v(rn-1)?qn)(16)η(v(qn)/v(rn-1))=η(v(rn-1)?qn)+d(rn-1?qn)(17)L(v(qn)?v(rn-1))=(π(qn))(18)對(duì)于每一[v(rj),v(rj-1)]∈A(v(qn)/v(rn-1)),在L(v(rj),v(rj-1))中的最后一個(gè)元素后插入π(qn).置η(v(qn))=min{η(v(qn)/v(rn-1))/v(rn-1)∈Γn-1}.如果η(v(qn)/v(rn-1))=η(v(qn)),將G(v(qn)/v(rn-1))并入G(v(qn)):Ω(v(qn)/v(rn-1))∪Ω(v(qn))?Ω(v(qn));A(v(qn)/v(rn-1))∪A(v(qn))?A(v(qn)),同時(shí)將G(v(qn)/v(rn-1))中的所有線性表并入G(v(qn)).4.2為如果在第n列至少存在一個(gè)頂點(diǎn)v(qn),滿足η(v(qn))<+∞和d(qn,0)<+∞,則旅行商訪問(wèn)的第n個(gè)城市取決于η(v(pn))=min{η(v(qn))+d(qn,0)/v(qn)∈Γn}.定理2G(v(pn))上存在最短路徑<v(p0),v(p1),…,v(pn)>的充分必要條件:存在一個(gè)弧的系列[v(pn),v(pn-1)],[v(pn-1),v(pn-2)],…,[v(p1),v(p0)],且π(pn)∈Ln(v(pn)?v(pn-1))(19)π(pn-1)∈Ln-1(v(pn-1)?v(pn-2))?π(pn)∈Ln(v(pn-1)?v(pn-2))；?；(20)π(p1)∈L1(v(p1)?v(p0))?π(p2)∈L2(v(p1)?v(p0))???π(pn)∈Ln(v(p1)?v(p0))(21)證明:a.必要性.假設(shè)G(v(pn))上存在最短路徑<v(p0),v(p1),…,v(pn)>.k=n時(shí),弧[v(pn),v(pn-1)]存在,L(v(pn),v(pn-1))=Ln(v(pn),v(pn-1))=(π(pn)),因此π(pn)∈Ln(v(pn),v(pn-1)).假設(shè)k=j時(shí),存在[v(pj),v(pj-1)],且π(pj)∈Lj(v(pj),v(pj-1)),π(pj+1)∈Lj+1(v(pj),v(pj-1)),…,π(pn)∈Ln(v(pj),v(pj-1))).當(dāng)k=j-1時(shí),因?yàn)?lt;v(p0),v(p1),…,v(pn)>是最短路徑,因此弧[v(pj-1),v(