復(fù)雜約束條件下求解帶權(quán)最短路徑方法

楊 瀾，段卓輝，鄧宏濤*

（1.江漢大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北 武漢 430056；2.華中科技大學(xué)服務(wù)計(jì)算技術(shù)與系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室/集群與網(wǎng)格計(jì)算湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074）

0 引言

隨著硬件條件的不斷發(fā)展和RDMA、SDN、NFV技術(shù)的不斷完善，網(wǎng)絡(luò)拓?fù)渥兊迷絹碓綇?fù)雜，網(wǎng)絡(luò)環(huán)境也變得更加復(fù)雜。在復(fù)雜的環(huán)境下，尋找?guī)?quán)最短路徑成為一大挑戰(zhàn)。傳統(tǒng)的搜索算法并不能較好適應(yīng)復(fù)雜的網(wǎng)絡(luò)環(huán)境，回溯算法［1］、深度優(yōu)先算法［2］、A*算法［3］都無法解決復(fù)雜約束條件下的帶權(quán)最短路徑問題，繁雜的約束條件破壞了深度遍歷或廣度遍歷求解帶權(quán)最短路徑的可能，多約束條件下求解帶權(quán)最短路徑成為NP難問題。

為了解決復(fù)雜約束條件下帶權(quán)最短路徑問題，已有研究基于傳統(tǒng)的Dijkstra算法、Floyed算法和A*算法實(shí)現(xiàn)了定路徑規(guī)劃的優(yōu)化算法［4-6］。雖然這些研究嘗試在約束條件下解決帶權(quán)最短路徑問題，但條件建模多偏向于路徑權(quán)值變化的單一約束?；诜€(wěn)定分支的變權(quán)網(wǎng)絡(luò)最優(yōu)路徑算法［4］優(yōu)化了Dijks?tra算法并設(shè)計(jì)穩(wěn)定樹算法動(dòng)態(tài)調(diào)整權(quán)值路徑，使其最短權(quán)值路徑保持穩(wěn)定，但真實(shí)網(wǎng)絡(luò)的約束條件不僅只有權(quán)值變化?；趶?fù)雜權(quán)值優(yōu)化的A*路徑搜索算法［5-6］也是側(cè)重于適應(yīng)復(fù)雜權(quán)值變化，并通過優(yōu)化A*算法求解帶權(quán)最短路徑問題。但該算法與變權(quán)網(wǎng)絡(luò)最優(yōu)路徑算法存在相同的問題，并不能求解出復(fù)雜約束條件下最優(yōu)的帶權(quán)最短路徑可行解。

傳統(tǒng)的帶權(quán)最短路徑算法已經(jīng)可以在較小時(shí)間復(fù)雜度內(nèi)求出最優(yōu)解，如SPFA算法［7］等，但當(dāng)帶權(quán)最短路徑問題遇到復(fù)雜的約束條件，權(quán)值最小的貪心思想將不再適用，每次路徑的選擇需嚴(yán)格滿足約束條件，問題規(guī)模從較小復(fù)雜度轉(zhuǎn)化成NP難。最直觀的解決思想就是遍歷所有路徑，查找其滿足約束條件路徑的最小值。雖然這種思路直接明了并能求出精確解，但隨著計(jì)算規(guī)模增大，其耗時(shí)較高。

剪枝可以減小圖規(guī)模，剔除顯然不滿足約束條件的遍歷路徑從而減小遍歷開銷。剪枝遍歷算法雖然可以解決復(fù)雜條件下的帶權(quán)最短路徑問題，但其算法復(fù)雜度還是隨著圖規(guī)模的變大而急速增加。雖然存在動(dòng)態(tài)剪枝等［8-9］優(yōu)化策略，但其求解的時(shí)間復(fù)雜度還是過于龐大。啟發(fā)性算法雖能解決復(fù)雜約束條件下的帶權(quán)最短路徑問題，如PSO算法［10］、蟻群算法［11］、遺傳退火算法［12］等，但其求解迭代耗時(shí)較高，啟發(fā)路線復(fù)雜，自學(xué)習(xí)不穩(wěn)定，極易陷入局部最優(yōu)的情況。這類算法并不適合直接用于求解復(fù)雜約束條件下帶權(quán)最短路徑問題。

本文將復(fù)雜網(wǎng)絡(luò)環(huán)境中的約束條件抽象成幾類傳統(tǒng)圖中約束條件組合，同時(shí)將實(shí)時(shí)網(wǎng)絡(luò)轉(zhuǎn)化為多種約束的抽象圖。在考慮權(quán)值、頂點(diǎn)約束和邊約束的情況下解決帶權(quán)最短路徑問題。本文提出基于壓縮圖的禁忌搜索算法，通過考慮多種約束條件來對(duì)求解圖進(jìn)行壓縮，并利用優(yōu)化禁忌搜索算法求解帶權(quán)最短路徑。

1 問題描述和網(wǎng)絡(luò)建模

為解決復(fù)雜網(wǎng)絡(luò)環(huán)境下帶權(quán)最短路徑問題，首先需要對(duì)復(fù)雜網(wǎng)絡(luò)環(huán)境中的約束條件進(jìn)行建模，將復(fù)雜網(wǎng)絡(luò)環(huán)境轉(zhuǎn)化為帶約束條件的圖數(shù)據(jù)結(jié)構(gòu)。將網(wǎng)絡(luò)約束條件轉(zhuǎn)化為圖的約束條件組合后即可利用優(yōu)化搜索算法解決復(fù)雜約束條件下帶權(quán)最短路徑問題。

通過對(duì)網(wǎng)絡(luò)環(huán)境中可能存在的一些復(fù)雜約束情況進(jìn)行分析，將其與圖中約束條件對(duì)應(yīng)組合進(jìn)行建模。由此，約束可分為以下4類：必須經(jīng)過的邊；必須經(jīng)過的頂點(diǎn)；不能經(jīng)過的邊；不能超過的最大跳數(shù)。利用上述4種基本約束類可以組合成各種復(fù)雜的網(wǎng)絡(luò)環(huán)境約束條件。下面通過這4種抽象約束條件類對(duì)幾類常見的網(wǎng)絡(luò)環(huán)境情況進(jìn)行分析：

1）服務(wù)點(diǎn)損壞：因?yàn)殚L(zhǎng)時(shí)間工作，很可能導(dǎo)致網(wǎng)絡(luò)中某服務(wù)點(diǎn)產(chǎn)生異常?；诩s束類可將此抽象為與該服務(wù)點(diǎn)鏈接的所有邊都不可達(dá)，這樣就可以在原有的網(wǎng)絡(luò)拓?fù)鋱D中將損壞服務(wù)點(diǎn)剔除。

2）網(wǎng)絡(luò)擁塞：網(wǎng)絡(luò)擁塞是一個(gè)非常復(fù)雜的情況，基于約束類可通過不能經(jīng)過的邊加上必須經(jīng)過的邊和頂點(diǎn)來模擬網(wǎng)絡(luò)協(xié)議中對(duì)擁塞情況下做出的妥協(xié)，并可以利用更新約束條件來形成當(dāng)前環(huán)境下的新網(wǎng)絡(luò)拓?fù)洹?/p>

3）信號(hào)衰減：基于約束類利用最大跳數(shù)來限制數(shù)據(jù)路由能通過的節(jié)點(diǎn)個(gè)數(shù)（路由器）。并通過必須經(jīng)過的節(jié)點(diǎn)（信號(hào)放大器）來實(shí)現(xiàn)長(zhǎng)距離傳輸。

綜上所述，此類約束條件所組合的抽象類確實(shí)能在一定程度上含括復(fù)雜網(wǎng)絡(luò)環(huán)境中的約束。通過利用基礎(chǔ)約束條件抽象類適當(dāng)搭配所形成的約束組合，能將復(fù)雜網(wǎng)絡(luò)環(huán)境轉(zhuǎn)化為多種約束條件的傳統(tǒng)圖。

2 算法設(shè)計(jì)和實(shí)現(xiàn)

在對(duì)NP難圖算法問題的研究中，圖的規(guī)模大小是影響求解NP難問題的重要因素。圖劃分通過圖壓縮提升尋找最短路徑的效率［13］。雖然剪枝算法能在一定程度上壓縮圖規(guī)模，但其壓縮過程是在DFS遍歷過程中進(jìn)行，實(shí)際上并不能有效降低圖規(guī)模。本文提出了一種針對(duì)復(fù)雜約束條件的圖壓縮算法，并介紹了基于圖壓縮的禁忌搜索算法。

圖壓縮算法的具體步驟如下（原圖中的點(diǎn)為頂點(diǎn)，壓縮圖中的點(diǎn)為節(jié)點(diǎn)）：

1）選取原圖中的必過頂點(diǎn)、起點(diǎn)、終點(diǎn)作為壓縮圖的節(jié)點(diǎn)。

2）利用SPFA算法計(jì)算原圖中滿足最大跳數(shù)的任意兩點(diǎn)之間的最短路徑權(quán)值，并記錄其對(duì)應(yīng)跳數(shù)和路徑。

3）取壓縮圖中的任意兩節(jié)點(diǎn)，并取步驟2）中所算出的原圖中此兩點(diǎn)的最短路徑權(quán)值和作為壓縮圖此兩點(diǎn)邊上的權(quán)值，反復(fù)這一步驟直到壓縮圖形成完全圖。

4）找到原圖中必過邊對(duì)應(yīng)的頂點(diǎn)，并將這兩頂點(diǎn)在壓縮圖中的邊權(quán)值賦值為必過邊權(quán)值，并改動(dòng)步驟2）中記錄下來的最短路徑權(quán)值、對(duì)應(yīng)跳數(shù)和路徑。

壓縮圖必定包含約束條件中的必定經(jīng)過頂點(diǎn)。在新構(gòu)造的壓縮圖中，只存放起點(diǎn)、終點(diǎn)、必須經(jīng)過頂點(diǎn)。之后利用SPFA算法計(jì)算新構(gòu)造的壓縮圖中任意兩點(diǎn)在原圖中的帶權(quán)最短路徑，將計(jì)算出來的值記為新壓縮圖中邊的權(quán)值。同時(shí)記錄壓縮圖節(jié)點(diǎn)間在原圖中的最短路徑和跳數(shù)。壓縮圖減少了頂點(diǎn)數(shù)量，只保留必須經(jīng)過頂點(diǎn)，減少了圖規(guī)模。此時(shí)壓縮過的完全圖中所有邊的權(quán)值為原圖中頂點(diǎn)間最短路徑權(quán)值。

如圖1所示，頂點(diǎn)0到3間存在必過邊，頂點(diǎn)3為必過頂點(diǎn)，起點(diǎn)為0，終點(diǎn)為5。若使用上述方法進(jìn)行壓縮則可能去掉必過約束邊。因此，在壓縮過程中，如果存在必過邊，那么這兩個(gè)頂點(diǎn)間的最短路徑為必過邊，權(quán)值為必過邊權(quán)值（見圖2）。

圖1 實(shí)例原圖Fig.1 Example graph

圖2 最終壓縮圖Fig.2 Final compression graph

在圖壓縮算法中，SPFA以權(quán)重優(yōu)先查找最短路徑［14］，這會(huì)舍去跳數(shù)低的高權(quán)值路線，從而因不滿足跳數(shù)約束條件導(dǎo)致無解。筆者在圖壓縮算法查找最短路徑的SPFA中加入了最大跳數(shù)約束，避免在圖壓縮過程中失去可行解。

雖然圖壓縮算法縮小了原圖規(guī)模，但因壓縮圖是一個(gè)由必過節(jié)點(diǎn)組成的完全圖，其圖復(fù)雜程度和必過節(jié)點(diǎn)數(shù)息息相關(guān)。如果當(dāng)約束條件中必過頂點(diǎn)個(gè)數(shù)較多時(shí)，壓縮圖規(guī)模還是會(huì)較大，若此時(shí)使用剪枝DFS算法求解，則依舊是NP難問題。所以為了避免這種情況的發(fā)生，本文使用禁忌搜索算法對(duì)壓縮圖的帶權(quán)最短路徑進(jìn)行求解。

因壓縮圖是由必過頂點(diǎn)組成的完全圖，所以壓縮圖上的單源最短路徑（single-source shortest path，SSSP）問題就被轉(zhuǎn)化為了旅行家問題（traveling salesman problem，TSP）［15］。通過設(shè)計(jì)禁忌搜索算法（Tabu search algorithm）以適應(yīng)壓縮后圖規(guī)模依舊過大的特殊情況。

在禁忌搜索算法中，首先按照隨機(jī)方法產(chǎn)生一個(gè)初始解作為當(dāng)前解，隨后在當(dāng)前解的鄰域中搜索若干個(gè)解，取其中的最優(yōu)解作為新的當(dāng)前解。為了避免陷入局部最優(yōu)解，算法允許一定的下山操作，使解的質(zhì)量變差從而激活搜索，以偏向全局最優(yōu)解。另外，為了避免對(duì)已搜索過的局部最優(yōu)解重復(fù)搜索，本算法使用禁忌表記錄已搜索的局部最優(yōu)解歷史信息，從而使搜索過程避開局部極值點(diǎn)，從而開辟新的搜索區(qū)域。

在搜索中構(gòu)造一個(gè)短期循環(huán)記憶禁忌表，禁忌表中存放剛剛進(jìn)行過的T（T為禁忌表長(zhǎng)度）個(gè)鄰居的移動(dòng)，這種移動(dòng)即解的簡(jiǎn)單變化。禁忌表中的移動(dòng)稱為禁忌移動(dòng)。對(duì)于進(jìn)入禁忌表中的移動(dòng)，在以后的T次循環(huán)內(nèi)是禁止的，以避免回到原來的解，從而避免陷入死循環(huán)。T次循環(huán)后禁忌解除。禁忌表是一個(gè)循環(huán)表，在搜索過程中被循環(huán)修改，使禁忌表始終保持T個(gè)移動(dòng)。即使引入了禁忌表，禁忌搜索仍可能出現(xiàn)循環(huán)。當(dāng)?shù)鷥?nèi)所發(fā)現(xiàn)的最好解無法改進(jìn)或無法離開它時(shí)，算法停止。

3 測(cè)試評(píng)估

實(shí)驗(yàn)的硬件測(cè)試環(huán)境：CPU為主頻2.6 GHz的20核Intel（R）Xeon（R）CPU E5-2670，內(nèi)存大小64 GB。實(shí)驗(yàn)采用CentOS 7系統(tǒng)，內(nèi)核版本為4.7.0。

測(cè)試案例使用中興提供（http://challenge.zte.net/activity.php?mod=info#title2）的網(wǎng)絡(luò)測(cè)試案例拓?fù)洌鐖D3所示。綠色節(jié)點(diǎn)為必須經(jīng)過頂點(diǎn)，綠色邊為必須經(jīng)過邊，紅色邊為無法通過邊。對(duì)DFS剪枝、壓縮圖剪枝、壓縮圖禁忌搜索算法進(jìn)行測(cè)試。

圖3 中興網(wǎng)絡(luò)測(cè)試拓?fù)銯ig.3 Topology of ZTE network test

3.1 算法對(duì)最大跳數(shù)約束條件的敏感性

通過運(yùn)用控制變量法將約束邊、約束頂點(diǎn)保持不變，并調(diào)整同一案例上允許的最大跳數(shù)來測(cè)試算法運(yùn)行時(shí)間。在中興網(wǎng)絡(luò)測(cè)試拓?fù)渖希謩e設(shè)置最大跳數(shù)為11、12、13、14跳，并測(cè)試各算法的運(yùn)行時(shí)間，結(jié)果如圖4所示。

圖4 算法測(cè)試結(jié)果Fig.4 Results of the algorithm test

從實(shí)驗(yàn)結(jié)果可以看出，DFS剪枝算法對(duì)最大跳數(shù)約束是敏感的，不論是在原圖還是壓縮圖，其運(yùn)行時(shí)間都隨最大跳數(shù)增加而增加。當(dāng)約束條件規(guī)模變大時(shí)，其性能將會(huì)變差。從圖4中可以發(fā)現(xiàn)，基于壓縮圖的DFS剪枝性能要大幅優(yōu)于原圖DFS剪枝，這說明圖壓縮算法起到了化簡(jiǎn)圖的作用，并大大提高了DFS剪枝算法的性能。而壓縮圖禁忌搜索算法對(duì)最大跳數(shù)不敏感，當(dāng)圖規(guī)模變大，其運(yùn)行時(shí)間不會(huì)明顯增加，并且耗時(shí)遠(yuǎn)小于DFS剪枝。這說明壓縮圖禁忌搜索算法并不會(huì)因?yàn)榧s束條件規(guī)模增大而性能變差。

3.2 圖規(guī)模對(duì)算法性能的影響

為了探究算法性能優(yōu)化是否會(huì)因圖規(guī)模大小而不同，控制最大跳數(shù)不變，觀察圖規(guī)模變化對(duì)算法的影響。為了滿足測(cè)試需要，筆者構(gòu)建了相同約束數(shù)量，不同圖規(guī)模的測(cè)試用例數(shù)據(jù)見表1。

表1 不同規(guī)模圖用例表Tab.1 Cases table of different size graphs

設(shè)定最大跳數(shù)為11跳，并記錄不同算法對(duì)應(yīng)的運(yùn)行時(shí)間，結(jié)果如圖5所示。DFS剪枝算法和壓縮圖DFS剪枝算法整體上對(duì)圖規(guī)模敏感，雖耗時(shí)呈現(xiàn)線性上漲的趨勢(shì)，但存在明顯波動(dòng)。筆者分析了這些波動(dòng)點(diǎn)（DFS剪枝在case 1、case 3、case 5上約束11跳和壓縮圖DFS剪枝在case 1上約束11跳），在case 3和case 5上設(shè)置約束跳為12跳進(jìn)行重復(fù)實(shí)驗(yàn)，此時(shí)運(yùn)行時(shí)間恢復(fù)正常增加趨勢(shì)。由于case 1、case 3和case 5用例上存在一個(gè)11跳的無解空間，導(dǎo)致DFS在深度遍歷的情況下找不到11跳的滿足條件，提前剪枝，大大收縮了圖規(guī)模，從而導(dǎo)致敏感性波動(dòng)。但從整體趨勢(shì)來說，DFS剪枝算法、壓縮圖DFS剪枝算法都對(duì)圖規(guī)模敏感，并隨著圖規(guī)模的增加使得運(yùn)行時(shí)間增加，這說明DFS算法不能適用于大規(guī)模圖的求解。而壓縮圖禁忌搜索算法對(duì)圖規(guī)模并不敏感，并且能在較小耗時(shí)求解。這說明了壓縮圖禁忌搜索算法能較好求解具有約束條件的大規(guī)模圖。

圖5 最大跳數(shù)11情況下圖規(guī)模敏感性實(shí)驗(yàn)圖Fig.5 Figure scale sensitivity test with maximum hops 11

4 結(jié)語

文本旨在解決復(fù)雜網(wǎng)絡(luò)環(huán)境下求解帶權(quán)最短路徑（開銷最短路徑）問題，并提出了基于壓縮圖的禁忌搜索算法。通過圖壓縮算法，將復(fù)雜約束條件下的帶權(quán)最短路徑問題轉(zhuǎn)化為旅行家問題（TSP），再通過優(yōu)化禁忌搜索算法求解復(fù)雜約束條件下帶權(quán)最短路徑問題。實(shí)驗(yàn)結(jié)果表明，基于壓縮圖的禁忌搜索算法具有求解快、時(shí)間復(fù)雜度低、收斂快、對(duì)圖規(guī)模和約束條件不敏感的優(yōu)點(diǎn)。在后續(xù)研究中，筆者將致力于優(yōu)化基于壓縮圖的禁忌搜索算法在稀疏圖上的性能，并考慮加入圖劃分的并行禁忌搜索算法以解決超大規(guī)模圖的問題。