廖志芳 陳亮名 彭志文 李嚴(yán)冰

(中南大學(xué)軟件學(xué)院 湖南 長(zhǎng)沙 410075)

基于節(jié)點(diǎn)壓縮的尋徑優(yōu)化算法

廖志芳 陳亮名 彭志文 李嚴(yán)冰

(中南大學(xué)軟件學(xué)院 湖南 長(zhǎng)沙 410075)

最短路徑問(wèn)題是一個(gè)經(jīng)典問(wèn)題，而目前的研究大多是針對(duì)給定起點(diǎn)和終點(diǎn)，選擇從起點(diǎn)到終點(diǎn)的最短路徑，且取得了不少成果。而對(duì)于限定時(shí)間的最短路徑問(wèn)題的研究成果相對(duì)較少，這類(lèi)問(wèn)題在現(xiàn)實(shí)生活中卻隨處可見(jiàn)。針對(duì)這一問(wèn)題提出幾種限定時(shí)間的尋徑優(yōu)化算法，從對(duì)回溯法的改進(jìn)到不同的節(jié)點(diǎn)壓縮的方法，給出改進(jìn)的回溯法以及三種基于節(jié)點(diǎn)壓縮的尋徑算法。算法實(shí)現(xiàn)在限定的時(shí)間內(nèi)從起點(diǎn)出發(fā)經(jīng)過(guò)給定的節(jié)點(diǎn)集合再到達(dá)終點(diǎn)的路徑選擇，并針對(duì)不同復(fù)雜度的網(wǎng)絡(luò)圖有相應(yīng)合適的算法可以選擇，從而有效地解決這類(lèi)問(wèn)題。

最短路徑 限定時(shí)間 節(jié)點(diǎn)壓縮 尋徑

0 引 言

圖論中單源最短路徑問(wèn)題[1-3]是一個(gè)經(jīng)典問(wèn)題，其在實(shí)際生活中應(yīng)用廣泛，如網(wǎng)絡(luò)路由路徑選擇、車(chē)載導(dǎo)航、旅行路線等。解決這一問(wèn)題的經(jīng)典算法是Dijkstra EW.A于1959年提出的Dijkstra算法。但這一算法不能解決從起點(diǎn)開(kāi)始必須經(jīng)過(guò)指定的中間節(jié)點(diǎn)再到達(dá)終點(diǎn)的問(wèn)題，然而這類(lèi)問(wèn)題實(shí)用性更強(qiáng)，比如：

(1) “郵遞員問(wèn)題”：郵遞員從郵局出發(fā)為有信件的居民送完信件后回家，在給定的時(shí)間內(nèi)為該郵遞員選擇一條行駛距離最短的路線；

(2) “旅行家問(wèn)題”[4-6]：在指定的時(shí)間內(nèi)為旅行者計(jì)算出一條旅行路線，從指定地點(diǎn)出發(fā)，到達(dá)指定旅游景點(diǎn)再到達(dá)指定目的地，要求路線的總行駛距離或者總行駛開(kāi)銷(xiāo)最短。

(3) “網(wǎng)絡(luò)尋徑問(wèn)題”[7-9]：在指定的時(shí)間內(nèi)為網(wǎng)絡(luò)數(shù)據(jù)傳輸尋找一條有效路徑，且這些數(shù)據(jù)必須經(jīng)過(guò)某些網(wǎng)絡(luò)站點(diǎn)，到達(dá)指定的站點(diǎn)，使得網(wǎng)絡(luò)開(kāi)銷(xiāo)最小。

這些問(wèn)題最終都可以歸納為同一個(gè)圖論問(wèn)題，即在一個(gè)帶權(quán)有向圖中，從起點(diǎn)經(jīng)過(guò)指定的中間節(jié)點(diǎn)，到達(dá)終點(diǎn)，要求在指定時(shí)間內(nèi)，尋找有效路徑，并計(jì)算這些路徑的權(quán)重，選擇一條權(quán)重最低的路徑作為結(jié)果路徑。

對(duì)于這一類(lèi)問(wèn)題，可以采用對(duì)整個(gè)圖進(jìn)行遍歷，尋找一條最短路徑。雖然從理論上來(lái)說(shuō)這種遍歷算法最終能夠得到最優(yōu)解，但是其時(shí)間復(fù)雜度相當(dāng)高。針對(duì)這一問(wèn)題，本文提出了時(shí)間限制的節(jié)點(diǎn)壓縮尋徑算法。該算法通過(guò)采用節(jié)點(diǎn)壓縮，將尋徑過(guò)程中得到的有用信息使用到搜索條件、調(diào)整子節(jié)點(diǎn)順序等方法，改善了傳統(tǒng)算法時(shí)間復(fù)雜度太高的問(wèn)題，為這類(lèi)問(wèn)題的解決給出了有效的辦法。

1 問(wèn)題描述

1.1 問(wèn)題的數(shù)學(xué)模型

給定一個(gè)帶權(quán)有向圖G(V,E),其中:V={1,2,…,n}為頂點(diǎn)集，E={eij=(i,j)|i,j∈V,i≠j}為邊集。dij(i,j∈V,i≠j)為頂點(diǎn)i到j(luò)的權(quán)重，其中:dij>0且dij≠∞，同時(shí)dij和dji可以不相等。V′={1′,2′,…,n′}∈V，給定起點(diǎn)s和終點(diǎn)t，s,t∈V且s，t不屬于V′，要求在給定時(shí)間內(nèi)求序列A={a1,a2,…,an},其中:a1=s,an=t，V′中的所有元素都必須在序列A中出現(xiàn)，并使得以按照序列A在圖中形成的路徑的所有邊的權(quán)重之和盡可能小，且路徑中不能出現(xiàn)環(huán)路。該問(wèn)題的數(shù)學(xué)模型定義如下：

(1)

∑i≠jXij=1i∈V

(2)

∑i≠jXij=1j∈V

(3)

∑Xsj=1j∈Vj≠s

(4)

∑Xjs=0j∈Vj≠s

(5)

∑Xit=1i∈Vi≠t

(6)

∑Xti=1i∈Vi≠t

(7)

為了限制路徑中不會(huì)出現(xiàn)無(wú)關(guān)的回路，作如下約束：

∑i,j∈VXij=|A|

(8)

為了方便后續(xù)描述，給出以下兩個(gè)定義：

定義1關(guān)鍵節(jié)點(diǎn)：?jiǎn)栴}描述中給定的起始節(jié)點(diǎn)s和終點(diǎn)t以及必經(jīng)節(jié)點(diǎn)的集合V′為關(guān)鍵節(jié)點(diǎn)。

定義2自由節(jié)點(diǎn)：除關(guān)鍵節(jié)點(diǎn)以外的所有節(jié)點(diǎn)都是自由節(jié)點(diǎn)。

1.2 簡(jiǎn)單樣例

如圖1所示的帶權(quán)有向圖G，分別有0、1、2、3共四個(gè)節(jié)點(diǎn)，即C={0,1,2,3}，圖中有0、1、2、3、4、5、6七條邊，即E={0,1,2,3,4,5,6}，邊的權(quán)重為{d01=1,d02=2,d03=1,d21=3,d31=1,d23=1,d32=1},如果此時(shí)需要尋找從0到1的路徑，且必須經(jīng)過(guò)頂點(diǎn)2和3，則V′={2,3}。對(duì)于該問(wèn)題，可以從圖中找到如下兩條可用路徑：0->2->3->1和0->3->2->1。由于第一條路徑各條邊的權(quán)重和為4，第二條路徑各條邊的權(quán)重和為5，所以此時(shí)最優(yōu)解應(yīng)該為0->2->3->1。

圖1 問(wèn)題的簡(jiǎn)單樣例

2 改進(jìn)的回溯法(IBA)

使用回溯法求解該問(wèn)題時(shí)，理論上可以得到最優(yōu)解，且可以得到所有解，但是回溯法沒(méi)有有效地利用在搜索過(guò)程中構(gòu)造的信息以及已求得的可行解，使其作為下一步搜索的優(yōu)化條件。本節(jié)通過(guò)對(duì)回溯法進(jìn)行改進(jìn)，提出改進(jìn)的回溯法，在算法每次搜索完上一節(jié)點(diǎn)后，并在搜索下一節(jié)點(diǎn)之前，利用已有的信息和已求出的可行解來(lái)添加搜索規(guī)則，從而對(duì)搜索方式進(jìn)行改進(jìn)，使得算法在運(yùn)行過(guò)程中，利用已有的信息和已求出的可行解來(lái)提高搜索效率。

改進(jìn)回溯法中的添加規(guī)則表示如下：

規(guī)則1如果下一節(jié)點(diǎn)是終點(diǎn)，而當(dāng)前路徑?jīng)]有經(jīng)過(guò)必經(jīng)節(jié)點(diǎn)集合中的所有節(jié)點(diǎn)，則回溯，繼續(xù)搜索下一節(jié)點(diǎn)。這一規(guī)則可以避免許多無(wú)效解的生成，以期提高算法效率。

規(guī)則2如果當(dāng)前路徑權(quán)重加上到達(dá)下一節(jié)點(diǎn)的那條邊的權(quán)重大于等于當(dāng)前已求得的權(quán)重最小的可行解的路徑，則回溯，繼續(xù)搜索下一節(jié)點(diǎn)。由于當(dāng)前已經(jīng)搜索到可行的路徑，如果當(dāng)前路徑權(quán)重加上下一節(jié)點(diǎn)的權(quán)重不小于已有路徑權(quán)重，那么接下來(lái)繼續(xù)搜索就沒(méi)有任何意義，因?yàn)閱?wèn)題是求解權(quán)重盡量小的路徑。

規(guī)則3對(duì)于不是終點(diǎn)而且沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)，要避免進(jìn)入搜索。如果某節(jié)點(diǎn)不是終點(diǎn)，又沒(méi)有子節(jié)點(diǎn)，到達(dá)該節(jié)點(diǎn)后無(wú)法繼續(xù)下去，因此這種節(jié)點(diǎn)是沒(méi)有必要搜索的，甚至可以在圖中直接刪除。

改進(jìn)回溯法算法的關(guān)鍵偽代碼如下：

Improved-Backtrack(G)

1 node=start

2 while usedtime

3 nodes.add(node)

4 record information include route and weigths

5 for i=1 to children.length

6 add search rule

7 Improvedacktrack(children[i])

8 if result ！=null-B

9 return result and weight

10 else

11 return NA

3 節(jié)點(diǎn)壓縮的搜索算法

雖然改進(jìn)的回溯算法在一定程度上可以提高搜索效率，但是隨著圖規(guī)模的增大，解空間的增長(zhǎng)，改進(jìn)的回溯法的復(fù)雜度也隨之提高。為降低算法復(fù)雜度，本文提出了新算法—基于節(jié)點(diǎn)壓縮的搜索算法NCSA(Node Compression based Search Algorithm)。

隨著圖規(guī)模的增大，圖中的路徑也隨之?dāng)U大，而所求路徑是從起點(diǎn)到終點(diǎn)且經(jīng)過(guò)中間節(jié)點(diǎn)的路徑，因此可以先將圖進(jìn)行預(yù)處理，對(duì)圖的總節(jié)點(diǎn)數(shù)進(jìn)行壓縮，去掉無(wú)關(guān)的節(jié)點(diǎn)和價(jià)值較低的路徑片段，盡量只保留需要的路徑，從而達(dá)到簡(jiǎn)化整個(gè)圖、縮小解空間、提高搜索效率的目的。

3.1 節(jié)點(diǎn)壓縮算法(NCA)

本算法要解決的問(wèn)題具有如下情況：如有節(jié)點(diǎn)比較偏僻，只能到達(dá)一個(gè)其他節(jié)點(diǎn)(即只有一個(gè)子節(jié)點(diǎn))，當(dāng)算法搜索過(guò)程中到達(dá)這樣的節(jié)點(diǎn)時(shí)，只會(huì)往它唯一的子節(jié)點(diǎn)往下走。每經(jīng)過(guò)該節(jié)點(diǎn)一次就要這樣走一次，這樣簡(jiǎn)單而又重復(fù)的計(jì)算是可以避免的。

解決辦法就是采用節(jié)點(diǎn)壓縮的方法，將經(jīng)過(guò)該類(lèi)型節(jié)點(diǎn)的唯一路徑在搜索算法第一次經(jīng)過(guò)時(shí)就記錄下來(lái)，并將這一節(jié)點(diǎn)移除，只保留這一路徑信息。當(dāng)下次搜索到達(dá)該節(jié)點(diǎn)時(shí)，直接使用已存在的路徑信息，避免重復(fù)搜索計(jì)算。移除節(jié)點(diǎn)之后的圖總節(jié)點(diǎn)數(shù)目減少，因此經(jīng)過(guò)壓縮之后的圖將更容易搜索出更好的解。

過(guò)程如圖2所示。

圖2 壓縮搜索算法的基本思想

圖中節(jié)點(diǎn)1只有1個(gè)子節(jié)點(diǎn)2，節(jié)點(diǎn)1到節(jié)點(diǎn)2的權(quán)重為2，路徑為“1”，壓縮過(guò)程就是將節(jié)點(diǎn)1的信息合并到節(jié)點(diǎn)2上，節(jié)點(diǎn)2成為節(jié)點(diǎn)0的直接子節(jié)點(diǎn)，壓縮之后，節(jié)點(diǎn)0到節(jié)點(diǎn)2的權(quán)重就變?yōu)?，節(jié)點(diǎn)0到節(jié)點(diǎn)2的路徑變?yōu)椤?|1”。這樣就有效地將節(jié)點(diǎn)1移除了，并將節(jié)點(diǎn)1到2的路徑保留在節(jié)點(diǎn)2的信息中。當(dāng)下次搜索算法到達(dá)節(jié)點(diǎn)0時(shí)，可以直接使用節(jié)點(diǎn)2中保留的信息，而無(wú)需再次搜索節(jié)點(diǎn)1。

3.2 完全壓縮算法(CCA)

由于節(jié)點(diǎn)壓縮算法(NCA)的目標(biāo)是針對(duì)只有一個(gè)子節(jié)點(diǎn)的自由節(jié)點(diǎn)，如果圖中這樣的節(jié)點(diǎn)個(gè)數(shù)較多，那么算法的效率提高就比較明顯。但是如果圖中這樣的節(jié)點(diǎn)很少甚至沒(méi)有，那么基本壓縮策略的效果就不明顯，甚至?xí)](méi)有任何效果，因而利用壓縮方法的搜索算法在這種情況下并沒(méi)有效果。

針對(duì)NCA算法的這一問(wèn)題，本文提出了更有效的壓縮策略，針對(duì)所有的自由節(jié)點(diǎn)進(jìn)行壓縮，從而有效地對(duì)圖中節(jié)點(diǎn)進(jìn)行壓縮，降低圖的復(fù)雜度，提高搜索效率。

該問(wèn)題集中在尋找從起點(diǎn)到終點(diǎn)并經(jīng)過(guò)中間節(jié)點(diǎn)集合的不成環(huán)的路徑，使得路徑上各條邊的權(quán)重盡可能小。當(dāng)圖中節(jié)點(diǎn)互相之間的可達(dá)關(guān)系比較復(fù)雜時(shí)，從一個(gè)節(jié)點(diǎn)到達(dá)另一個(gè)節(jié)點(diǎn)的可行路徑會(huì)很多，由于問(wèn)題要求必須經(jīng)過(guò)中間節(jié)點(diǎn)集合V′,且中間節(jié)點(diǎn)集合中的各個(gè)節(jié)點(diǎn)之間的可達(dá)路徑也會(huì)有多條。而最終解只會(huì)從這些路徑中選擇一條作為它的一個(gè)片段，因此，找出所有可達(dá)路徑，并盡可能保存權(quán)重最小的一條路徑，當(dāng)搜索算法到達(dá)相應(yīng)的節(jié)點(diǎn)時(shí)可以直接使用這些保存好的路徑。而原路徑上的自由節(jié)點(diǎn)則可以從圖中移除，從而減少了圖中的節(jié)點(diǎn)。使用這種壓縮方法壓縮后的圖中，僅存在起點(diǎn)、終點(diǎn)、中間節(jié)點(diǎn)集合以及它們之間互通的路徑信息，這樣就在很大程度上簡(jiǎn)化了整個(gè)圖，更加有效地進(jìn)行了壓縮。

3.3 改進(jìn)的完全壓縮算法(ICCA)

為進(jìn)一步改善壓縮效果，本文繼續(xù)進(jìn)行節(jié)點(diǎn)壓縮的調(diào)整和改進(jìn)。

1) 調(diào)整子節(jié)點(diǎn)順序使之按照權(quán)重大小順序排序

由于在搜索過(guò)程中，可以當(dāng)前可行解的權(quán)重為基礎(chǔ)進(jìn)行搜索(參照基本搜索算法的改進(jìn)規(guī)則2)，將子節(jié)點(diǎn)的順序按照權(quán)重大小從小到大排序，搜索時(shí)先搜索權(quán)重小的子節(jié)點(diǎn)，則權(quán)重較小的路徑就有可能先得到。根據(jù)搜索策略就可以跳過(guò)一些權(quán)重較大的路徑，減少不必要的搜索過(guò)程，提高效率。

2) 調(diào)整子節(jié)點(diǎn)順序，使之按照經(jīng)過(guò)的節(jié)點(diǎn)的個(gè)數(shù)從小到大的順序排序

從概率的角度來(lái)講，如果經(jīng)過(guò)的節(jié)點(diǎn)個(gè)數(shù)越多，那么新加入一個(gè)節(jié)點(diǎn)時(shí)產(chǎn)生重復(fù)路徑的可能性就越大。因此，在權(quán)重相同的基礎(chǔ)上，優(yōu)先選擇那些經(jīng)過(guò)節(jié)點(diǎn)個(gè)數(shù)較少的子節(jié)點(diǎn)，在后續(xù)選擇路徑時(shí)尋找沒(méi)有重復(fù)節(jié)點(diǎn)的過(guò)程就越簡(jiǎn)單，從而更容易尋找符合條件的路徑。

3) 去掉子節(jié)點(diǎn)中權(quán)重較大的子節(jié)點(diǎn)

該條件是針對(duì)復(fù)雜程度很高的圖，壓縮之后剩下的節(jié)點(diǎn)基本可以?xún)蓛尚纬陕窂健ａ槍?duì)這樣的情況，為了降低圖的復(fù)雜度，對(duì)于圖中某些子節(jié)點(diǎn)，因其權(quán)重比較大，雖然經(jīng)過(guò)該節(jié)點(diǎn)有能夠到達(dá)終點(diǎn)的有效路徑，但由于其權(quán)重過(guò)大，該路徑可能是結(jié)果不太好的路徑。去掉這些權(quán)重較高的異常關(guān)系，可以降低圖的復(fù)雜度，提高搜索效率，另一方面，也避免了搜索這些點(diǎn)耗費(fèi)的時(shí)間，從而更快地搜索權(quán)重較低的路徑。

經(jīng)過(guò)分析，IBA的空間復(fù)雜度為O(n)，NCA、CCA及ICCA的空間復(fù)雜度為O(n2),其中n為圖中總節(jié)點(diǎn)個(gè)數(shù)。

4 實(shí)驗(yàn)驗(yàn)證

4.1 數(shù)據(jù)說(shuō)明及分析

為了不失一般性，實(shí)驗(yàn)數(shù)據(jù)采取“2016年華為軟件精英大賽”的多個(gè)用例，這些用例來(lái)自華為公司在建設(shè)網(wǎng)絡(luò)時(shí)的路由器交換機(jī)等網(wǎng)絡(luò)元素構(gòu)成的網(wǎng)絡(luò)拓?fù)鋱D。

1) 問(wèn)題描述

給定一個(gè)帶權(quán)重的有向圖G=(V,E)，V為頂點(diǎn)集，E為有向邊集，每一條有向邊均包含權(quán)重。對(duì)于給定的頂點(diǎn)s、t，以及V的子集V′，在給定的時(shí)間內(nèi)，尋找從s到t的不成環(huán)有向路徑P，使得P經(jīng)過(guò)V′中所有的頂點(diǎn)(對(duì)經(jīng)過(guò)V′中節(jié)點(diǎn)的順序不做要求)，并使得路徑P上的所有有向邊的權(quán)重之和盡可能小。

2) 數(shù)據(jù)說(shuō)明

(1) 圖中所有權(quán)重均為[1，20]內(nèi)的整數(shù)；

(2) 任一有向邊的起點(diǎn)不等于終點(diǎn)；

(3) 連接頂點(diǎn)A至頂點(diǎn)B的有向邊可能超過(guò)一條，其權(quán)重可能一樣，也可能不一樣；

(4) 有向圖的頂點(diǎn)不會(huì)超過(guò)600個(gè)，每個(gè)頂點(diǎn)出度(以該點(diǎn)為起點(diǎn)的有向邊數(shù)量)不超過(guò)8；

(5)V′中元素個(gè)數(shù)不超過(guò)50；

(6) 從s到t的不成環(huán)有向路徑P是指，P為由一系列有向邊組成的從s至t的有向連通路徑，且不允許重復(fù)經(jīng)過(guò)任一節(jié)點(diǎn)；

(7) 路徑的權(quán)重是指所有組成該路徑的所有有向邊的權(quán)重之和。

3) 數(shù)據(jù)格式

(1) 圖的數(shù)據(jù)中，每一行包含如下的信息：{LinkID,SourceID,DestinationID,Cost}，其中LinkID為該有向邊的索引，SourceID為該有向邊的起始頂點(diǎn)的索引，DestinationID為該有向邊的終止頂點(diǎn)的索引，Cost為該有向邊的權(quán)重。頂點(diǎn)與有向邊的索引均從0開(kāi)始 編號(hào)(不一定連續(xù)，但用例保證索引不重復(fù))。

(2) 路徑信息中，只有一行如下數(shù)據(jù)：SourceID,DestinationID,IncludingSet。其中，SourceID為該路徑的起點(diǎn)，DestinationID為該路徑的終點(diǎn)，IncludingSet表示必須經(jīng)過(guò)的頂點(diǎn)集合V′，其中不同的頂點(diǎn)索引之間用“|”分割。

4) 實(shí)驗(yàn)環(huán)境

Windows7 64位操作系統(tǒng)，處理器為Intel core i5，jre1.6，32位Java虛擬機(jī)，可占用的最大內(nèi)存為2 GB。

4.2 實(shí)驗(yàn)方法及結(jié)果分析

1) IBA、NCA、CCA的比較

為了驗(yàn)證回溯法，IBA、NCA以及CCA之間的效果，將進(jìn)行四組實(shí)驗(yàn)，求解時(shí)間限定為10秒，從實(shí)驗(yàn)1到實(shí)驗(yàn)4將會(huì)逐漸增加圖中的總節(jié)點(diǎn)個(gè)數(shù)和圖中邊的條數(shù)，而中間節(jié)點(diǎn)個(gè)數(shù)保持不變。實(shí)驗(yàn)將從最終結(jié)果路徑的權(quán)重,找出最終結(jié)果的使用時(shí)間兩個(gè)維度進(jìn)行比較。

實(shí)驗(yàn)1總節(jié)點(diǎn)個(gè)數(shù)10,必經(jīng)節(jié)點(diǎn)個(gè)數(shù)3，圖的邊數(shù)39，如圖3所示。

圖3 實(shí)驗(yàn)1實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)1的實(shí)驗(yàn)結(jié)果可以看出，IBA比Backtrack的效率要高一些，基于節(jié)點(diǎn)壓縮的NCA和CCA效果提高不明顯，這是因?yàn)閴嚎s節(jié)點(diǎn)的過(guò)程要耗費(fèi)一些時(shí)間，當(dāng)圖的復(fù)雜度較低時(shí)，效率提高就不太明顯了。

實(shí)驗(yàn)2總節(jié)點(diǎn)個(gè)數(shù)20,必經(jīng)節(jié)點(diǎn)個(gè)數(shù)5，圖的邊數(shù)55，如圖4所示。

圖4 實(shí)驗(yàn)2實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)2的實(shí)驗(yàn)結(jié)果可以看出，IBA、NCA、CCA相比Backtrack效果有明顯提高，CCA效果則更加明顯；IBA和NCA效果相似，這是因?yàn)閳D中較偏僻的節(jié)點(diǎn)較少。

實(shí)驗(yàn)3總節(jié)點(diǎn)個(gè)數(shù)30,必經(jīng)節(jié)點(diǎn)個(gè)數(shù)10，圖的邊數(shù)135，如圖5所示。

圖5 實(shí)驗(yàn)3實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)3的實(shí)驗(yàn)結(jié)果可以看出當(dāng)圖的復(fù)雜度逐漸提高時(shí)，CCA的優(yōu)越性更加明顯地體現(xiàn)出來(lái)了。

實(shí)驗(yàn)4總節(jié)點(diǎn)個(gè)數(shù)40,必經(jīng)節(jié)點(diǎn)個(gè)數(shù)10，圖的邊數(shù)229，如圖6所示。

圖6 實(shí)驗(yàn)4實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)4的結(jié)果表明，當(dāng)圖的復(fù)雜度達(dá)到更高時(shí)，Backtrack的實(shí)用性就不那么好了，而CCA的效率依然很好。

從實(shí)驗(yàn)結(jié)果可以看出，IBA無(wú)論在得到的結(jié)果路徑的權(quán)重還是搜索時(shí)間上，都比Backtrack要好；NCA比IBA有一定的進(jìn)步，但效果不明顯，主要原因是實(shí)驗(yàn)中所使用的圖中，存在偏僻節(jié)點(diǎn)的情況不多；而CCA在各個(gè)維度上相比前三種算法，都大大地提高了搜索結(jié)果的質(zhì)量和效率，可見(jiàn)CCA是一種很有效解決這一問(wèn)題的算法。

2) CCA和ICCA的比較

從前4個(gè)實(shí)驗(yàn)結(jié)果來(lái)看，Backtrack、IBA、NCA的效率隨著圖中節(jié)點(diǎn)個(gè)數(shù)的增加急劇降低。因此，繼續(xù)增加節(jié)點(diǎn)個(gè)數(shù)將變得沒(méi)有意義，接下來(lái)將只針對(duì)CCA和ICCA之間的比較。

實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)1-實(shí)驗(yàn)4的相同，也將逐漸增加總節(jié)點(diǎn)個(gè)數(shù)和圖中邊的條數(shù)，另外還會(huì)逐漸增加中間節(jié)點(diǎn)集合的大小，將從以下5個(gè)實(shí)驗(yàn)進(jìn)行比較。

實(shí)驗(yàn)5總節(jié)點(diǎn)個(gè)數(shù)60,必經(jīng)節(jié)點(diǎn)個(gè)數(shù)10，圖的邊數(shù)285，如圖7所示。

圖7 實(shí)驗(yàn)5的實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)6總節(jié)點(diǎn)個(gè)數(shù)100,必經(jīng)節(jié)點(diǎn)個(gè)數(shù)15，圖的邊數(shù)516，如圖8所示。

圖8 實(shí)驗(yàn)6的實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)7總節(jié)點(diǎn)個(gè)數(shù)200,必經(jīng)節(jié)點(diǎn)個(gè)數(shù)20，圖的邊數(shù)997，如圖9所示。

圖9 實(shí)驗(yàn)7的實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)8總節(jié)點(diǎn)個(gè)數(shù)400,必經(jīng)節(jié)點(diǎn)個(gè)數(shù)28，圖的邊數(shù)2 178，如圖10所示。

圖10 實(shí)驗(yàn)8的實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)9總節(jié)點(diǎn)個(gè)數(shù)600,必經(jīng)節(jié)點(diǎn)個(gè)數(shù)50，圖的邊數(shù)3 418，如圖11所示。

圖11 實(shí)驗(yàn)9的實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)結(jié)果可以看出，ICCA相比CCA，其最終解都要好一些，因此，3.3節(jié)中的改進(jìn)策略是行之有效的。

5 結(jié) 語(yǔ)

無(wú)論是“郵遞員問(wèn)題”、“旅行家問(wèn)題”、公交車(chē)專(zhuān)線設(shè)計(jì)以及網(wǎng)絡(luò)選路問(wèn)題，還是其他生活中類(lèi)似問(wèn)題，都可以抽象為本文研究的尋徑問(wèn)題。本文提出的IBA和NCA適用于規(guī)模中等的問(wèn)題。如果圖中有很多相對(duì)偏僻的節(jié)點(diǎn)，則建議使用NCA；CCA和ICCA這兩種算法適用于規(guī)模較大的問(wèn)題，算法實(shí)現(xiàn)難度較大，如果問(wèn)題可以通過(guò)調(diào)整字節(jié)點(diǎn)的排序規(guī)則來(lái)提高搜索效率，則使用ICCA。

由于當(dāng)問(wèn)題規(guī)模變得更加龐大時(shí)，CCA和ICCA在給定的時(shí)間內(nèi)也無(wú)法將整個(gè)解空間搜索完全，得不到最優(yōu)解。接下來(lái)將會(huì)把壓縮思想融入到遺傳算法、蟻群算法等啟發(fā)式算法中，以期獲得更高效的搜索算法，從而解決更大規(guī)模的尋徑問(wèn)題。

[1] 章登義,吳文李,歐陽(yáng)黜霏.RDF圖的Top-k最短路徑查詢(xún)[J].電子學(xué)報(bào),2015,43(8):1531-1537.

[2] 王峰,曼媛,段俊潔.一種改進(jìn)的求解前N條最短路徑問(wèn)題的多重標(biāo)號(hào)算法[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(7):1482-1487.

[3] 馮琳耀,袁林旺,羅文,等.節(jié)點(diǎn)約束型最短路徑的幾何代數(shù)算法[J].電子學(xué)報(bào),2014,42(5):846-851.

[4] 戚遠(yuǎn)航,蔡延光,蔡顥,等.旅行商問(wèn)題的混沌混合離散蝙蝠算法[J].電子學(xué)報(bào),2016,44(10):2543-2547.

[5] 王勇臻,陳燕,張金松.求解TSP的學(xué)習(xí)記憶果蠅算法[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(12):2722-2726.

[6] 吳新杰,王靜文,黃國(guó)興,等.一種求解旅行商問(wèn)題的改進(jìn)蛙跳算法[J].小型微型計(jì)算機(jī)系統(tǒng),2015,36(5):1078-1081.

[7] 劉大偉,呂元娜,余智華.一種改進(jìn)的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)算法[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(5):1071-1074.

[8] 安瑩,黃家瑋,羅熹,等.延遲容忍網(wǎng)絡(luò)中一種基于節(jié)點(diǎn)介數(shù)的擁塞感知路由算法[J].小型微型計(jì)算機(jī)系統(tǒng),2014,35(9):2062-2067.

[9] 李曉華,王士猛,楊曉春,等.基于Grid網(wǎng)格劃分的改進(jìn)路網(wǎng)最短路徑查詢(xún)[J].小型微型計(jì)算機(jī)系統(tǒng),2014,35(9):1937-1942.

SEARCHPATHOPTIMIZATIONALGORITHMBASEDONNODECOMPRESSION

Liao Zhifang Chen Liangming Peng Zhiwen Li Yanbing

(SchoolofSoftware,CentralSouthUniversity,Changsha410075,Hunan,China)

The shortest path problem is a classic problem，while the current study is mostly for a given starting point and end point, choose the shortest path from the starting point to the end, and has achieved a lot of results. For the limit time of the research achievements of the shortest path problem is relatively less, this kind of problem is ubiquitous in real life. In this paper, we propose several optimization algorithms for time-dependent optimization of this problem, from the improvement of backtracking method to the method of different node compression, an improved backtracking method and three algorithms based on node compression are proposed. Implemented in a limited amount of time, starting from the starting point after a given node set to reach the destination path selection, and according to different complexity of network diagram, can choose the appropriate algorithm to deal with, which can effectively solve the problem.

Shortest path Time constrained Node compression Search path

2017-02-12。國(guó)家自然科學(xué)基金青年項(xiàng)目(61301136)。廖志芳，副教授，主研領(lǐng)域：數(shù)據(jù)挖掘，推薦系統(tǒng)。陳亮名，碩士。彭志文，碩士。李嚴(yán)冰，碩士。

TP393

A

10.3969/j.issn.1000-386x.2017.11.045