先走+h邊,當(dāng)走+h邊的+1邊的+h邊優(yōu)先尋徑策略

先走+h邊,當(dāng)走+h邊的+1邊的+h邊優(yōu)先尋徑策略

1雙環(huán)網(wǎng)絡(luò)優(yōu)化算法雙環(huán)網(wǎng)絡(luò)是計算機連接網(wǎng)絡(luò)或通信系統(tǒng)的重要拓撲結(jié)構(gòu)，廣泛應(yīng)用于計算機lan級處理結(jié)構(gòu)和各種平行處理結(jié)構(gòu)。圖論模型指的是向圖g（n；1，h）：每個點記錄為0、1、2、1、2、，n-1，每個點ii.1（mon）和i.i（mon）邊緣，他們在邊i和h（mon）邊緣上記錄。h是自然數(shù)，h是h。網(wǎng)絡(luò)的雙環(huán)研究取得了許多[1、2、3、4、5、6、7、8、9、10]。在這項工作中，我們提出了一種路徑方法：在[h]邊，優(yōu)先尋求路徑策略，獲得一些重要的結(jié)果和直觀的圖形，并指出文獻中的錯誤。2雙環(huán)網(wǎng)絡(luò)最短路徑由于雙環(huán)網(wǎng)絡(luò)的對稱性,僅需考慮從節(jié)點0到其它節(jié)點的最短路徑.從節(jié)點0發(fā)出兩條有向邊[+1]和[+h]去訪問其它節(jié)點,有五種訪問方式:(1)只走[+1]邊;(2)只走[+h]邊;(3)優(yōu)先走[+1]邊,后走[+h]邊;(4)優(yōu)先走[+h]邊,后走[+1]邊;(5)[+1]和[+h]邊同時走.對于某些特殊節(jié)點來說,前3種方法可以用,但是對于普遍意義的節(jié)點來說,后兩種方法才能更快地找到最短路徑.作者在文獻中已提出[+1][+h]雙邊尋徑策略.因此,本文提出[+h]邊優(yōu)先尋徑策略.引理1.在雙環(huán)網(wǎng)絡(luò)中從節(jié)點0出發(fā),經(jīng)過x條[+1]邊,y條[+h]邊達到節(jié)點v的充分必要條件是v=x+yh(modN).證明.見文獻.定義1.若存在整數(shù)x,使得x[+1]是0到v(0<v<N)的路徑,則稱x[+1]是0到v的單一[+1]邊路徑;設(shè)x′[+1]是0到v的單一[+1]邊路徑,若不存在比x′更小的x,使x[+1]也是0到v的單一[+1]邊路徑,則稱x′[+1]是0到v的單一[+1]邊最短路徑;若存在整數(shù)y,使得y[+h]是0到v(0<v<N)的路徑,則稱y[+h]是0到v的單一[+h]邊路徑;設(shè)y′[+h]是0到v的單一[+h]邊路徑,若不存在比y′更小的y,使y[+h]也是0到v的單一[+h]邊路徑,則稱y′[+h]是0到v的單一[+h]邊最短路徑.對于單位步長的雙環(huán)網(wǎng)絡(luò),兩種路徑的存在性有如下結(jié)論.結(jié)論1.0到v(0<v<N)的單一[+1]邊路徑和單一[+1]邊最短路徑均存在.當(dāng)gcd(N,h)=1,0到v(0<v<N)的單一[+h]邊路徑和單一[+h]邊最短路徑均存在;當(dāng)gcd(N,h)=m≠1,若v=0(modm),0到v(0<v<N)的單一[+h]邊路徑和單一[+h]邊最短路徑均存在,若v≠0(modm),0到v(0<v<N)的單一[+h]邊路徑和單一[+h]邊最短路徑均不存在.現(xiàn)在要研究的問題是尋找0到v的最短路徑,設(shè)x*+y*=min{x+y|x[+1]+y[+h],x≥0,y≥0}是0到v的最短路徑,一般情況下,x*和y*不唯一,即便x*和y*唯一,但最短路徑表現(xiàn)形式也有Cx*x*+y*種.如何求得這個最短路徑長度?一種思路是:去尋找某一條特殊的最短路徑;另一種思路是:同時找出所有最短路徑.作者在文獻中已討論過同時找出所有最短路徑的方法,因此,下面只介紹尋找某種特殊的最短路徑的方法.3節(jié)點優(yōu)先最短路徑的確定不失一般性,先研究0到任意節(jié)點v的最短距離.為了最快達到v點,顯然優(yōu)先走[+h]邊,當(dāng)走[+h]邊不再有利時,走[+1]邊,這種策略稱為[+h]邊優(yōu)先的最短路徑尋徑策略.定義2.設(shè)從節(jié)點0到節(jié)點v共有t條最短路徑:x(i)v[+1]+y(i)v[+h](i=1,2,…,t),若y(j)v=max{y(i)v,i=1,2,…,t},且所有[+h]邊依次在前,所有[+1]邊依次在后,則稱x(j)v[+1]+y(j)v[+h]為從節(jié)點0到節(jié)點v的[+h]邊優(yōu)先最短路徑.文獻中定義了[+1]邊優(yōu)先最短路徑,并稱該路徑存在且唯一,“唯一”這個結(jié)論是錯誤的,因為定義沒有強調(diào)[+1]邊和[+h]邊的次序,所以仍有Cxvxv+yv條路徑,只能說xv,yv的值唯一,嚴格來講,文獻中的[+1]邊優(yōu)先最短路徑應(yīng)改稱為:[+1]邊最大最短路徑.從實際情況來看,[+h]邊優(yōu)先最短路徑的概念更有意義,體現(xiàn)更快的接近節(jié)點v的尋徑策略.從定義可知[+h]邊優(yōu)先最短路徑必為最短路徑(是一條特殊的最短路徑),反之不成立.并且,從節(jié)點0到任意節(jié)點v的[+h]邊優(yōu)先最短路徑存在,不僅xv,yv的值唯一,路徑形式也唯一:所有[+h]邊依次在前,所有[+1]邊依次在后.引理2.設(shè)v=kh+r,0≤r<h,則x[+1]+y[+h]是G(N;1,h)中從節(jié)點0到節(jié)點r的[+h]邊優(yōu)先最短路徑的充分必要條件是:x[+1]+(y+k)[+h]是節(jié)點0到節(jié)點v的[+h]邊優(yōu)先最短路徑.證明.必要性.(1)是路徑,因為x[+1]+y[+h]是G(N;1,h)中從0到r的[+h]邊優(yōu)先最短路徑,因而r=x+yh(modN)(由引理1得),代入v=kh+r=kh+x+yh(modN)=x+(y+k)h(modN),所以x[+1]+(y+k)[+h]是0到v的路徑;(2)是最短路徑,用反證法,設(shè)另有x1[+1]+(y1+k)[+h]是0到v的最短路徑,則x1+(y1+k)<x+(y+k)?x1+y1<x+y,由引理1知x1[+1]+y1[+h]是0到r的路徑,所以x[+1]+y[+h]不是0到r的最短路徑,這與已知條件矛盾,因而x[+1]+(y+k)[+h]是0到v的最短路徑;(3)是[+h]邊優(yōu)先最短路徑,用反證法,設(shè)另有x1[+1]+(y1+k)[+h]是0到v的[+h]邊優(yōu)先最短路徑,則x1+(y1+k)=x+(y+k)并且y1+k>y+k?y1>y,由引理1和第2步證明知x1[+1]+y1[+h]是0到r的最短路徑,所以x[+1]+y[+h]不是0到r的[+h]邊優(yōu)先最短路徑,這與已知條件矛盾,因而x[+1]+(y+k)[+h]是0到v的[+h]邊優(yōu)先最短路徑.充分性.(1)是路徑,因為x[+1]+(y+k)[+h]是G(N;1,h)中從0到v的[+h]邊優(yōu)先最短路徑,因而v=x+(y+k)h(modN)(由引理1得),代入v=kh+r?r=v-kh=x+yh(modN),所以x[+1]+y[+h]是0到r的路徑;(2)是最短路徑,用反證法,設(shè)另有x1[+1]+y1[+h]是0到r的最短路徑,則x1+y1<x+y?x1+(y1+k)<x+(y+k),由引理1知x1[+1]+(y1+k)[+h]是0到v的路徑,所以x[+1]+(y+k)[+h]不是0到v的最短路徑,這與已知條件矛盾,因而x[+1]+y[+h]是0到r的最短路徑;(3)是[+h]邊優(yōu)先最短路徑,用反證法,設(shè)另有x1[+1]+y1[+h]是0到r的[+h]邊優(yōu)先最短路徑,則x1+y1=x+y∧y1>y?y1+k>y+k,由引理1和第2步證明知x1[+1]+(y1+k)[+h]是0到v的[+h]邊優(yōu)先最短路徑,所以x[+1]+(y+k)[+h]不是0到v的[+h]邊優(yōu)先最短路徑,這與已知條件矛盾,因而x[+1]+y[+h]是0到r的[+h]邊優(yōu)先最短路徑.證畢.文獻中為了證明其引理3,提出了引理2,其引理2的結(jié)論和證明都是錯誤的(見本文第7節(jié)),其引理3的結(jié)論正確,證明過程有誤,因為它用到其引理2.由定義2和引理2可知,從節(jié)點0到任意節(jié)點v的最短路徑都轉(zhuǎn)化為求0到節(jié)點r(=v-kh)的[+h]邊優(yōu)先最短路徑問題.引理3.設(shè)x[+1]+y[+h]是0到i的[+h]邊優(yōu)先最短路徑,且x≠0,則(x-1)[+1]+y[+h]是0到i-1的[+h]邊優(yōu)先最短路徑.證明.(1)是路徑,因為x[+1]+y[+h]是0到i的[+h]邊優(yōu)先最短路徑,因而i=x+yh(modN)(由引理1得),又有i≠0,x≠0,則i-1=x-1+yh(modN),所以(x-1)[+1]+y[+h]是0到i-1的路徑;(2)是最短路徑,用反證法,設(shè)另有(x1-1)[+1]+y1[+h]是0到i-1的最短路徑,則x1-1+y1<x-1+y?x1+y1<x+y,由引理1知x1[+1]+y1[+h]是0到i的路徑,所以x[+1]+y[+h]不是0到i的最短路徑,這與已知條件矛盾,因而(x-1)[+1]+y[+h]是0到i的最短路徑;(3)是[+h]邊優(yōu)先最短路徑,用反證法,設(shè)另有(x1-1)[+1]+y1[+h]是0到i-1的[+h]邊優(yōu)先最短路徑,則(x1-1)+y1=(x-1)+y并且y1>y,由引理1和第2步證明知x1[+1]+y1[+h]是0到i的最短路徑,所以x[+1]+y[+h]不是0到i的[+h]邊優(yōu)先最短路徑,這與已知條件矛盾,因而(x-1)[+1]+y[+h]是0到i的[+h]邊優(yōu)先最短路徑.由引理3可知,當(dāng)i不是單一[+h]邊優(yōu)先最短路徑節(jié)點時,它與i-1的[+h]邊優(yōu)先最短路徑之間存在遞推關(guān)系.證畢.定理1.設(shè)xi[+1]+yi[+h]是0到i的[+h]邊優(yōu)先最短路徑,則0→i+1的[+h]邊優(yōu)先最短路徑xi+1[+1]+yi+1[+h]滿足:(1)當(dāng)xi+yi+1≤si+1或si+1不存在時,xi+1=xi+1,yi+1=yi;(2)當(dāng)xi+yi+1>si+1時,xi+1=0,yi+1=si+1.其中si+1是0到i+1的單一[+h]邊優(yōu)先最短路徑的長度.這個定理的證明完全同文獻.定義3.稱以下節(jié)點為節(jié)點0所對應(yīng)的“非平常節(jié)點”:0到它們的[+h]邊優(yōu)先最短路徑正好就是0到它們的單一[+h]邊最短路徑.“非平常節(jié)點”正是[+h]邊優(yōu)先尋徑的結(jié)果,有了“非平常節(jié)點”的定義后,與文獻一樣可以求出0所對應(yīng)的在0<i<h范圍內(nèi)的“非平常節(jié)點”.因為當(dāng)0<i<h時,0→i的[+h]邊優(yōu)先最短路徑的長度不會超過i.計算it=t×h(modN)(0<t<h),若0<it<h且t≤it,則記錄(t,it),這些it就是可能的“非平常節(jié)點”.假設(shè)已經(jīng)求出0<i<h范圍內(nèi)所有可能的“非平常節(jié)點”:i1<i2<…<iu,共有u個以及0到它們的單一[+h]邊優(yōu)先最短路徑的長度是si1,si2,…,siu,可以得出如下兩個定理.定理2.確定“非平常節(jié)點”.(1)i1是“非平常節(jié)點”,0到i1的[+h]邊優(yōu)先最短路徑是si1[+h];(2)若si1+(i2-i1)<si2,則i2不是“非平常節(jié)點”,且0到i2的[+h]邊優(yōu)先最短路徑是(i2-i1)[+1]+si1[+h];否則i2是“非平常節(jié)點”,0到i2的[+h]邊優(yōu)先最短路徑是si2[+h];(3)對于3≤j≤u,設(shè)0到ij-1的[+h]邊優(yōu)先最短路徑是xij-1[+1]+yij-1[+h],若(ij-ij-1)+xij-1+yij-1<sij,則ij不是“非平常節(jié)點”,且0到ij的[+h]邊優(yōu)先最短路徑是(ij-ij-1+xij-1)[+1]+yij-1[+h];否則ij是“非平常節(jié)點”.定理3.確定0→h內(nèi)任意點的[+h]邊優(yōu)先最短路徑:設(shè)0<i1<i2<…<iw<h是節(jié)點0所對應(yīng)的在0到h之內(nèi)的所有的w個“非平常節(jié)點”,0到它們的[+h]邊優(yōu)先最短路徑分別是xi1[+1]+yi1[+h],xi2[+1]+yi2[+h],…,xiw[+1]+yiw[+h],則對任意節(jié)點j(ij<j<ij+1),ij和ij+1是“非平常節(jié)點”),0到j(luò)的[+h]邊優(yōu)先最短路徑為(j-ij+xij)[+1]+yij[+h];若j<i1,則0到j(luò)的[+h]邊優(yōu)先最短路徑為j[+1].利用[+h]邊優(yōu)先的最短路徑尋徑策略,將雙環(huán)網(wǎng)絡(luò)的節(jié)點分成p(=[N/h](N=ph+q))個長度為h的等長區(qū)間和一個長度為q的區(qū)間,設(shè)0<i1<i2<…<ir<…<iw<h是0→h區(qū)間內(nèi)的所有的w個“非平常節(jié)點”(ir是r前面的第一個“非平常節(jié)點”),0到它們的[+h]邊優(yōu)先最短路徑分別是si1,si2,…,sir,…,siw,這w+1個區(qū)間的長度分別是li0,li1,li2,…,lir,…,liu,Lh??=max{(sij+lij)|0≤j≤w},Lr??=max{(sij+lij)|0≤j<r},注:si0=0.推論1.在G(N;1,h)中,節(jié)點0到任意節(jié)點v(0<v<N)的最短路徑長度l=k+sir+r-∑j=0r?1lij,其中v=kh+r(0≤r<h),ir是r前面的第一個“非平常節(jié)點”.雙環(huán)網(wǎng)絡(luò)的直徑d=max{p-1+Lh,p+Lr}.k稱為直接模長;sir稱為回轉(zhuǎn)模長,r-∑j=0r?1lij稱為余步,k和sir都是優(yōu)先走單一[+h]邊得來的,r?∑j=0r?1lij是后走單一[+1]邊得來的.這就是優(yōu)先走[+h]邊尋徑的思想.推論2.在G(N;1,h)中,當(dāng)N≥h×(h-1)時,0→h內(nèi)非平常節(jié)點肯定不存在,則0到任意節(jié)點v(0<v<N)的最短路徑長度l=k+r,其中v=kh+r(0≤r<h).雙環(huán)網(wǎng)絡(luò)的直徑d=max{p-1+h-1,p+q},其中N=ph+q.推論3.在G(N;1,h)中,當(dāng)d>p+h-2時,則在0→h內(nèi)至少存在一個“非平常節(jié)點”.證明.假設(shè)0→h內(nèi)不存在“非平常節(jié)點”,則d=p+h-2,則與d>p+h-2與矛盾.所以當(dāng)d>p+h-2時,則在0→h內(nèi)至少存在一個“非平常節(jié)點”.[+h]邊優(yōu)先尋徑可以構(gòu)造一個直觀的模型——“竹筏”FG(1,h),將p(=[N/h])個長度為h的等長區(qū)間和一個長度為q的區(qū)間稱為p+1根竹子,“非平常節(jié)點”是其中的“竹節(jié)”,平常節(jié)點分布在竹節(jié)之間.“竹筏”構(gòu)造如下:(1)將p+1根竹子Fi(0≤i≤p)向右依次擺好;(2)將竹子Fi(0≤i≤p)之間對應(yīng)節(jié)點v0j,v1j,…,vPj(0≤j≤h-1)用一根繩索連起來,最后一根竹子的0≤j≤q;當(dāng)q=0時,稱為矩形“竹筏”;當(dāng)q≠0時,稱為L形“竹筏”.顯然“竹筏”是一種新的L形瓦,與傳統(tǒng)的L形瓦形式一樣,只是節(jié)點擺放的次序不一樣.由“竹筏”的定義,可以得到一些性質(zhì):(1)th,th+1,…,(t+1)h-1這h個節(jié)點必順序擺在第t根竹子上,其中0≤t≤p-1,并且ph,ph+1,…,ph+q-1順序擺在第p根竹子上.(2)設(shè)第i(0≤i≤p-1)根竹子上點j(0≤j≤h-1)的[+h]邊優(yōu)先最短路徑是xij[+1]+yij[+h],則第i+1根竹子上點j的[+h]邊優(yōu)先最短路徑是xij[+1]+(yij+1)[+h].(3)設(shè)第i(0≤i≤p)根竹子上點j的[+h]邊優(yōu)先最短路徑是xij[+1]+yij[+h],則第i根竹子上點j+1的[+h]邊優(yōu)先最短路徑是(xij+1)[+1]+yij[+h],其中,點j和j+1位于同一個“竹節(jié)”之內(nèi).[+h]邊優(yōu)先尋徑的算法同文獻.4基于[+h]邊優(yōu)先尋徑策略的算法用VisualBasic6.0和SQLServer2000編程來實現(xiàn)[+h]邊優(yōu)先尋徑策略的算法,以文獻的DL(39,17)(注:表示G(39;1,17),以下相同)為例,列出最短路徑的一種空間解——“竹筏”,見圖1.5[+1][+h]作者在文獻中提出了[+1][+h]雙邊尋徑策略,得到一種空間解——“螺旋環(huán)”,下面將兩者進行比較.[+h]邊優(yōu)先尋徑策略適合求0到某一個節(jié)點v的一條特殊最短路徑—[+h]邊優(yōu)先最短路徑和該路徑長度;其思路是:固定節(jié)點,尋找路徑;其策略是:優(yōu)先走[+h]邊;其關(guān)鍵是求出0→h內(nèi)的“非平常節(jié)點”;其它節(jié)點的[+h]邊優(yōu)先最短路徑和長度可以由遞推關(guān)系式求出.[+1][+h]雙邊尋徑策略適合求0到所有節(jié)點的所有最短路徑和它們的長度;其思路是:固定路徑,尋找節(jié)點;其策略是:同時走[+1][+h]邊;其關(guān)鍵是記住已訪問節(jié)點集和剛剛訪問節(jié)點集;所有節(jié)點的最短路徑和長度可以直接得出.[+h]邊優(yōu)先尋徑策略的思想只適合單位步長的雙環(huán)網(wǎng)絡(luò),不適合非單位步長的雙環(huán)網(wǎng)絡(luò)和雙環(huán)以上的網(wǎng)絡(luò);它利用了[+1]邊的特殊性.[+1][+h]雙邊尋徑策略的思想不僅適合單位步長的雙環(huán)網(wǎng)絡(luò),還適合非單位步長的雙環(huán)網(wǎng)絡(luò)和雙環(huán)以上的網(wǎng)絡(luò).[+h]邊優(yōu)先尋徑策略得到一個直觀模型——“竹筏”:由p根長度為h的竹子和一根長度為q的竹子組成,“竹節(jié)”代表“非平常節(jié)點”,平常節(jié)點分布在竹節(jié)之間.“竹筏”特點是:竹子長度、竹子上節(jié)點、節(jié)點數(shù)和節(jié)點位置固定;但0到節(jié)點的距離需要計算;竹子之間對應(yīng)節(jié)點和“竹節(jié)”中的節(jié)點[+h]邊優(yōu)先最短路徑存在遞推關(guān)系.這個特點是由其“固定節(jié)點,尋找路徑”的策略決定的.[+1][+h]雙邊尋徑策略得到一個直觀模型——“螺旋環(huán)”:由d+1個環(huán)組成.“螺旋環(huán)”特點是:環(huán)個數(shù)、環(huán)直徑大小、環(huán)上節(jié)點和個數(shù)需要求解;但0到環(huán)的距離固定;同環(huán)節(jié)點到0的距離相等,不同環(huán)之間節(jié)點距離存在簡單關(guān)系—等差為1;所有最短路徑都在“螺旋環(huán)”中出現(xiàn);雙環(huán)網(wǎng)絡(luò)直徑就是頂環(huán)數(shù).這個特點是由其“固定路徑,尋找節(jié)點”的策略決定的.從算法復(fù)雜度來看:[+h]邊優(yōu)先尋徑策略需要復(fù)雜比較、計算和排序,耗時間,但存儲節(jié)點少,少占空間;[+1][+h]雙邊尋徑策略存儲節(jié)點和節(jié)點狀態(tài)多,多占空間,但計算簡單,少耗時間.“竹筏”可以看成是靜態(tài)的空間解,“螺旋環(huán)”體現(xiàn)動態(tài)的空間解.從實現(xiàn)角度看,借助數(shù)據(jù)庫SQLServer來解決存儲,[+1][+h]雙邊尋徑策略更容易實現(xiàn).6雙環(huán)網(wǎng)絡(luò)的直徑從節(jié)點[+h]邊優(yōu)先最短路徑值的角度來說,[+h]邊優(yōu)先尋徑策略得到的直觀模型是“竹筏”;但從節(jié)點擺放位置的角度來說,[+h]邊優(yōu)先尋徑策略得到的直觀模型是一種新的L形瓦,其參數(shù)值不等于相對應(yīng)的傳統(tǒng)L形瓦的參數(shù)值.傳統(tǒng)L形瓦構(gòu)造相對困難,需按規(guī)則構(gòu)造,但計算雙環(huán)網(wǎng)絡(luò)的直徑相對容易.新的L形瓦構(gòu)造相對容易,由h去分割N,然后順序擺放就行,但計算雙環(huán)網(wǎng)絡(luò)的直徑相對困難(見圖1).從節(jié)點值的角度來說,傳統(tǒng)L形瓦是均勻的,其值是連續(xù)變化的;新的L形瓦是非均勻的,其值跳變的.但從節(jié)點位置的角度來說,傳統(tǒng)L形瓦是非均勻的,其順序是跳變的;新的L形瓦是均勻的,其順序是連續(xù)變化的.簡單來說,新的L形瓦易構(gòu)造但難以求其直徑;傳統(tǒng)的L形瓦難以構(gòu)造但易求其直徑;兩者都有其均勻和非均勻的一面.7節(jié)點是“異化點”(1)文獻中的[+1]邊優(yōu)先最短