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

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

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