李忠飛,楊雅君,王 鑫

1(天津大學(xué) 智能與計(jì)算學(xué)部,天津 300354)

2(數(shù)字出版技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京 100871)

3(天津市認(rèn)知計(jì)算與應(yīng)用重點(diǎn)實(shí)驗(yàn)室,天津 300354)

近年來(lái),隨著信息技術(shù)和互聯(lián)網(wǎng)的飛速發(fā)展,圖數(shù)據(jù)作為一種重要的數(shù)據(jù)模型變得愈加重要.在很多領(lǐng)域,圖數(shù)據(jù)刻畫了不同實(shí)體之間的相互關(guān)系,例如社交網(wǎng)絡(luò)[1,2]、道路交通網(wǎng)[3]、生物信息網(wǎng)[4]、計(jì)算機(jī)網(wǎng)絡(luò)[5]和Web 網(wǎng)絡(luò)[6]等.

其中,最短路徑查詢是圖數(shù)據(jù)管理中的一類非常重要的研究問(wèn)題.在社交網(wǎng)絡(luò)中,每個(gè)人都構(gòu)成了圖中的一個(gè)頂點(diǎn),人與人之間的聯(lián)系則形成了邊.社交網(wǎng)絡(luò)中的最短路徑是網(wǎng)絡(luò)頂點(diǎn)影響力評(píng)判的重要因素,小世界網(wǎng)絡(luò)中,直徑的計(jì)算一般也是通過(guò)計(jì)算最長(zhǎng)最短路徑得到的[7];在Web網(wǎng)絡(luò)中,數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)每個(gè)路由器使用路由協(xié)議和鏈路狀態(tài)信息來(lái)識(shí)別從自己到其他路由器的最短路徑,網(wǎng)絡(luò)拓?fù)渫ǔｋS時(shí)間而變化,因此,一個(gè)高效的最短路徑算法在路由計(jì)算中顯得尤為重要[8];在道路交通網(wǎng)中,經(jīng)常需要計(jì)算兩個(gè)地點(diǎn)之間的最短路徑,有時(shí)因?yàn)橐恍┨厥獾男枨筮€要計(jì)算最小的前k條最短路徑[9-11].

在實(shí)際應(yīng)用中,用戶往往需要查詢帶有約束條件的最短路徑.例如,某游客去一座城市旅行,他計(jì)劃首先前往某餐館就餐,然后分別參觀景點(diǎn)A～景點(diǎn)C,最后返回酒店.特別地,該游客計(jì)劃在參觀景點(diǎn)B之前先參觀景點(diǎn)A.因此,如何設(shè)計(jì)一條滿足用戶約束且代價(jià)最小的觀光路徑成為一個(gè)重要的問(wèn)題.在該例中,道路交通網(wǎng)被建模為一張圖G(V,E),則上述問(wèn)題可形式化描述為:給定起點(diǎn)vs和終點(diǎn)ve,尋找一條從vs到ve的最短路徑,使得此路徑經(jīng)過(guò)用戶指定點(diǎn)集Vs?V中的所有點(diǎn),且某些點(diǎn)的訪問(wèn)要滿足一定的先后順序.在本文中,該問(wèn)題被稱為基于規(guī)則的最短路徑查詢問(wèn)題.

目前,存在少量工作研究了最優(yōu)路徑查詢問(wèn)題optimal route queries(ORQ).ORQ將圖G中全部頂點(diǎn)劃分為多個(gè)不同的類別,用戶查詢時(shí),給出起點(diǎn)vs和一個(gè)訪問(wèn)順序圖GQ.這里,GQ是一個(gè)有向無(wú)環(huán)圖,GQ中的每個(gè)點(diǎn)都對(duì)應(yīng)于G中的一個(gè)類別信息,GQ中每條有向邊(c,c′)表示G中類別c優(yōu)先于類別c′訪問(wèn).查詢結(jié)果是一條以vs為起點(diǎn)且滿足GQ的最優(yōu)路徑.例如,某游客計(jì)劃去餐館、酒吧和電影院,每個(gè)類別都有多個(gè)具體的地點(diǎn)可供選擇,而且游客希望在去酒吧之前要先去餐館吃飯,因此,他需要制定一條路線使得在滿足約束條件的前提下路線的總距離最短.目前,解決ORQ問(wèn)題的精確算法的基本思想是:首先計(jì)算GQ中所有類別的全排列(每個(gè)類別在排列中的順序代表此類的訪問(wèn)順序),并刪除訪問(wèn)順序不滿足約束條件的排列;然后對(duì)于每一個(gè)排列,依次從排列的每個(gè)類中選擇一個(gè)點(diǎn)構(gòu)成一條路徑;最終枚舉出滿足約束條件的所有路徑,并返回具有最短距離的路徑.然而這些方法在面對(duì)基于規(guī)則的最短路徑問(wèn)題時(shí),主要存在以下兩個(gè)缺點(diǎn):(1) 針對(duì)基于規(guī)則的路徑查詢問(wèn)題,對(duì)圖G進(jìn)行劃分所得的每個(gè)類僅包含一個(gè)頂點(diǎn),即任意兩點(diǎn)對(duì)應(yīng)的類都不相同,已有的算法求解此類問(wèn)題相當(dāng)于枚舉出所有滿足約束條件的排列,然而大部分排列對(duì)于求解最短路徑來(lái)說(shuō)是冗余的;(2) 目前已有的解決ORQ問(wèn)題的算法面向的是空間數(shù)據(jù)庫(kù),這些算法均通過(guò)計(jì)算兩點(diǎn)之間的歐氏距離加速查詢,然而本文所解決的問(wèn)題是基于普通的圖模型,兩點(diǎn)間的最短距離即為最短路徑的長(zhǎng)度,而存儲(chǔ)全部頂點(diǎn)對(duì)之間的最短距離空間開銷過(guò)高.因此,本文設(shè)計(jì)了一種前向擴(kuò)展算法來(lái)快速求解基于規(guī)則的最短路徑問(wèn)題,其主要思想是,盡可能早地過(guò)濾掉不能構(gòu)成最短路徑的子路徑.真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明了本文提出的算法的效率遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)ORQ算法.

本文的主要貢獻(xiàn)如下:

(1) 提出了廣義規(guī)則樹的概念,設(shè)計(jì)了生成廣義規(guī)則樹的算法,并利用廣義規(guī)則樹來(lái)判斷算法是否找到一條基于規(guī)則的最短路徑;

(2) 設(shè)計(jì)了基于最優(yōu)子路徑的前向擴(kuò)展算法,該算法可以快速求解基于規(guī)則的最短路徑問(wèn)題,并設(shè)計(jì)了前向擴(kuò)展算法的改進(jìn)算法——基于最短優(yōu)先策略的前向擴(kuò)展算法;

(3) 在真實(shí)的數(shù)據(jù)集上設(shè)計(jì)了大量的實(shí)驗(yàn),并與已有的性能最好的算法比較,實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的有效性.

本文第1節(jié)給出基于規(guī)則的最短路徑查詢問(wèn)題的形式化定義,并證明此類問(wèn)題是NP-hard問(wèn)題.第2節(jié)介紹廣義規(guī)則樹的概念,并設(shè)計(jì)生成廣義規(guī)則樹的算法.第 3節(jié)介紹一種圖數(shù)據(jù)的預(yù)處理技術(shù),可以用來(lái)快速求解兩點(diǎn)之間的最短路徑.第 4節(jié)和第 5節(jié)分別介紹前向擴(kuò)展算法以及基于最短優(yōu)先策略的前向擴(kuò)展算法,并分別對(duì)它們的算法復(fù)雜度進(jìn)行分析.第6節(jié)在真實(shí)的數(shù)據(jù)集上驗(yàn)證本文算法的高效性.第7節(jié)介紹相關(guān)工作.最后一節(jié)對(duì)全文進(jìn)行總結(jié).

1 問(wèn)題定義

有向加權(quán)圖可以表示為G(V,E,w)(簡(jiǎn)稱G),V表示圖G中全部頂點(diǎn)的集合,E表示全部邊的集合.任意一條有向邊e∈E可以表示為e=(vi,vj),其中,vi,vj∈V,e稱為vi的出邊或者vj的入邊,vj(vi)被稱為vi(vj)的出邊(入邊)鄰居.w是一個(gè)權(quán)重函數(shù),并且對(duì)圖G中的每條邊都賦予一個(gè)非負(fù)的權(quán)重,本文使用wi,j來(lái)表示有向邊(vi,vj)∈E的權(quán)重,即wi,j=w(vi,vj).圖G中的路徑p是一個(gè)頂點(diǎn)序列,即p=(v1,v2,…vk),其中,(vi,vi+1)(1≤i≤k-1)是圖G中的一條有向邊,路徑p的權(quán)重用w(p)表示,表示p中全部有向邊的權(quán)重之和,即.路徑p是一條簡(jiǎn)單路徑當(dāng)且僅當(dāng)p中沒(méi)有重復(fù)的頂點(diǎn).對(duì)于無(wú)向圖,一條無(wú)向邊(vi,vj)等價(jià)于兩條有向邊(vi,vj)和(vj,vi),因此,本文提出的方法也可應(yīng)用到無(wú)向圖上的同類問(wèn)題.

本文主要研究基于規(guī)則的最短路徑查詢問(wèn)題,首先介紹什么是路徑查詢規(guī)則,然后給出基于規(guī)則的路徑定義.本文中,路徑規(guī)則用R表示,被定義為二元組R=(I,R),包含兩個(gè)元素.

(i)I是V的一個(gè)頂點(diǎn)子集,即I?V;

(ii)R是一組偏序關(guān)系〈vi,vj〉的集合,其中,vi,vj∈I.〈vi,vj〉表示vi?vj.

需要注意的是:偏序關(guān)系集R中不存在環(huán),即R中不存在一個(gè)偏序關(guān)系子集{〈v1,v2〉,…,〈vk-1,vk〉,〈vk,v1〉},其中,頂點(diǎn)v1,v2,…,vk∈I.下面給出基于規(guī)則的路徑定義.

定義1.1(基于規(guī)則的路徑).給定圖G(V,E,w),起點(diǎn)為vs,終點(diǎn)為ve,規(guī)則R=(I,R),如果路徑p滿足以下兩個(gè)條件,則被稱為由vs到ve的基于規(guī)則R的路徑.

(1) 對(duì)每一個(gè)頂點(diǎn)vi∈I,都有vi∈p;

(2) 對(duì)每一個(gè)偏序關(guān)系〈vi,vj〉∈R(或者vi?vj),路徑p中都存在一個(gè)從vi到vj的子路徑vi?vj.

在定義1.1中,條件(1)是指:若路徑p基于規(guī)則R=(I,R),則p需要包含I中的所有點(diǎn);條件(2)是指:對(duì)R中的任意偏序關(guān)系vi?vj,在路徑p中都存在一條從頂點(diǎn)vi到頂點(diǎn)vj的子路徑.

給定圖G中的兩個(gè)頂點(diǎn)vs,ve以及規(guī)則R,從vs到ve的基于規(guī)則R的最短路徑表示為,是指從vs到ve的基于規(guī)則R的所有路徑中權(quán)重w(p)最小的路徑.表1列出了本文常用的符號(hào).

Table 1 List of notations表1 符號(hào)列表

例 1.1:給定有向圖G(V,E,w),如圖1(a)所示,已知規(guī)則R=(I,R),I={v2,v4,v5,v6},R={v2?v4,v2?v5},其中,起點(diǎn)為v1,終點(diǎn)為v3,可得此圖基于規(guī)則R的最短路徑為,如圖1(b)中的虛線箭頭所示.

Fig.1 Rule-based shortest path圖1 基于規(guī)則的最短路徑

定理1.1.基于規(guī)則的最短路徑查詢問(wèn)題是一個(gè)NP-hard問(wèn)題.

證明:本文通過(guò)將其歸約到哈密爾頓路問(wèn)題(NPC問(wèn)題)證明.給定一個(gè)有向圖G,令vs和ve分別表示起點(diǎn)和終點(diǎn).G中每條邊的權(quán)重都設(shè)為1,規(guī)則R=(I,R)被設(shè)置為I=V-{vs,ve},R=?.顯然,圖G中存在一條從vs到ve的哈密爾頓路當(dāng)且僅當(dāng)從vs到ve的基于規(guī)則R的最短路徑的長(zhǎng)度為|V|-1(|V|表示V中頂點(diǎn)的個(gè)數(shù)),而且對(duì)于一條給定的路徑,不能在多項(xiàng)式時(shí)間驗(yàn)證它是否是基于規(guī)則的最短路徑,因此,基于規(guī)則的最短路徑問(wèn)題是一個(gè)NP-hard問(wèn)題.證畢. □

2 廣義規(guī)則樹

若p為一條基于規(guī)則R的路徑,由第1節(jié)可知:在規(guī)則R中,偏序關(guān)系集R中的偏序關(guān)系vi?vj(vi,vj∈I)表示在路徑p中存在一條從vi到vj的子路徑.顯然,對(duì)I中的任意一點(diǎn)vi,p中存在一條從起點(diǎn)vs到vi的子路徑,也存在一條vi到終點(diǎn)ve子路徑.由于vs和ve分別為p的起點(diǎn)和終點(diǎn),因此集合IR=I∪{vs,ve}中的任意點(diǎn)都在基于規(guī)則R的路徑p中,稱集合IR為規(guī)則點(diǎn)集,IR中的點(diǎn)稱為規(guī)則點(diǎn).本節(jié)提出了廣義規(guī)則樹的概念,廣義規(guī)則樹并非真正的樹,其將規(guī)則點(diǎn)集IR中的全部頂點(diǎn)組織成類似樹的結(jié)構(gòu),并通過(guò)樹中的祖先后代關(guān)系來(lái)表示兩個(gè)規(guī)則點(diǎn)之間的偏序關(guān)系,即:若vi?vj,則在廣義規(guī)則樹中,結(jié)點(diǎn)vi是結(jié)點(diǎn)vj的祖先結(jié)點(diǎn).與普通樹區(qū)別在于,廣義規(guī)則樹中的結(jié)點(diǎn)可能具有多個(gè)父親結(jié)點(diǎn).利用廣義規(guī)則樹,本文提出的算法可以高效判斷搜索到的路徑p是否是一條滿足規(guī)則的路徑.下面首先給出廣義規(guī)則樹的定義,然后給出廣義規(guī)則樹的生成算法.

定義2.1(廣義規(guī)則樹).滿足規(guī)則R的廣義規(guī)則樹是一棵由規(guī)則點(diǎn)集IR中全部頂點(diǎn)構(gòu)成的廣義樹,記為TR,其滿足以下兩個(gè)條件.

(1) 起點(diǎn)vs為根結(jié)點(diǎn)、終點(diǎn)ve為唯一葉結(jié)點(diǎn);

(2) 對(duì)TR中除根結(jié)點(diǎn)和葉結(jié)點(diǎn)外的任意兩個(gè)結(jié)點(diǎn)vi,vj,若vi是vj的一個(gè)父親結(jié)點(diǎn),當(dāng)且僅當(dāng)vi?vj;且不存在另外一個(gè)頂點(diǎn)vk∈I,使得vi?vk和vk?vj同時(shí)成立.

廣義規(guī)則樹滿足以下兩個(gè)性質(zhì).

性質(zhì)2.1.給定起點(diǎn)vs、終點(diǎn)ve和規(guī)則R,廣義規(guī)則樹TR存在且唯一.

證明:當(dāng)給定起點(diǎn)vs和終點(diǎn)ve,TR的根和唯一葉結(jié)點(diǎn)即已確定.給定規(guī)則R,TR中結(jié)點(diǎn)的父親-孩子關(guān)系也已確定,故TR存在且唯一.證畢. □

性質(zhì)2.2.R中蘊(yùn)含的任意一個(gè)偏序關(guān)系都對(duì)應(yīng)廣義規(guī)則樹中的一對(duì)祖先后代結(jié)點(diǎn).證明:若R中蘊(yùn)含vi?vj,由廣義規(guī)則樹定義中的條件(2)可知:在TR中,vi是vj的祖先結(jié)點(diǎn).證畢. □顯然,在廣義規(guī)則樹中,起點(diǎn)是所有其他點(diǎn)的祖先結(jié)點(diǎn),終點(diǎn)是所有其他點(diǎn)的后代結(jié)點(diǎn).規(guī)則點(diǎn)vi∈IR的全部父結(jié)點(diǎn)集合表示為,子結(jié)點(diǎn)集合表示為,祖先結(jié)點(diǎn)集合表示為,后代結(jié)點(diǎn)集合表示為.例 2.1給出了廣義規(guī)則樹的示例.

例 2.1:給定有向

圖G,如圖1(a)所示,其中,起點(diǎn)為v1,終點(diǎn)為v3,規(guī)則R=(I,R),I={v2,v4,v5,v6},若R=?,則基于規(guī)則R的廣義規(guī)則樹如圖2(a)所示;若R={v2?v4,v2?v5},此基于規(guī)則R的廣義規(guī)則樹如圖2(b)所示.

Fig.2 Generalized rule tree圖2 廣義規(guī)則樹

下文中,規(guī)則點(diǎn)vi∈IR的父結(jié)點(diǎn)、子結(jié)點(diǎn)、祖先結(jié)點(diǎn)和后代結(jié)點(diǎn)均指廣義規(guī)則樹中對(duì)應(yīng)樹結(jié)點(diǎn)vi的父結(jié)點(diǎn)、子結(jié)點(diǎn)、祖先結(jié)點(diǎn)和后代結(jié)點(diǎn).例如在圖2(b)中,規(guī)則點(diǎn)v2的父結(jié)點(diǎn)集合、子結(jié)點(diǎn)集合、祖先結(jié)點(diǎn)集合、后代結(jié)點(diǎn)集合.

算法1展示了構(gòu)造廣義規(guī)則樹的偽代碼.初始階段,算法將所有的規(guī)則點(diǎn)初始化一棵廣義樹(第1行),廣義樹的根設(shè)為起點(diǎn)vs,唯一葉結(jié)點(diǎn)設(shè)為終點(diǎn)ve,I中的所有頂點(diǎn)都互為兄弟結(jié)點(diǎn),且它們的父結(jié)點(diǎn)和祖先結(jié)點(diǎn)都設(shè)為vs,子結(jié)點(diǎn)和后代結(jié)點(diǎn)都設(shè)為ve,因此,vs的子結(jié)點(diǎn)集合和ve的父結(jié)點(diǎn)集合均為I.算法1的主要思想是:依次處理R中的每一對(duì)偏序關(guān)系,并逐步構(gòu)造廣義規(guī)則樹.在每次迭代中,對(duì)每個(gè)〈vi,vj〉∈R,算法判斷在TR中vi是否是vj的祖先:若是,則忽略〈vi,vj〉并跳出本輪迭代(第 3行～第 3行);否則,根據(jù)〈vi,vj〉更新廣義規(guī)則樹TR.更新過(guò)程如下.

· 首先,對(duì)TR中vi的每個(gè)子結(jié)點(diǎn),若vk是vj的后代結(jié)點(diǎn),則將vk從中刪除(第6行～第10行);對(duì)TR中vj的每個(gè)父結(jié)點(diǎn),若vk是vi的祖先結(jié)點(diǎn),則將vk從中刪除(第11行～第15行);

· 然后,將vi加入vj的父結(jié)點(diǎn)集合,將vj加入vi的子結(jié)點(diǎn)集合(第16行);

· 最后,對(duì)vj的每個(gè)祖先結(jié)點(diǎn)vk,將vk的后代結(jié)點(diǎn)集合更新為(第 17行～第 19行);對(duì)vi的每個(gè)祖先結(jié)點(diǎn)vk,將vk的祖先結(jié)點(diǎn)集合更新為(第 20行～第22行).當(dāng)R中的全部偏序關(guān)系處理完畢,算法結(jié)束并返回TR.

算法1.GeneralizedRuleTree(G,vs,ve,R).

輸入:圖G,起點(diǎn)vs,終點(diǎn)ve,規(guī)則R=(I,R);

輸出:廣義規(guī)則樹TR.

例2.2:接例1.1,利用算法1構(gòu)造其對(duì)應(yīng)的廣義規(guī)則樹.首先,初始化廣義規(guī)則樹,結(jié)果如圖3(a)所示;當(dāng)偏序關(guān)系v2?v4插入到廣義樹中后,結(jié)點(diǎn)v2的子結(jié)點(diǎn)集合修改為{v4},結(jié)點(diǎn)v4的父結(jié)點(diǎn)集合修改為{v2},結(jié)點(diǎn)v1的子結(jié)點(diǎn)集合修改為{v2,v5,v6},結(jié)點(diǎn)v3的父結(jié)點(diǎn)集合修改為{v4,v5,v6},結(jié)果如圖3(b)所示;當(dāng)偏序關(guān)系v2?v5插入到廣義樹中后,結(jié)點(diǎn)v2的子結(jié)點(diǎn)集合修改為{v4,v5},結(jié)點(diǎn)v5的父結(jié)點(diǎn)集合修改為{v2},結(jié)點(diǎn)v1的子結(jié)點(diǎn)集合修改為{v2,v6},結(jié)果如圖3(c)所示.

Fig.3 Construction of generalized rule tree圖3 廣義規(guī)則樹的構(gòu)造過(guò)程

廣義規(guī)則樹TR中,結(jié)點(diǎn)vi被某路徑p合法訪問(wèn)是指:若vi為根結(jié)點(diǎn),則p包含vi;否則,p包含vi且vi在TR中的所有父結(jié)點(diǎn)都已被p中從起點(diǎn)vs到vi的子路徑合法訪問(wèn).定理2.1給出了路徑p是否滿足規(guī)則R的判斷條件.

定理2.1.路徑p為一條從起點(diǎn)vs到終點(diǎn)ve的路徑,若終點(diǎn)ve被路徑p合法訪問(wèn),則路徑p為一條基于規(guī)則R的路徑.

證明:由規(guī)則點(diǎn)被路徑合法訪問(wèn)的定義可知,集合I中的點(diǎn)都在路徑p中.下面證明偏序關(guān)系集R中的所有偏序關(guān)系均已滿足.假設(shè)存在一個(gè)偏序關(guān)系〈vi,vj〉∈R,使得p不滿足此偏序關(guān)系,即p中不存在一條從vi到vj的子路徑,因此,規(guī)則點(diǎn)vj沒(méi)有被合法訪問(wèn)且vj的所有子結(jié)點(diǎn)也沒(méi)有被合法訪問(wèn).由于終點(diǎn)ve是所有規(guī)則點(diǎn)的后代結(jié)點(diǎn),可得終點(diǎn)ve沒(méi)有被路徑p合法訪問(wèn).這與已知條件矛盾.因此,所有的偏序關(guān)系均已滿足.綜上可得,路徑p為一條基于規(guī)則R的路徑.證畢. □

由定理2.1可知:可以依據(jù)一個(gè)查詢的終點(diǎn)是否被一條路徑合法訪問(wèn),來(lái)判斷此路徑是否為基于規(guī)則的路徑.在下文介紹的前向擴(kuò)展算法中,本文依據(jù)定理2.1來(lái)判斷是否已找到一條基于規(guī)則的路徑.

3 分層收縮技術(shù)

分層收縮(contraction hierarchies,簡(jiǎn)稱 CH)[12]是一種簡(jiǎn)單有效的圖數(shù)據(jù)預(yù)處理技術(shù),它可以提高最短路徑的查詢效率.CH本質(zhì)上是預(yù)先存儲(chǔ)一些最短路徑信息,從而實(shí)現(xiàn)加速最短路徑查找的目的.本文采用CH技術(shù)進(jìn)行預(yù)處理,以使算法能更高效地計(jì)算兩點(diǎn)之間的最短路徑.給定圖G(V,E,w),CH首先給V中所有頂點(diǎn)分配一個(gè)序號(hào),任意兩個(gè)頂點(diǎn)的序號(hào)都不相同;然后依據(jù)序號(hào)的大小,按照從小到大的順序?qū)c(diǎn)進(jìn)行收縮.頂點(diǎn)vi被收縮是指:把vi以及與vi相連的邊從G中刪除,并且添加一些新的邊到G中.具體地,對(duì)每一對(duì)vi的入邊(vj,vi)和出邊(vi,vk),如果路徑(vj,vi,vk)是連接vj和vk的唯一的最短路徑,則往G中添加邊(vj,vk),并且將邊(vj,vk)的權(quán)重設(shè)為(vj,vi)和(vi,vk)的權(quán)重之和.所有頂點(diǎn)收縮完成之后,CH將原圖G分為兩個(gè)新圖,分別為前向圖Gu和后向圖Gd;然后,CH利用Gu和Gd計(jì)算最短路徑.CH技術(shù)的具體細(xì)節(jié)見文獻(xiàn)[12].

4 FE算法

本節(jié)提出前向擴(kuò)展算法(forward expanding,簡(jiǎn)稱 FE)來(lái)求解基于規(guī)則R的最短路徑.接下來(lái),首先介紹最優(yōu)子排列,然后詳細(xì)介紹FE算法,最后分析了算法的時(shí)間和空間復(fù)雜度.

4.1 最優(yōu)子排列

給定有向圖G(V,E,w)、規(guī)則R=(I,R)以及起點(diǎn)vs和終點(diǎn)ve,可得規(guī)則點(diǎn)集IR,令r表示IR中點(diǎn)的個(gè)數(shù),即r=|IR|.IR的一個(gè)排列π是一個(gè)點(diǎn)序列v1v2…vr,對(duì)任意點(diǎn)vi(1≤i≤r)都有vi∈IR,且排列π中不包含重復(fù)的點(diǎn).顯然,一個(gè)規(guī)則點(diǎn)集IR總共有r!個(gè)排列.對(duì)于一個(gè)排列π,本文用規(guī)則點(diǎn)在π中的次序來(lái)表示此規(guī)則點(diǎn)在路徑p中的合法訪問(wèn)順序,即:若vi∈IR在π中處于第i個(gè)位置,則在p中,vi是第i個(gè)被合法訪問(wèn)的.給定排列π=v1v2…vr,如果路徑p滿足下面3個(gè)條件,稱p為一條對(duì)應(yīng)于π的路徑,記為p|π.

(1) 對(duì)π中任意點(diǎn)vi,p中都包含點(diǎn)vi;

(2) 若π中點(diǎn)vi的位置在vj之前,則p中包含一條從vi到vj的子路徑;

(3) 路徑p的起點(diǎn)和終點(diǎn)分別為v1和vr.

給定路徑p|π,它可以被π中的所有點(diǎn)劃分為r-1條子路徑.每條子路徑都被稱為p|π的一個(gè)路徑片段.本文使用Sp|π來(lái)表示p|π的所有路徑片段.

定義4.1(基于規(guī)則的排列).給定圖G(V,E,w),起點(diǎn)為vs,終點(diǎn)為ve,規(guī)則R=(I,R),π是規(guī)則點(diǎn)集IR的一個(gè)排列.已知條件:(1)π起始位置和末尾位置的頂點(diǎn)分別為vs和ve;(2) 對(duì)每一個(gè)偏序關(guān)系〈vi,vj〉∈R(或者vi?vj),π中vi的位置都在vj之前.若排列π滿足上述兩個(gè)條件,則稱π為從vs到ve的基于規(guī)則R的排列.所有基于規(guī)則R的排列構(gòu)成的集合記為,即,中所有排列都以vs為起始位置頂點(diǎn)、ve為末尾位置頂點(diǎn)且滿足規(guī)則R.

由定義4.1可知:若π為一個(gè)基于規(guī)則R的排列,則p|π為一個(gè)基于規(guī)則R的路徑.如果路徑p是對(duì)應(yīng)于排列π的路徑,且p中的所有路徑片段均為最短路徑,本文稱p為對(duì)應(yīng)于排列π的最短路徑,記為p*|π.由此可以得到下面的定理:

定理4.1.給定圖G(V,E,w),起點(diǎn)為vs,終點(diǎn)為ve,規(guī)則R=(I,R),若p*是IR的所有基于規(guī)則的排列所對(duì)應(yīng)的p*|π中權(quán)重最小的一條路徑,則p*即為基于規(guī)則R的最短路徑.

證明:給定IR的一個(gè)基于規(guī)則R的排列π,因?yàn)閜*|π中的所有路徑片段都是最短路徑,因此p*|π的權(quán)重不大于π所對(duì)應(yīng)的每一條路徑p|π的權(quán)重;又因?yàn)閜*是所有基于規(guī)則的排列所對(duì)應(yīng)的p*|π中權(quán)重最小的一條路徑,而且所有的p*|π都是基于規(guī)則R的路徑,因此,p*為基于規(guī)則R的最短路徑.證畢. □

由定理4.1可知:對(duì)于一個(gè)基于規(guī)則的排列π,只有當(dāng)π所對(duì)應(yīng)的路徑p|π中的所有路徑片段都為最短路徑時(shí),即p|π為p*|π,此路徑才有可能成為基于規(guī)則的最短路徑.因此,本文后續(xù)部分所提到的任意排列π所對(duì)應(yīng)的路徑都特指p*|π,即所有的路徑片段都為最短路徑.

對(duì)于點(diǎn)集Vs?V,可以逐步擴(kuò)展點(diǎn)序列的長(zhǎng)度來(lái)得到Vs的排列,其中,點(diǎn)序列中的每個(gè)點(diǎn)都屬于Vs,且點(diǎn)序列中不包含重復(fù)的頂點(diǎn).如果點(diǎn)序列中包含l個(gè)頂點(diǎn),本文稱此點(diǎn)序列為Vs的l-子排列(特別地,本文規(guī)定:規(guī)則點(diǎn)集IR的所有子排列均以起點(diǎn)vs作為起始位置的頂點(diǎn)),記為πl(wèi),其中,1≤l≤r(r=|Vs|).包含πl(wèi)中l(wèi)個(gè)頂點(diǎn)的點(diǎn)集合稱為子排列πl(wèi)對(duì)應(yīng)的點(diǎn)集,記為Vπl(wèi).給定一個(gè)排列π,π⊕v表示π擴(kuò)展一個(gè)頂點(diǎn)后形成的新排列,這稱為排列的擴(kuò)展操作,其中,⊕是一個(gè)連接符,即,把點(diǎn)v添加到π的末尾.若πl(wèi)1和πl(wèi)2分別為Vs的l1-子排列和l2-子排列,已知條件:(1)l1≤l2;(2)πl(wèi)2經(jīng)由πl(wèi)1擴(kuò)展 0個(gè)或多個(gè)頂點(diǎn)得到.如果πl(wèi)1和πl(wèi)2滿足條件(1)和條件(2),則稱πl(wèi)1為πl(wèi)2的前綴.例如,v1v2是v1v2v3v4的前綴.下面本文給出子排列滿足的規(guī)則的定義.

定義4.2(子排列滿足的規(guī)則R′=(I′,R′)).給定圖G(V,E,w),起點(diǎn)為vs,終點(diǎn)為ve,規(guī)則R=(I,R),πl(wèi)為IR的l-子排列(1≤l≤|IR|)且πl(wèi)起始位置的頂點(diǎn)為vs.R′=(I′,R′),其中,I′?I,R′?R,已知條件:(1)πl(wèi)是I′的一個(gè)排列;(2) 對(duì)任意偏序關(guān)系〈vi,vj〉∈R′,都有vi,vj∈I′且πl(wèi)中vi的位置在vj之前;(3) 不存在偏序關(guān)系〈vi,vj〉∈R-R′,使得vi,vj∈I′.若規(guī)則R′滿足上述3個(gè)條件,則稱R′為子排列πl(wèi)滿足的規(guī)則.

利用定義4.2,可以很容易地給出最優(yōu)子排列定理.

定理4.2.給定圖G(V,E,w),起點(diǎn)為vs,終點(diǎn)為ve,規(guī)則R=(I,R),若IR的排列π對(duì)應(yīng)的路徑p|π為基于規(guī)則R的最短路徑,πl(wèi)為π的包含l(1≤l≤|IR|)個(gè)頂點(diǎn)的前綴,πl(wèi)滿足的規(guī)則為R′=(I′,R′),v*是πl(wèi)末尾位置的頂點(diǎn),對(duì)任意排列,都有,本文稱πl(wèi)為IR的一個(gè)最優(yōu)子排列.

給定有向圖G(V,E,w)如圖1(a)所示,已知規(guī)則,起點(diǎn)為v1,終點(diǎn)為v3,可得排列對(duì)應(yīng)的路徑為基于規(guī)則R的最短路徑,為π的包含4個(gè)頂點(diǎn)的前綴,v6是π4末尾位置的頂點(diǎn),π4滿足的規(guī)則為R′=(I′,R′),其中,,π4和π4′分別對(duì)應(yīng)的路徑為.顯然,

推論4.1.給定圖G(V,E,w),起點(diǎn)為vs,終點(diǎn)為ve,規(guī)則R=(I,R),已知IR的長(zhǎng)度為l(1≤l≤|IR|)的一個(gè)子排列πl(wèi),πl(wèi)起始位置的頂點(diǎn)為vs、末尾位置的頂點(diǎn)為v*,πl(wèi)滿足的規(guī)則為R′=(I′,R′),則擴(kuò)展操作得到的子排列集合中,存在一個(gè)子排列′,使得對(duì)任意的,都有,IR的排列π對(duì)應(yīng)的路徑p|π為基于規(guī)則R的最短路徑,若π的長(zhǎng)度為l的前綴屬于,將π的長(zhǎng)度為l的前綴替換為′得到新的排列π′,則w(p|π′)=w(p|π),本文稱πl(wèi)′為IR的一個(gè)最優(yōu)子排列.

4.2 前向擴(kuò)展算法

本節(jié)提出求解基于規(guī)則R的最短路徑的前向擴(kuò)展算法,算法的主要思想是:從規(guī)則點(diǎn)集IR的 1-子排列逐步進(jìn)行擴(kuò)展操作直至IR的r-子排列(r=|IR|),并利用最優(yōu)子排列對(duì)生成的子排列進(jìn)行過(guò)濾,最終返回IR的r-子排列對(duì)應(yīng)的路徑中權(quán)重最小的那條路徑.

前向擴(kuò)展算法的偽代碼見算法2.

算法2.FE(G,vs,ve,R).

輸入:圖G,起點(diǎn)vs,終點(diǎn)ve,規(guī)則R=(I,R);

給定圖G(V,E,w),起點(diǎn)為vs,終點(diǎn)為ve,規(guī)則R=(I,R),FE首先調(diào)用算法 1得到廣義規(guī)則樹TR(第 1行);然后,利用下文相關(guān)工作部分介紹的啟發(fā)式算法NN求解得到基于規(guī)則R的路徑pg,令θ等于pg的權(quán)重(第2行、第2行);第4行～第 24行,FE逐步擴(kuò)展規(guī)則點(diǎn)集IR的 1-子排列直至IR的r-子排列(r=|IR|).在構(gòu)建IR的 1-子排列時(shí),因?yàn)橹挥笑?=vs這一個(gè)1子排列滿足規(guī)則,因此,FE將R1初始化為{vs}(第4行、第5行);第6行～第24行,FE循環(huán)得到IR的2-子排列至r-子排列.下面將詳細(xì)介紹FE求解IR的l-子排列的過(guò)程,其中,2≤l≤r.

FE用Rl來(lái)存儲(chǔ)IR的l子排列所對(duì)應(yīng)的路徑:首先,將Rl初始化為空集(第7行);然后,FE對(duì)長(zhǎng)度為l-1的子排列進(jìn)行擴(kuò)展操作,并利用最優(yōu)子排列理論過(guò)濾不可能成為基于規(guī)則的最短路徑所對(duì)應(yīng)排列的前綴.依據(jù)子排列πl(wèi)-1對(duì)應(yīng)的點(diǎn)集Vπl(wèi)-1,FE將Rl-1劃分為不同的集合,即屬于同一集合里的路徑擁有相同的點(diǎn)集Vπl(wèi)-1,屬于不同集合的路徑擁有不同的點(diǎn)集Vπl(wèi)-1(第8行).接下來(lái),FE依次遍歷規(guī)則點(diǎn)集IR中除vs之外的其他所有點(diǎn)(第9行),并對(duì)每一個(gè)v∈IR-{vs}做如下操作:遍歷劃分Rl-1得到的每一個(gè)集合中的每一條路徑都與一個(gè)長(zhǎng)度為l-1的子排列所對(duì)應(yīng),對(duì)于Rl′-1中的每一條路徑p|πl(wèi)-1及相應(yīng)的πl(wèi)-1,如果πl(wèi)-1中不包含點(diǎn)v且v的所有父結(jié)點(diǎn)均已被p|πl(wèi)-1合法訪問(wèn),那么將v添加到πl(wèi)-1的末尾構(gòu)成長(zhǎng)度為l的子排列πl(wèi)并且生成相應(yīng)的路徑p|πl(wèi),若中的每一條路徑均已完成上述操作,則從新生成的路徑中選擇一條權(quán)重最小的路徑,記為即為一個(gè)最優(yōu)子排列,如果p*|πl(wèi)的權(quán)重不大于θ,則將p*|πl(wèi)添加到Rl中(第10行～第22行).

FE求得IR的r-子排列所對(duì)應(yīng)的路徑之后,由于IR的r子排列所對(duì)應(yīng)的路徑的最后一個(gè)頂點(diǎn)為終點(diǎn)ve,由定理2.1可知,IR的r子排列所對(duì)應(yīng)的路徑都為基于規(guī)則R的路徑,顯然,基于規(guī)則R的最短路徑即為IR的r子排列所對(duì)應(yīng)的路徑中權(quán)重最小的一條.第25行、第26行,FE首先遍歷Rr得到具有最小權(quán)重的路徑,然后返回此路徑作為基于規(guī)則R的最短路徑.

例4.1:接例 1.1,利用 FE算法求解基于規(guī)則R的最短路徑的過(guò)程見表2,其中,πl(wèi)表示一個(gè)子排列,|πl(wèi)|表示子排列中包含頂點(diǎn)的個(gè)數(shù),Vπl(wèi)表示πl(wèi)對(duì)應(yīng)的點(diǎn)集,v*表示πl(wèi)的最后一個(gè)頂點(diǎn),p|πl(wèi)表示πl(wèi)所對(duì)應(yīng)的路徑.用貪心算法求解得到基于規(guī)則R的路徑pg=(v1,v3,v2,v4,v5,v3,v2,v4,v6,v5,v3),θ=w(pg)=12.加刪除線的子排列表示被最優(yōu)子排列過(guò)濾掉的子排列,從表2的結(jié)果可得,最優(yōu)子排列可以減少算法在求解過(guò)程中生成的子排列個(gè)數(shù),從而降低算法的求解時(shí)間.FE算法最終得到的排列為π=v1v2v4v6v5v3,所對(duì)應(yīng)的路徑為p|π=(v1,v3,v2,v4,v6,v5,v3),w(p|π)=8,因此,p|π即為基于規(guī)則R的最短路徑.

Table 2 Solving process of FE algorithm表2 FE算法的求解過(guò)程

4.3 復(fù)雜度分析

4.3.1 時(shí)間復(fù)雜度.

FE的時(shí)間復(fù)雜度主要集中在計(jì)算IR的長(zhǎng)度為1至r(r=|IR|)的子排列上,對(duì)于長(zhǎng)度為l(1≤l≤r)的子排列,由最優(yōu)子排列可知,FE至多生成個(gè),其中,表示IR中頂點(diǎn)的組合數(shù).因此,FE至多生成個(gè)子排列.本文采用 CH技術(shù)求解兩點(diǎn)之間的最短路徑,它的時(shí)間復(fù)雜度為O(nlogn+m)(n=|V|,m=|E|),因此,FE的時(shí)間復(fù)雜度為O((nlogn+m)·(r·2r)).

4.3.2 空間復(fù)雜度.

FE需要利用長(zhǎng)度為l-1的子排列來(lái)求解長(zhǎng)度為l的子排列,因?yàn)镕E至多生成個(gè)長(zhǎng)度為l(2≤l≤r)的子排列,因此在求解長(zhǎng)度為l的子排列時(shí),內(nèi)存的總消耗為;一旦求得長(zhǎng)度為l的子排列之后,即可將存儲(chǔ)長(zhǎng)度為l-1的子排列的內(nèi)存釋放.因此,FE所消耗的內(nèi)存最大為,即,FE 的空間復(fù)雜度為O(n·r·2r).

5 FEBF算法

本節(jié)提出 FE算法的改進(jìn)算法——基于最短優(yōu)先策略的前向擴(kuò)展算法(forward expanding based on best-first searching,簡(jiǎn)稱 FEBF).接下來(lái),本文首先分析如何對(duì) FE算法進(jìn)行改進(jìn);然后給出基于最短優(yōu)先策略的前向擴(kuò)展算法,并對(duì)算法做出詳細(xì)的介紹;接著,對(duì)FEBF算法提出了幾個(gè)優(yōu)化技術(shù);最后,分析了FEBF算法的時(shí)間和空間復(fù)雜度.

5.1 基于最短優(yōu)先策略的前向擴(kuò)展算法

從第4.2節(jié)可知,FE算法依次擴(kuò)展規(guī)則點(diǎn)集IR的長(zhǎng)度為1至長(zhǎng)度為r(r=|IR|)的子排列,最后從長(zhǎng)度為r的子排列對(duì)應(yīng)的路徑中選擇權(quán)重最小的路徑作為問(wèn)題的解.在求解長(zhǎng)度為l的子排列時(shí),FE必須先求得長(zhǎng)度為l-1的所有子排列.事實(shí)上,某些長(zhǎng)度為l-1的子排列所對(duì)應(yīng)路徑的權(quán)重已大于基于規(guī)則R的最短路徑的權(quán)重,因此沒(méi)有必要對(duì)這部分子排列進(jìn)行擴(kuò)展操作.在例4.1中長(zhǎng)度為3的子排列v1v6v2對(duì)應(yīng)路徑為(v1,v3,v2,v4,v6,v5,v3,v2),其權(quán)重為9,而基于規(guī)則R的最短路徑權(quán)重為8,因此,沒(méi)有必要再對(duì)子排列v1v6v2進(jìn)行擴(kuò)展操作.基于此,本文提出基于最短優(yōu)先策略來(lái)逐步擴(kuò)展路徑的算法,算法的主要思想是:在對(duì)子排列進(jìn)行擴(kuò)展操作時(shí), FEBF首先從已有的子排列中選擇一個(gè)對(duì)應(yīng)路徑的權(quán)重最小的一個(gè)子排列,然后對(duì)它進(jìn)行擴(kuò)展操作,并得到對(duì)應(yīng)的路徑,所有規(guī)則點(diǎn)擴(kuò)展結(jié)束之后,FEBF刪除這個(gè)子排列,然后重復(fù)上述操作,直至找到一個(gè)基于規(guī)則R的排列,它所對(duì)應(yīng)的路徑即為基于規(guī)則R的最短路徑.

FEBF算法本質(zhì)上也是逐步擴(kuò)展IR的長(zhǎng)度為1的子排列到長(zhǎng)度為r的子排列,它采用最短優(yōu)先的策略盡可能少地計(jì)算IR的子排列,從而可以盡快找到問(wèn)題的解.FEBF算法的偽代碼見算法3.

算法3.FEBF(G,vs,ve,R).

輸入:圖G,起點(diǎn)vs,終點(diǎn)ve,規(guī)則R=(I,R);

給定圖G(V,E,w),起點(diǎn)為vs,終點(diǎn)為ve,規(guī)則R=(I,R),FEBF利用優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)從已有子排列中選出具有最小權(quán)值的路徑及其相應(yīng)的子排列.算法首先定義優(yōu)先級(jí)隊(duì)列Q,Q中存儲(chǔ)的元素為二元組,記為〈π,w(p|π)〉,其中,π為IR的子排列,并用w(p|π)的值進(jìn)行優(yōu)先級(jí)比較,以實(shí)現(xiàn)對(duì)Q中的元素從小到大進(jìn)行排序(第1行).接下來(lái)調(diào)用算法1得到廣義規(guī)則樹TR(第2行),然后用NN算法求解得到基于規(guī)則R的路徑pg,令θ等于pg的權(quán)重(第3行、第4行).為了利用最優(yōu)子排列過(guò)濾子排列,FEBF逐步構(gòu)建最優(yōu)子排列表(記為Ω)來(lái)存儲(chǔ)已得到的最優(yōu)子排列.當(dāng)擴(kuò)展得到子排列πl(wèi)時(shí),FEBF首先查找最優(yōu)子排列表中對(duì)應(yīng)位置的元素(記為,其中,v*為πl(wèi)末尾位置的頂點(diǎn),Vπl(wèi)為子排列πl(wèi)對(duì)應(yīng)的點(diǎn)集),然后對(duì)和w(p|πl(wèi))進(jìn)行比較:若,則將的值設(shè)為w(p|πl(wèi)) 且保留子排列πl(wèi)并對(duì)其進(jìn)行后續(xù)操作;否則,刪除子排列πl(wèi).FEBF將最優(yōu)子排列表中每一個(gè)元素的值都初始化為∞(第 5行).接下來(lái),FEBF將逐步擴(kuò)展子排列直至找到基于規(guī)則R的排列(第6行～第20行).

在構(gòu)建IR的1-子排列時(shí),因?yàn)橹挥笑?=vs這一個(gè)1子排列滿足規(guī)則,因此,FEBF將 〈π1,w(p|π1)〉插入到優(yōu)先級(jí)隊(duì)列Q中(第 6 行、第 7 行),然后彈出Q的隊(duì)首元素〈π′,w(p|π′)〉,令v*為π′末尾位置的點(diǎn)(第 8 行).如果v*=ve(第 9行),則表示π′是一個(gè)基于規(guī)則R的排列(由定理2.1可得),又因?yàn)镼每次彈出的位于隊(duì)首的元素都具有最小的路徑權(quán)重,因此,p|π′即為基于規(guī)則R的最短路徑,FEBF返回此路徑作為問(wèn)題的解(第 21行、第 22行);否則(v*≠ve),執(zhí)行以下循環(huán)操作(第10行～第19行).首先,FEBF依次遍歷規(guī)則點(diǎn)集IR中除vs之外的其他所有點(diǎn)(第10行),然后對(duì)每一個(gè)v∈IR-{vs}做如下操作:如果π′中不包含點(diǎn)v且v的所有父結(jié)點(diǎn)均已被p|π′合法訪問(wèn),那么將v添加到π′的末尾構(gòu)成新的子排列π,若Ωv,Vπ＞w(p|π),則將Ωv,Vπ的值設(shè)為w(p|π),并將〈π,w(p|π)〉插入到Q中(第11行～第17行).若IR-{vs}中的每個(gè)點(diǎn)均已完成上述操作,則 FEBF 彈出Q的隊(duì)首元素〈π′,w(p|π′)〉,令v*為π′末尾位置的點(diǎn)(第19行),然后開始下一輪循環(huán).

例5.1:接例1.1,利用FEBF算法求解基于規(guī)則R的最短路徑.

FEBF首先生成〈v1,0〉并把它插入到優(yōu)先級(jí)隊(duì)列Q中,接下來(lái)的操作是:從Q中彈出〈v1,0〉,利用它擴(kuò)展得到〈v1v2,2〉,〈v1v6,5〉并分別插入到Q中;

從Q中彈出〈v1v2,2〉,利用它擴(kuò)展得到〈v1v2v4,3〉,〈v1v2v5,4〉,〈v1v2v6,5〉并分別插入到Q中;從Q中彈出〈v1v2v4,3〉,利用它擴(kuò)展得到〈v1v2v4v5,4〉,〈v1v2v4v6,5〉并分別插入到Q中;從Q中彈出〈v1v2v5,4〉,利用它擴(kuò)展得到〈v1v2v5v4,7〉,〈v1v2v5v6,9〉并分別插入到Q中;從Q中彈出〈v1v2v4v5,4〉,利用它擴(kuò)展得到〈v1v2v4v5v6,9〉并插入到Q中;從Q中彈出〈v1v6,5〉,利用它擴(kuò)展得到〈v1v6v2,9〉并插入到Q中;

從Q中彈出〈v1v2v6,5〉,利用它擴(kuò)展得到〈v1v2v6v4,10〉, 〈v1v2v6v5,7〉并分別插入到Q中;

從Q中彈出〈v1v2v4v6,5〉,利用它擴(kuò)展得到〈v1v2v4v6v5,7〉并插入到Q中;

從Q中彈出〈v1v2v5v4,7〉,利用它擴(kuò)展得到〈v1v2v5v4v6,9〉并插入到Q中;

從Q中彈出〈v1v2v6v5,7〉,利用它擴(kuò)展得到〈v1v2v6v5v4,10〉并插入到Q中;

從Q中彈出〈v1v2v4v6v5,7〉,利用它擴(kuò)展得到〈v1v2v4v6v5v3,8〉并插入到Q中;

從Q中彈出〈v1v2v4v6v5v3,8〉且滿足路徑搜索終止條件,此時(shí)算法終止,FEBF返回(v1,v3,v2,v4,v6,v5,v3)作為問(wèn)題的解.

在例4.1中,FE算法總共生成24個(gè)子排列;而在例5.1中,FEBF總共生成18個(gè)子排列.顯然,FEBF能有效減少算法生成的子排列個(gè)數(shù).

5.2 優(yōu)化技術(shù)

本節(jié)提出3個(gè)優(yōu)化技術(shù)來(lái)提高FEBF算法的效率.

· 緩存機(jī)制

給定IR的基于規(guī)則R的兩個(gè)不同排列π和π′,這兩個(gè)排列對(duì)應(yīng)的路徑p*|π′和p|π′可能包含一些相同的路徑片段,因此這些相同的路徑片段本質(zhì)上只需要計(jì)算一次.本文可以采用緩存機(jī)制,將計(jì)算過(guò)的路徑片段存儲(chǔ)在內(nèi)存中,這樣就可以避免大量重復(fù)的計(jì)算,從而提高算法的效率.比如在例 4.1中,長(zhǎng)度為 6的排列v1v2v4v6v5v3和v1v2v4v6v5v3所對(duì)應(yīng)的路徑包含相同的路徑片段v1?v2和v2?v4,因此當(dāng)采用緩存機(jī)制后,這兩個(gè)路徑片段僅僅只需要計(jì)算一次,當(dāng)再次需要計(jì)算這兩個(gè)路徑片段時(shí),可以直接從緩存中讀取出來(lái).實(shí)驗(yàn)結(jié)果驗(yàn)證了緩存機(jī)制可以有效避免大量的冗余計(jì)算.

· 排列過(guò)濾

當(dāng) FE對(duì)長(zhǎng)度為l-1的子排列πl(wèi)-1進(jìn)行擴(kuò)展操作時(shí),它首先判斷規(guī)則點(diǎn)v∈IR是否已在πl(wèi)-1中,然后再判斷v的所有父結(jié)點(diǎn)是否已被路徑合法訪問(wèn),若上述兩個(gè)條件都滿足,則將v添加到πl(wèi)-1的末尾構(gòu)成長(zhǎng)度為l的子排列πl(wèi).上述兩個(gè)條件本質(zhì)上是從規(guī)則點(diǎn)v是否應(yīng)該被合法訪問(wèn)這個(gè)角度判斷v是否應(yīng)該添加到πl(wèi)-1的末尾,本文也可以從路徑權(quán)重的角度來(lái)進(jìn)一步過(guò)濾生成的排列,即:已知vi,vj∈IR且vj已被添加到πl(wèi)-1的末尾構(gòu)成πl(wèi)-1⊕vj,v*是πl(wèi)-1末尾位置的頂點(diǎn),如果v*到vj的最短路徑是v*到vi最短路徑的子路徑,則vi不應(yīng)被添加到πl(wèi)-1的末尾構(gòu)成πl(wèi)-1⊕vi.下面的定理保證了排列過(guò)濾的正確性.

定理5.1.給定長(zhǎng)度為l-1 的子排列πl(wèi)-1,v*是πl(wèi)-1末尾位置的頂點(diǎn),已知vi,vj∈IR,πl(wèi)-1⊕vj和πl(wèi)-1⊕vi分別為 FE用vj和vi對(duì)πl(wèi)-1進(jìn)行擴(kuò)展操作得到的長(zhǎng)度為l的子排列,如果v*到vj的最短路徑是v*到vi最短路徑的子路徑,則IR的所有基于規(guī)則R且以πl(wèi)-1⊕vi為前綴的排列π都對(duì)應(yīng)一個(gè)IR基于規(guī)則R且以πl(wèi)-1⊕vj為前綴的排列π′,且w(p|π′)≤w(p|π).

證明:不失一般性,設(shè)πl(wèi)-1=v1v2…v*是IR的長(zhǎng)度為l-1 的子排列,πl(wèi)-1⊕vj和πl(wèi)-1⊕vi分別為 FE 用vj和vi對(duì)πl(wèi)-1進(jìn)行擴(kuò)展操作得到的長(zhǎng)度為l的子排列,已知v*到vj的最短路徑是v*到vi最短路徑的子路徑.

綜上可得w(p|π′)≤w(p|π).證畢.□

在例4.1中,對(duì)于長(zhǎng)度為2的子排列v1v2,可以分別用點(diǎn)v4,v5,v6對(duì)v1v2進(jìn)行擴(kuò)展操作,從而得到v1v2v4,v1v2v5,v1v2v6.因?yàn)閺膙2到v4的最短路徑(v2,v4)是從v2到v5最短路徑(v2,v4,v5)的子路徑,也是從v2到v6最短路徑(v2,v4,v6)的子路徑,因此可以過(guò)濾掉子排列v1v2v5和v1v2v6.

· 權(quán)重預(yù)估

當(dāng) FE擴(kuò)展長(zhǎng)度為l-1的子排列得到長(zhǎng)度為l的子排列πl(wèi)時(shí),v*是πl(wèi)末尾位置的頂點(diǎn).對(duì)于IR的所有基于規(guī)則R且以πl(wèi)為前綴的排列π,可以估計(jì)w(p|π)的下限,從而使得FE可以盡量早的過(guò)濾掉一些排列,提高算法的效率.具體的做法是:當(dāng)?shù)玫溅衛(wèi)后,首先計(jì)算w(p|πl(wèi)) ,然后計(jì)算從v*到終點(diǎn)ve的最短路徑的權(quán)重,然后得到這兩個(gè)路徑的權(quán)重之和w*,若w*>θ,則舍棄子排列πl(wèi);否則保留πl(wèi).

5.3 復(fù)雜度分析

本文首先分析FEBF的時(shí)間復(fù)雜度,對(duì)于長(zhǎng)度為l(1≤l≤|IR|)的子排列,FEBF至多生成個(gè),因?yàn)楸疚牟捎肅H技術(shù)求解兩點(diǎn)之間的最短路徑,因此,FEBF的時(shí)間復(fù)雜度為O((nlogn+m)·(r·2r))(n=|V|,m=|E|);接下來(lái)分析算法的空間復(fù)雜度,FEBF的優(yōu)先級(jí)隊(duì)列Q中至多存儲(chǔ)O(r·2r)個(gè)元素,每個(gè)元組至多消耗的內(nèi)存為O(n),除此之外,最優(yōu)子排列表Ω消耗的內(nèi)存至多為O(r·2r),因此,FEBF 的空間復(fù)雜度為O(n·r·2r+r·2r)=O(n·r·2r).

6 實(shí)驗(yàn)分析

本節(jié)使用不同規(guī)模的真實(shí)數(shù)據(jù)集來(lái)驗(yàn)證算法的有效性,并與解決同類問(wèn)題中已有的最好算法作對(duì)比.第6.1節(jié)介紹了實(shí)驗(yàn)的基本設(shè)置,第6.2節(jié)對(duì)實(shí)驗(yàn)的結(jié)果進(jìn)行分析.

6.1 實(shí)驗(yàn)設(shè)置

本文的所有算法都使用 C++語(yǔ)言實(shí)現(xiàn),并在 Linux操作系統(tǒng)環(huán)境下進(jìn)行測(cè)試,硬件的信息為:Intel(R)Core(TM) i7-4770K,32GB RAM.本文對(duì)每組實(shí)驗(yàn)重復(fù)100次,并把平均值作為此組實(shí)驗(yàn)的結(jié)果.如果一個(gè)算法在某個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間超過(guò)24h或者超過(guò)32GB RAM,則忽略此算法在這個(gè)數(shù)據(jù)集上的運(yùn)行結(jié)果.

· 數(shù)據(jù)集

本文使用8個(gè)真實(shí)數(shù)據(jù)集來(lái)驗(yàn)證本文提出的算法,其中4個(gè)為道路交通網(wǎng)數(shù)據(jù)集(http://www.dis.uniroma1.it/challenge9/index.shtml),另外 4個(gè)為非道路交通網(wǎng)數(shù)據(jù)集(http://snap.stanford.edu/data/),數(shù)據(jù)集的詳細(xì)信息見表3,d表示頂點(diǎn)的平均度的大小.對(duì)于道路交通網(wǎng)數(shù)據(jù)集,本文將兩點(diǎn)之間的距離作為邊的權(quán)重;對(duì)于非道路交通網(wǎng)數(shù)據(jù)集,本文給每一條邊隨機(jī)生成一個(gè)1～100之間的值作為此邊的權(quán)重值.

Table 3 Datasets表3 數(shù)據(jù)集

· 查詢集

對(duì)于每個(gè)數(shù)據(jù)集,本文生成25個(gè)查詢集 Q1～Q25,它們分別對(duì)應(yīng)不同規(guī)模的規(guī)則R.在現(xiàn)實(shí)生活中,I的規(guī)模一般不超過(guò)10,本文從實(shí)際應(yīng)用的角度設(shè)計(jì)了以下的查詢集.對(duì)于Q1～Q5,|R|=5,I中頂點(diǎn)的個(gè)數(shù)依次為6～10;對(duì)于 Q6～Q10,|I|=8,R中偏序關(guān)系個(gè)數(shù)依次為 4,6,8,10,12;對(duì)于 Q11～Q15,R=?,I中頂點(diǎn)的個(gè)數(shù)依次為 6～10;對(duì)于Q16～Q20,I中頂點(diǎn)的個(gè)數(shù)依次為6～10,對(duì)應(yīng)的R中偏序關(guān)系個(gè)數(shù)依次為15,21,28,36,45;對(duì)于Q21～Q25,|R|=10,I中頂點(diǎn)的個(gè)數(shù)依次為 16～20.注意到:查詢集 Q11～Q15中偏序集個(gè)數(shù)為 0,此問(wèn)題退化為廣義旅行商問(wèn)題;Q16～Q20中的偏序集可以構(gòu)成一個(gè)全序集,即I中頂點(diǎn)的合法訪問(wèn)順序已確定,此問(wèn)題退化為最優(yōu)序列路徑查詢問(wèn)題.Q21～Q25中規(guī)則R的規(guī)模較大,是用來(lái)驗(yàn)證算法能否應(yīng)用于輸入規(guī)模較大的情形.對(duì)于上述所有的查詢集,I中所有的頂點(diǎn)以及起點(diǎn)vs和終點(diǎn)ve都是采用隨機(jī)數(shù)的方式隨機(jī)生成,R中偏序關(guān)系也是隨機(jī)從對(duì)應(yīng)的I中選擇兩個(gè)點(diǎn)構(gòu)成且保證R中不存在兩個(gè)相同的偏序關(guān)系.

· 對(duì)比算法

對(duì)每一組實(shí)驗(yàn),本文將算法FE、FEBF與算法SBS和SFS作對(duì)比,SBS[13]和SFS[13]是同類問(wèn)題的已有算法中性能最好的精確算法.本文不與其他的算法對(duì)比的原因是:(1) BBS[13]和BFS[13]分別為SBS和SFS的優(yōu)化算法,主要是解決當(dāng)I中包含的不是點(diǎn)而是類別信息時(shí),隨著每個(gè)類中包含頂點(diǎn)的個(gè)數(shù)增多,導(dǎo)致搜索空間增大的問(wèn)題,當(dāng)每個(gè)類中只包含一個(gè)頂點(diǎn)時(shí),優(yōu)化前后的算法性能相同;(2) NN[14]是一個(gè)啟發(fā)式算法,它最終返回的路徑是一條接近最優(yōu)的路徑,而本文的算法返回的是一條最優(yōu)的路徑.

· 其他

由于SBS和SFS都為應(yīng)用于空間數(shù)據(jù)集上的算法,在空間數(shù)據(jù)集上可以直接利用經(jīng)緯度坐標(biāo)求得兩點(diǎn)之間的歐氏距離,而本文所設(shè)計(jì)的算法均應(yīng)用于普通的圖數(shù)據(jù),即,由點(diǎn)和邊構(gòu)成的數(shù)據(jù),考慮到對(duì)比的公平性,本文對(duì)所有的算法均利用CH技術(shù)來(lái)求解兩點(diǎn)之間的最短距離.

6.2 結(jié)果分析

· 查詢效率

在查詢集Q1～Q5上算法的運(yùn)行結(jié)果如圖4所示.可以看出:對(duì)于每一個(gè)數(shù)據(jù)集,SFS的查詢時(shí)間都大于其他算法的查詢時(shí)間,FE算法的查詢時(shí)間明顯小于SBS和SFS的查詢時(shí)間,FEBF算法的查詢時(shí)間小于其他所有算法,即使在具有百萬(wàn)個(gè)頂點(diǎn)的數(shù)據(jù)集(FLA)上,FEBF也能在 1s左右得到查詢的結(jié)果.因?yàn)椴樵兗?Q1～Q5具有相同個(gè)數(shù)的偏序關(guān)系,隨著規(guī)則點(diǎn)集的規(guī)模逐漸增大,規(guī)則點(diǎn)集的基于規(guī)則R的排列也逐漸增多,因此算法的查詢時(shí)間也逐漸增多,圖中的結(jié)果驗(yàn)證了這一點(diǎn),即:從 Q1～Q5,所有算法的查詢時(shí)間都逐漸增多.顯然,改進(jìn)后的FEBF算法比原始的FE算法性能有較大的提高.

Fig.4 Query efficiency on Q1～Q5圖4 在Q1～Q5上的查詢效率

圖5展示了算法在查詢集Q6～Q10上的查詢結(jié)果.對(duì)于所有的數(shù)據(jù)集,SFS具有最大的查詢時(shí)間,FEBF算法的查詢時(shí)間小于其他所有算法.因?yàn)椴樵兗疩6～Q10具有相同個(gè)數(shù)的規(guī)則點(diǎn),隨著R中偏序關(guān)系的逐漸增多,規(guī)則點(diǎn)集的基于規(guī)則R的排列將逐漸減少.可以看出對(duì)于所有算法,Q6～Q10的查詢時(shí)間都逐漸減小.

Fig.5 Query efficiency on Q6～Q10圖5 在Q6～Q10上的查詢效率

查詢集Q11～Q15中包含的偏序關(guān)系個(gè)數(shù)為0,此問(wèn)題退化為廣義旅行商問(wèn)題,算法的查詢結(jié)果如圖6所示.因?yàn)?Q11～Q15的偏序關(guān)系個(gè)數(shù)為 0,則規(guī)則點(diǎn)集的任意排列都為基于規(guī)則R的排列,算法的查詢時(shí)間顯然大于在Q1～Q5上的查詢時(shí)間.對(duì)于每一個(gè)數(shù)據(jù)集,FEBF的查詢時(shí)間都小于其他算法的查詢時(shí)間.

Fig.6 Query efficiency on Q11～Q15圖6 在Q11～Q15上的查詢效率

查詢集Q16～Q20的偏序集可以構(gòu)成一個(gè)全序集,即I中頂點(diǎn)的合法訪問(wèn)順序已確定,此問(wèn)題退化為最優(yōu)序列路徑查詢問(wèn)題,算法的查詢結(jié)果如圖7所示.由于每個(gè)類中僅包含一個(gè)頂點(diǎn),因此,Q16～Q20本質(zhì)上為計(jì)算|I|+1個(gè)最短路徑.從圖中可知:對(duì)于每一個(gè)數(shù)據(jù)集,SBS算法的查詢時(shí)間都是最短的.這是因?yàn)镾BS沒(méi)有利用其他的優(yōu)化策略來(lái)過(guò)濾子排列,而對(duì)于Q16～Q20來(lái)說(shuō),基于規(guī)則R的子排列只有一個(gè),因此,SBS可以快速地求解得到問(wèn)題的解.FE和FEBF算法由于利用了一些過(guò)濾子排列的優(yōu)化技術(shù)(Q16～Q20并不需要對(duì)子排列進(jìn)行過(guò)濾),從而增加了算法的運(yùn)行時(shí)間.然而在現(xiàn)實(shí)生活中,這種查詢幾乎不存在(退化為普通的最短路徑問(wèn)題).

Fig.7 Query efficiency on Q16～Q20圖7 在Q16～Q20上的查詢效率

查詢集Q21～Q25對(duì)應(yīng)的規(guī)則R規(guī)模較大,因此算法的運(yùn)行時(shí)間較長(zhǎng).在此,本文僅給出算法FEBF的查詢時(shí)間.從圖8的結(jié)果來(lái)看:即使在規(guī)則R的規(guī)模較大時(shí),本文的FEBF算法也可以在一定時(shí)間內(nèi)給出問(wèn)題的解.

Fig.8 Query efficiency on Q21～Q25圖8 在Q21～Q25上的查詢效率

· 改進(jìn)后的算法有效性

FEBF算法是FE算法的改進(jìn)算法,圖9展示了FE和FEBF算法在查詢集Q11～Q15上的加速比(加速比是指FE算法的查詢時(shí)間與FEBF算法的查詢時(shí)間的比值),結(jié)果表明:在每個(gè)數(shù)據(jù)集上,隨著規(guī)則點(diǎn)個(gè)數(shù)的增多,加速比越來(lái)越大.顯然,改進(jìn)后的FEBF算法的運(yùn)行效率極大地優(yōu)于FE算法的運(yùn)行效率.

Fig.9 Speedup ratio of improved algorithm圖9 改進(jìn)后算法的加速比

FE和FEBF算法的查詢時(shí)間主要與生成的子排列個(gè)數(shù)有關(guān):生成的子排列越多,查詢時(shí)間則越長(zhǎng);反之,查詢時(shí)間則越短.因此,本文用子排列的減少比(NFE表示FE算法生成的子排列個(gè)數(shù),NFEBF表示FEBF算法生成的子排列個(gè)數(shù))來(lái)反映FE和FEBF算法的性能優(yōu)劣,結(jié)果如圖10所示.對(duì)于道路交通網(wǎng)數(shù)據(jù)集,FEBF算法生成的子排列個(gè)數(shù)比FE算法生成的子排列個(gè)數(shù)降低了至少20%;對(duì)于非道路交通網(wǎng)數(shù)據(jù)集,FEBF算法生成的子排列個(gè)數(shù)相比于FE算法生成的子排列個(gè)數(shù)也有所降低.

Fig.10 Reduction ratio of sub-permutation圖10 子排列的減少比

· 優(yōu)化技術(shù)的有效性

對(duì)于FEBF算法,本文提出了3個(gè)優(yōu)化技術(shù).圖11展示了在查詢集Q11～Q15上,FEBF算法在未使用優(yōu)化技術(shù)與使用優(yōu)化技術(shù)兩種情況下的加速比(即未使用優(yōu)化技術(shù)的FEBF算法的查詢時(shí)間與使用優(yōu)化技術(shù)的FEBF算法的查詢時(shí)間的比值),結(jié)果表明:在每個(gè)數(shù)據(jù)集上,相對(duì)于未使用優(yōu)化技術(shù)的 FEBF算法,使用優(yōu)化技術(shù)的FEBF算法能夠有效降低算法的查詢時(shí)間.

Fig.11 Effectiveness of optimizing techniques圖11 優(yōu)化技術(shù)的有效性

7 相關(guān)工作

本節(jié)介紹相關(guān)的工作,并把最短路徑問(wèn)題分為傳統(tǒng)的最短路徑問(wèn)題和 ORQ問(wèn)題.ORQ問(wèn)題又細(xì)分為如下幾類:已指定必須經(jīng)過(guò)類別的訪問(wèn)順序、未指定必須經(jīng)過(guò)類別的訪問(wèn)順序、部分指定必須經(jīng)過(guò)類別的訪問(wèn)順序.下面分類依次介紹相關(guān)的工作.

· 傳統(tǒng)的最短路徑問(wèn)題

傳統(tǒng)的最短路徑問(wèn)題具有不同的應(yīng)用場(chǎng)景.稠密距離圖(dense distance graph,簡(jiǎn)稱 DDG)是平面圖的分解圖,即:將一個(gè)平面圖分解為幾個(gè)區(qū)域,每個(gè)區(qū)域所包含的頂點(diǎn)個(gè)數(shù)最多為r,其中,r

· 已指定必須經(jīng)過(guò)類別的訪問(wèn)順序

已知必須經(jīng)過(guò)的類別集合,若已規(guī)定所有類別的訪問(wèn)順序,則 ORQ問(wèn)題稱為類別全序的最優(yōu)路徑查詢問(wèn)題.R-LORD[23]是一個(gè)精確算法,用來(lái)求解空間數(shù)據(jù)集上類別全序的最優(yōu)路徑查詢問(wèn)題,假設(shè)p*=(vs,v1,v2,…,vr,ve)是上述問(wèn)題的一個(gè)最優(yōu)路徑,則p*的任意一個(gè)后綴p在p中都是最短的,P是滿足下面兩個(gè)條件的路徑集合:(1) 以p的起點(diǎn)作為起點(diǎn);(2) 與p相同的順序訪問(wèn)p中的所有類.基于此,R-LORD采用動(dòng)態(tài)規(guī)劃的方式逐步構(gòu)建最優(yōu)后綴表.在構(gòu)建最優(yōu)后綴表之前,R-LORD利用貪心算法得到一條滿足類別訪問(wèn)順序的路徑,并用此路徑的權(quán)重作為閾值來(lái)過(guò)濾不可能成為最優(yōu)路徑的后綴.在構(gòu)建最優(yōu)后綴表時(shí),R-LORD利用橢圓剪枝技術(shù)來(lái)排除無(wú)法構(gòu)成最優(yōu)路徑的子路徑.Michael等人提出了基于動(dòng)態(tài)規(guī)劃的算法求解類別全序的最優(yōu)路徑查詢問(wèn)題[24],此算法主要是逐步構(gòu)建一個(gè)實(shí)值矩陣X,X是一個(gè)r行g(shù)列的矩陣,其中,r表示必須經(jīng)過(guò)的類別個(gè)數(shù),g表示規(guī)模最大的類中包含的頂點(diǎn)個(gè)數(shù).矩陣的每個(gè)元素X[i,j]是一個(gè)最優(yōu)子路徑的長(zhǎng)度,此路徑表示從起點(diǎn)到訪問(wèn)順序?yàn)閕的類別中的第j個(gè)頂點(diǎn)的最優(yōu)子路徑.此外,Michael還設(shè)計(jì)了兩個(gè)優(yōu)化技術(shù),分別為圖結(jié)構(gòu)優(yōu)化和問(wèn)題結(jié)構(gòu)優(yōu)化,并通過(guò)剪枝策略來(lái)解決由于類別規(guī)模過(guò)大導(dǎo)致算法運(yùn)行時(shí)間過(guò)長(zhǎng)的問(wèn)題.由于本文所研究的問(wèn)題對(duì)類別的訪問(wèn)順序只做了部分的限制,即,并未完全指定每個(gè)類別的訪問(wèn)順序,因此,上述兩個(gè)算法都無(wú)法用來(lái)求解本文所研究的問(wèn)題.

· 未指定必須經(jīng)過(guò)類別的訪問(wèn)順序

已知必須經(jīng)過(guò)的類別集合,若沒(méi)有規(guī)定任何類別的訪問(wèn)順序,則ORQ問(wèn)題稱為類別無(wú)序的最優(yōu)路徑查詢問(wèn)題.對(duì)于空間數(shù)據(jù)集,Li等人提出了幾個(gè)近似算法來(lái)求解類別無(wú)序的最優(yōu)路徑查詢問(wèn)題[25].ANN[25]是一個(gè)近似算法,其主要思想是:從單個(gè)起點(diǎn)構(gòu)成的路徑p′開始,反復(fù)地從G中選擇一個(gè)離p′末尾頂點(diǎn)最近的點(diǎn)(記為vc),且vc對(duì)應(yīng)的類別c尚未被p′訪問(wèn),然后將vc添加到p′的末尾構(gòu)成新的p′.重復(fù)上述操作,直至所有的類別都已被p′訪問(wèn),最后將終點(diǎn)添加到p′的末尾,從而構(gòu)成一條包含指定所有類別的路徑.AMD[25]也是一個(gè)近似算法,它的主要思想是:對(duì)于每一個(gè)必須訪問(wèn)的類c,從類c中選擇一個(gè)頂點(diǎn)vc,使得vc離起點(diǎn)和終點(diǎn)的距離之和小于其他任意點(diǎn)離起點(diǎn)和終點(diǎn)的距離之和,從每個(gè)類中選擇得到的點(diǎn)構(gòu)成集合VC,然后調(diào)用ANN算法(此處在調(diào)用ANN算法時(shí),將G中的點(diǎn)替換為VC中的點(diǎn)),從而得到一條包含指定所有類別的路徑.LESS[26]是一個(gè)求解此類問(wèn)題的精確算法,它的本質(zhì)是將指定的所有類別進(jìn)行全排列,每個(gè)類別在排列中的位置表示此類別在路徑中被訪問(wèn)時(shí)所處的位置.對(duì)于每一個(gè)排列,按順序依次從排列的類別中選擇一個(gè)頂點(diǎn),最終構(gòu)成一條包含指定所有類別的路徑.LESS枚舉出所有排列對(duì)應(yīng)的所有路徑,然后選擇一條長(zhǎng)度最小的路徑作為問(wèn)題的最優(yōu)解.由于本文所研究的問(wèn)題對(duì)類別的訪問(wèn)順序做了部分的限制,而上述算法只能解決訪問(wèn)順序沒(méi)有限制的情況,因此,上述兩個(gè)算法都無(wú)法用來(lái)求解本文所研究的問(wèn)題.

· 部分指定必須經(jīng)過(guò)類別的訪問(wèn)順序

已知必須經(jīng)過(guò)的類別集合,若已規(guī)定部分類別的訪問(wèn)順序,則 ORQ問(wèn)題稱為類別偏序的最優(yōu)路徑查詢問(wèn)題.NN[14]是求解類別偏序的最優(yōu)路徑查詢問(wèn)題的啟發(fā)式算法,它最終返回一條接近最優(yōu)的路線,算法的具體流程為:從單個(gè)起點(diǎn)構(gòu)成的路徑p′開始,反復(fù)地從G中選擇一個(gè)離p′末尾頂點(diǎn)最近的點(diǎn)(記為vc),且vc對(duì)應(yīng)的類別c在圖GQ(GQ是查詢圖且是一個(gè)有向無(wú)環(huán)圖,GQ中的每個(gè)點(diǎn)都對(duì)應(yīng)于G中的一個(gè)類別信息,GQ中每條有向邊(c,c′)表示G中類別c的點(diǎn)先于類別c′的點(diǎn)訪問(wèn))中且入度為0,然后,從GQ中刪除類別c以及與它相連的邊,接著將vc添加到p′的末尾構(gòu)成新的p′.重復(fù)上述操作,直至GQ中不包含任何點(diǎn),最終找到一條滿足約束條件的路線.Li等人提出了4個(gè)精確算法來(lái)求解在空間數(shù)據(jù)集上的此類問(wèn)題[13],它們分別為SBS,BBS,SFS和BFS. SBS利用R-LORD[23]中提出的后綴最優(yōu)定理,逐步求解1后綴到r后綴(r為必須經(jīng)過(guò)的類別的個(gè)數(shù)),然后,從r后綴中選擇一個(gè)路徑長(zhǎng)度最小的路徑作為此問(wèn)題的最優(yōu)解.BBS是 SBS的優(yōu)化算法,對(duì)于每一個(gè)必須經(jīng)過(guò)的類別,BBS首先將具有相同類別的點(diǎn)進(jìn)行聚類,即,把彼此距離較近的一些點(diǎn)歸為同一組,然后,BBS以每一個(gè)組的點(diǎn)為單位,執(zhí)行與SBS相同的操作,當(dāng)每個(gè)類中包含的點(diǎn)的個(gè)數(shù)較多時(shí),BBS可以很大程度地提高算法的運(yùn)行效率.SFS本質(zhì)上是采用分層回溯的方式求解問(wèn)題的解,算法運(yùn)行時(shí)所處的層數(shù)表示此時(shí)已得到的子路徑所包含的類別個(gè)數(shù).SFS采用 NN[14]添加頂點(diǎn)的方式,每次選擇離當(dāng)前路徑末尾頂點(diǎn)最近的一個(gè)點(diǎn),每往路徑中添加一個(gè)新的頂點(diǎn),則意味著SFS進(jìn)入到當(dāng)前層的下一層,然后再執(zhí)行相同的添加頂點(diǎn)的操作.當(dāng)算法到達(dá)第r層后,則表明此算法已找到一條滿足約束的路徑,然后算法回溯到r-1層,將離當(dāng)前路徑末尾頂點(diǎn)次近的點(diǎn)添加到路徑的末尾.重復(fù)上述回溯操作,直至得到所有滿足約束的路徑,最后返回一條最優(yōu)的路徑.BFS是 SFS的優(yōu)化算法,與BBS類似,BFS首先將具有相同類別的點(diǎn)進(jìn)行聚類,即,把彼此距離較近的一些點(diǎn)歸為同一組,然后,BFS以每一個(gè)組的點(diǎn)為單位,執(zhí)行與SFS相同的操作,最終得到問(wèn)題的最優(yōu)解.由于本文所研究的問(wèn)題是基于普通的圖數(shù)據(jù)而非空間數(shù)據(jù),因此上述 4個(gè)算法無(wú)法直接應(yīng)用于本文所研究的問(wèn)題,而且這些算法較少過(guò)濾掉不可能成為最優(yōu)路徑的子路徑,使得算法的運(yùn)行時(shí)間較長(zhǎng).

廣義旅行商問(wèn)題是傳統(tǒng)旅行商問(wèn)題的變種,帶優(yōu)先級(jí)約束的旅行商問(wèn)題屬于廣義旅行商問(wèn)題的一種,它可以描述為:已知n個(gè)城市之間的相互距離,現(xiàn)有一旅行商計(jì)劃全部訪問(wèn)這n個(gè)城市,并且每個(gè)城市只能訪問(wèn)一次,在訪問(wèn)這些城市時(shí)必須滿足一定的約束條件(例如,必須先訪問(wèn)城市1和城市2,然后才能訪問(wèn)城市3),最后,旅行商返回到出發(fā)的城市,目的是尋找一條旅行商行走的路線,使得此路線滿足上述約束條件且具有最小的距離.Ascheuer等人[27]提出了基于分支切割的算法來(lái)解決不對(duì)稱的有約束條件的旅行商問(wèn)題.Moon等人[28]和Wang等人[29]分別采用遺傳算法和整數(shù)規(guī)劃的方式解決帶有約束條件的旅行商問(wèn)題;有優(yōu)先約束的哈密頓路徑問(wèn)題(Hamiltonian path problems with precedence constraints)又稱為順序排序問(wèn)題(sequential ordering problem),可描述為尋找由指定的起點(diǎn)前往指定的終點(diǎn)的最短路徑查詢問(wèn)題,途中經(jīng)過(guò)其他所有頂點(diǎn)有且只有一次,而且頂點(diǎn)之間存在先后順序約束,Karan等人[30]提出了一個(gè)基于分支界限法的算法來(lái)解決順序排序問(wèn)題.已有的解決廣義旅行商問(wèn)題的精確算法本質(zhì)上為枚舉出每一種可能的路徑,因此這些算法不適用于大規(guī)模圖上問(wèn)題的求解,而本文所提的算法可以很好地應(yīng)用于大規(guī)模圖上的查詢.

8 總 結(jié)

本文設(shè)計(jì)了一個(gè)基于最優(yōu)子路徑的前向擴(kuò)展算法,該算法可以快速求解基于規(guī)則的最短路徑查詢問(wèn)題,并設(shè)計(jì)了前向擴(kuò)展算法的改進(jìn)算法——基于最短優(yōu)先策略的前向擴(kuò)展算法.從實(shí)驗(yàn)的結(jié)果來(lái)看,基于最短優(yōu)先策略的前向擴(kuò)展算法對(duì)原始算法的查詢效率有很大程度的提高.本文在真實(shí)的數(shù)據(jù)集上設(shè)計(jì)了大量的實(shí)驗(yàn),并與已有的性能最好的算法作比較,實(shí)驗(yàn)結(jié)果表明,本文的算法大幅度優(yōu)于已有的算法.