帶單一限制條件的單源多權(quán)最短路徑問題

帶單一限制條件的單源多權(quán)最短路徑問題

2000年，馮德民和謝娟英提出了一種基于單一限制條件的最短路徑算法（以下簡稱馮算法）。帶單一限制條件的單源多權(quán)最短路徑問題(以下簡稱此類問題)在實際中比比皆是,解決此類問題算法有著非常廣泛的應(yīng)用價值。遺憾的是,馮算法不是一個正確的算法。本文中首先分析了馮算法的不足之處,并給出馮算法的一個反例;然后,本文提出了一個解決此類問題的算法(以下簡稱本算法),并證明本算法是正確的。本算法中設(shè)計了獨特的數(shù)據(jù)結(jié)構(gòu)并且用十分簡單的方法解決了此類問題,這是本算法的一個顯著特點。1邊性質(zhì)、vn、wj、li定義1設(shè)有向圖G=(V(G),E(G)),其中V(G)={vi|1≤i≤n,n為圖中頂點數(shù)},稱V(G)為圖G的頂點集;E(G)={epq|epq=〈vp,vq〉,〈vp,vq〉為一條邊,vp,vq∈V(G),1≤p,q≤n},稱E(G)為圖G的有向邊集,w1(p,q),w2(p,q),…,wh(p,q)是圖G的一條邊〈vp,vq〉上的h個權(quán),wi(p,q)≥0(i=1,2,…,h);稱v1為源點,vn為終點。定義2對應(yīng)定義1中的h個權(quán),有h個數(shù)k1,k2,…,kh(0≤kj≤1,1≤j≤h;且它們稱為評價系數(shù);一條邊〈vp,vq〉的評價長度為函數(shù)的值(函數(shù)val(p,q)稱為評價函數(shù));一條路徑上各條j=1邊的評價長度和稱為此條路徑評價長度。定義3設(shè)一個頂點序列v1,…,vn是從v1到vn的一條路徑,若該路徑上所有邊上的一個權(quán)wj(本文中規(guī)定wj為w1)之和滿足∑wj≤LI,其中LI為一給定的正常數(shù),則稱這一路徑為滿足對權(quán)wj限制的路徑。定義4設(shè)l1,l2,…,lm分別是從v1到vn的滿足對權(quán)wj限制的所有m條路徑,則稱這m條路徑中評價長度最小的那條路徑為滿足對權(quán)wj限制的最短路徑。2馮算法的不足和反例2.1lenth+val,n馮算法的存儲結(jié)構(gòu)、主要變量說明和算法請見文獻(xiàn)中。設(shè)val(k,k-1)為<vk,vk-1>這條邊上評價長度,w1(k-1,k)為這條邊上權(quán)w1的值,設(shè)nlen=dist[k-1].LENTH+val(k,k-1),nsw=disk[k-1].SW+w1(k-1,k);馮算法的基本思路是:當(dāng)從某個頂點vk-1出發(fā),遍歷其鄰接頂點vk時,如果下列條件成立(馮算法中p為總的限制值,在本文中用LI表示馮算法中的p常量)。則用以下賦值語句進行“替換”,即:馮算法的不足之處是:當(dāng)上述條件(1)成立,但同時nsw>dist[k].SW也成立時,按照馮算法要進行上述“替換”,這樣,dist[k].LENTH值比“替換”前小,但dist[k].SW值卻比“替換”前大,結(jié)果常常找不出一個正確的解來。2.2鄰接點邏輯的計算例1一個有向圖如圖1所示。其中v1是源點,v4是終點,LI=8,兩個評價系數(shù)為:k1=k2=0.5,評價函數(shù)為:val(p,q)=0.5×(w1(p,q)+w2(p,q))。按照馮算法,從v1出發(fā)分別遍歷v3、v2、v4得:dist.LENTH=3,dist.SW=3;dist.LENTH=7.5,dist.SW=5;dist.LENTH=20,dist.SW=7,再從v3出發(fā)遍歷其鄰接點v2。因為:(nsw=dist.SW+4=7<LI=8)且(nlen=dist.LENTH+0.5(4+1)=5.5<dist.LENTH=7.5)這一條件成立,按照馮算法要進行如下“替換”;dist.LENTH=5.5,dist.SW=7,再從v2出發(fā)遍歷v4終點,因為此時dist.SW+2=9>LI=8,所以用馮算法只找到一個滿足限制條件LI=8的解,為dist.LENTH=20;但實際上還存在一個解,即<v1,v2,v4>,此條路徑的∑w1=5+2=7<LI,而評價長度值為0.5×(5+10+2+2)=9.5。3該算法為了簡便,以下規(guī)定:受限制的權(quán)為w1,定義中h=2,即:只有兩個權(quán)w1,w2;多權(quán)的情況用本算法求解是完全類似的。3.1頂小狀態(tài)spd的大小比較定義5圖中一個頂點vp的一個狀態(tài)(state)。從源點v1出發(fā)經(jīng)過一條路徑到達(dá)一個頂點vp,該路徑上各條邊上的權(quán)w1之和以及評價長度之和分別記為∑w1,∑val;則稱(∑val,∑w1)這個二元組為頂點vp的一個狀態(tài)。顯然,vp可能有多個狀態(tài),頂點vp的第d個狀態(tài)記為Spd,即:Spd=(vapd,w1pd)。定義6兩個狀態(tài)間按“字典序”進行的大小比較。設(shè)一個狀態(tài)為Spd=(vapd,w1pd),另一狀態(tài)為Smj=(vamj,w1mj),(m和p可為相同的值),如果(vapd<vamj或((vapd=vamj)且(w1pd<w1mj))),則稱Spd<Smj,即:狀態(tài)Spd按字典序比狀態(tài)Smj“小”;如果(vapd=vamj且w1pd=w1mj),則稱Spd=Smj,即:兩狀態(tài)值相等。按上面定義的字典序,我們可以從多個狀態(tài)中找出一個最小狀態(tài)。3.2狀態(tài)結(jié)論的生成圖G是一個有n個頂點的有向圖,它的鄰接表由n個單鏈表(稱為鄰接單鏈表)和一維數(shù)組hg組成;第p(1≤p≤n)個鄰接單鏈表中每個結(jié)點(稱為鄰接結(jié)點)有4個域,如下所示:〈vp,vq〉(1≤q≤n)為圖G中一條邊,wpq、valpq分別是這條邊上權(quán)w1的值和評價長度的值,link是指針域,指向此單鏈表的下一個結(jié)點。本算法中,同一個鄰接單鏈表中各個結(jié)點按wpq域的值非遞減的順序在鄰接單鏈表中按照從前(表頭結(jié)點)往后(表尾結(jié)點)的順序依次排列,這樣做可提高整個算法的效率。hg[p]中存的是第p個鄰接單鏈表的頭指針。(2)狀態(tài)表狀態(tài)表由一維數(shù)組hs和n個稱為狀態(tài)單鏈表的單鏈表組成。根據(jù)定義5,一個頂點可能有多個狀態(tài),本文中為每個頂點vp(1≤p≤n)建立了一個狀態(tài)單鏈表(此狀態(tài)單鏈表也稱為vp的狀態(tài)單鏈表),一個狀態(tài)單鏈表中的一個結(jié)點稱為一個狀態(tài)結(jié)點,一個頂點vp的狀態(tài)結(jié)點共有6個域。如下所示:其中vall,ww中分別存的是如定義5中定義的vp一個狀態(tài)(vapd,w1pd)的二個分量值vapd和w1pd。(vall,ww)也稱為此狀態(tài)結(jié)點的狀態(tài)。act/sta:稱為活動/靜止域;當(dāng)act/sta域值為0時,此狀態(tài)結(jié)點稱為(定義為)一個活動結(jié)點,當(dāng)act/sta域值為1時,此狀態(tài)結(jié)點稱為(定義為)一個靜止結(jié)點。ver稱為頂點域,一個頂點vp的狀態(tài)結(jié)點的ver域的值即為vp本身(為了簡化,ver域中僅寫上vp的下標(biāo)p)。pre:稱為直接前趨域。一個狀態(tài)結(jié)點(設(shè)為D結(jié)點)的pre域中存狀態(tài)表中另一個狀態(tài)結(jié)點(設(shè)為C結(jié)點)的地址值,C結(jié)點的狀態(tài)必須是D結(jié)點狀態(tài)的前趨狀態(tài)(見下面定義7)。slink為指針域,指向下一個狀態(tài)結(jié)點。定義7前趨狀態(tài)、后繼狀態(tài)從一個頂點vp(此時它的狀態(tài)為Spd=(vapd,w1pd))出發(fā)訪問它的一鄰接點vq,<vp,vq>為一條邊,vq的一個狀態(tài)為Sqg=(vaqg,w1qg),如果下述等式成立:則稱,Spd為Sqg的前趨狀態(tài),Sqg為Spd的后繼狀態(tài)。從定義7可知,因為val(p,q)≥0且w1(p,q)≥0,顯然有下面的引理1成立。引理1后繼狀態(tài)大于或等于前趨狀態(tài)(字典序)求最短路徑常要求求出這條最短路徑本身(即:通過哪些頂點)。起初,本算法是在狀態(tài)結(jié)點中使用一些標(biāo)號域以便記住一條最短路徑上各個頂點,但使用標(biāo)號域的算法相當(dāng)繁瑣;后來,經(jīng)過反復(fù)研究,本算法借用了C語言的一個特點可用指針變量存儲一個結(jié)點的地址,本算法在狀態(tài)結(jié)點中不用標(biāo)號域而是改用前面所說的ver和pre域,其中pre域是一個指針變量,它指著狀態(tài)表中一個具有前趨狀態(tài)的結(jié)點,這樣確定一條最短路徑所通過的各個頂點非常的方便、快捷(只需從終點的一個狀態(tài)結(jié)點出發(fā)通過pre域連續(xù)地找具有前趨狀態(tài)的結(jié)點,并同時打印相應(yīng)狀態(tài)結(jié)點的頂點域的值,直到找到一個狀態(tài)結(jié)點其pre域的值為空(即:∧)時為止。因為一條最短路徑上最多有n個頂點,所以打印一條最短路徑最多需時間為O(n))。在狀態(tài)結(jié)點中設(shè)置pre域來存儲具有前趨狀態(tài)的結(jié)點的地址是本算法的一個顯著特點。頭數(shù)組hs中每個元素有兩個域,如右所示:hs[r].lk(1≤r≤n)中存的狀態(tài)表中頂點vr的狀態(tài)單鏈表的頭指針,hs[r].alk中存的是hs[r].lk所指向的狀態(tài)單鏈表中排在最前面的第一個活動結(jié)點的地址值。定義8一個狀態(tài)單鏈表中的狀態(tài)結(jié)點是按字典序排列的。如果一個狀態(tài)單鏈表中原來有任兩個狀態(tài)結(jié)點SE、SF,SE的狀態(tài)為(ve,ww1e),SF的狀態(tài)為(vf,ww1f),它們都經(jīng)過下面(1)、(2)兩個步驟處理后,這個狀態(tài)單鏈表就稱為是按字典序排列的。(1)如果(ve≤vf且ww1e≤ww1f),則將SF結(jié)點從此狀態(tài)單鏈表中刪除。即:留“小”(SE)丟“大”(SF)。(2)如果(ve≤vf且ww1e≥ww1f)成立(注:如果出現(xiàn)ve=vf且ww1e=ww1f情況仍按(1)處理,即:刪除SE或SF),則SE這個結(jié)點是SF這個結(jié)點的前趨結(jié)點。本文中狀態(tài)單鏈表均按字典序排列。定義9將一個狀態(tài)結(jié)點按字典序插入狀態(tài)單鏈表。這種插入是指插入后此狀態(tài)單鏈表仍是按字典序排列的。3.3在最短路徑kv1為源點,vn為終點;限制條件為LI。(1)僅以w1(p,q)作為每條邊〈vp,vq〉上的長度,用Dijktra算法求出在這種情況下從v1到vn的最短距離LT1n,如果LT1n>LI,則無解,算法結(jié)束。(2)置初值。依次掃描鄰接表中以hg為頭指針的鄰接單鏈表中各個鄰接結(jié)點(設(shè)當(dāng)前掃描結(jié)點為E結(jié)點),如果E.wpq域的值>LI,則停止掃描,轉(zhuǎn)(3);否則,每掃描到一個E結(jié)點則在狀態(tài)表中產(chǎn)生并插入一個狀態(tài)結(jié)點(設(shè)此結(jié)點為F結(jié)點),F結(jié)點的地址存在hs[q].alk和hs[q].lk中,而且F結(jié)點的6個域賦值如下:F.act/sta=0(即此狀態(tài)結(jié)點開始時為活動結(jié)點),F.vall=E.valpq,F.ww=E.wpq,F.ver=E.q,F.pre=∧,F.slink=∧。(3)在狀態(tài)表中找出按字典序最小的活動狀態(tài)將hs[r].alk(1≤r≤n)所指的n個狀態(tài)單鏈表中的排在最前面的第一個活動結(jié)點狀態(tài)進行字典序大小的比較,找出一個最小狀態(tài)(mval,mww1)和具有此狀態(tài)的狀態(tài)結(jié)點U(設(shè)指向此結(jié)點的指針為hs[u].alk)(1≤u≤n),如果u=n(vn為終點。),則找到了一滿足限制條件的最短路徑,其評價長度值為mval,此條最短路徑通過哪些頂點可通過如在3.2節(jié)中狀態(tài)表一節(jié)中描述那樣借助pre和ver域快速求得,然后結(jié)束此算法。如果u≠n,則將U.act/sta域置為1,然后將hs[u].alk指向U后的第一個活動結(jié)點,設(shè)U結(jié)點的地址為AU。(4)從本算法第(3)步中剛找出的U結(jié)點的U.ver(它是圖中一個頂點vu)出發(fā)遍歷其所有鄰接點vy(通過訪問鄰接表中以hg[u]為頭指針的鄰接單鏈表來實現(xiàn)遍歷);設(shè)此時vu的狀態(tài)值為(mval,mww1),如果mww1+w1(u,y)>LI,則停止遍歷,轉(zhuǎn)(3);否則,產(chǎn)生一個vy的狀態(tài),即:(mval+val(u,y),mww1+w1(u,y)),并產(chǎn)生一個狀態(tài)結(jié)點Y,設(shè)其地址為AY,設(shè)mvuy=mval+val(u,y),mw1uy=mww1+w(u,y),則Y結(jié)點如下所示:然后將此結(jié)點按字典序插入狀態(tài)表中以hs[y].alk為頭指針的單鏈表中,轉(zhuǎn)(3)。3.4狀態(tài)結(jié)論sn.守護神從本算法可知:以hs[n].alk為頭指針的狀態(tài)單鏈表中第一個被找出的狀態(tài)結(jié)點,即是本算法要找出的最后一個狀態(tài)結(jié)點;如果一個狀態(tài)結(jié)點U,它是所求的最短路徑的終點vn所在狀態(tài)結(jié)點,它必須滿足下面3個等式:(3)、(4)、(5)。(下面用符號→表示所指向的結(jié)點,用符號→.state表示所指向的結(jié)點的狀態(tài)。)下面來證明vn的所有狀態(tài)結(jié)點(記為SN,即:SN.ver等于vn)中的狀態(tài)(記為SN.state)均有SN.state≥U.state成立即可。SN.state分二種情況:(1)SN已求出。那么SN在以hs[n].alk為頭指針的狀態(tài)單鏈表中,因為U結(jié)點為此狀態(tài)單鏈表的頭結(jié)點(因為:U=hs[n].alk→),且狀態(tài)單鏈表又按字典序排列,所以,SN.state≥U.state。(2)SN未求出,SN的狀態(tài)是現(xiàn)在狀態(tài)表中一個活動結(jié)點(記為SAN)的狀態(tài)的一個后繼狀態(tài)(即:SN.state=SAN的后繼狀態(tài))。從引理1知:SAN的后繼狀態(tài)≥SAN.state,SN.state=SAN的后繼狀態(tài)≥SAN.state,從U結(jié)點滿足的3個等式可看出,U結(jié)點是當(dāng)前狀態(tài)表中所有活動結(jié)點中字典序最小的結(jié)點,所以:SAN.state≥U.state,SN.state≥SAN.state≥U.state,SN.state≥U.state。從上面(1)、(2)可知:SN.state≥U.state。3.5種方法解決不太復(fù)雜的問題文獻(xiàn)將帶限制條件的此類最短路徑問題列為NP問題;也就是說,本算法時間復(fù)雜度在最壞情況下是指數(shù)函數(shù)。現(xiàn)在遇到NP問題,通常用3種方法來解決:(1)設(shè)計一個算法和相應(yīng)程序,只運行這個程序的一個小的實例。如背包問題算法;(2)設(shè)計一個算法和相應(yīng)程序,只運行這個程序解決一個不太復(fù)雜的實例。如頂點覆蓋問題算法;(3)設(shè)計一個近似算法。如:貨郎擔(dān)問題近似算法。本算法對于解決不