楊 瀾，段卓輝，鄧宏濤*

（1.江漢大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院，湖北 武漢 430056；2.華中科技大學(xué)服務(wù)計算技術(shù)與系統(tǒng)教育部重點實驗室/集群與網(wǎng)格計算湖北省重點實驗室，湖北 武漢 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*算法實現(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è)計穩(wěn)定樹算法動態(tài)調(diào)整權(quán)值路徑，使其最短權(quán)值路徑保持穩(wěn)定，但真實網(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)可以在較小時間復(fù)雜度內(nèi)求出最優(yōu)解，如SPFA算法［7］等，但當(dāng)帶權(quán)最短路徑問題遇到復(fù)雜的約束條件，權(quán)值最小的貪心思想將不再適用，每次路徑的選擇需嚴(yán)格滿足約束條件，問題規(guī)模從較小復(fù)雜度轉(zhuǎn)化成NP難。最直觀的解決思想就是遍歷所有路徑，查找其滿足約束條件路徑的最小值。雖然這種思路直接明了并能求出精確解，但隨著計算規(guī)模增大，其耗時較高。

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

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

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

為解決復(fù)雜網(wǎng)絡(luò)環(huán)境下帶權(quán)最短路徑問題，首先需要對復(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)最短路徑問題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 實例原圖Fig.1 Example graph

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

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

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

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

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

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

3 測試評估

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

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

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

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

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

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

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

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

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

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

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

圖5 最大跳數(shù)11情況下圖規(guī)模敏感性實驗圖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)最短路徑問題。實驗結(jié)果表明，基于壓縮圖的禁忌搜索算法具有求解快、時間復(fù)雜度低、收斂快、對圖規(guī)模和約束條件不敏感的優(yōu)點。在后續(xù)研究中，筆者將致力于優(yōu)化基于壓縮圖的禁忌搜索算法在稀疏圖上的性能，并考慮加入圖劃分的并行禁忌搜索算法以解決超大規(guī)模圖的問題。