王婧,劉輝平,金澈清

(華東師范大學(xué)計(jì)算機(jī)科學(xué)與軟件工程學(xué)院,上海200062)

基于正則表達(dá)式的限制性路徑規(guī)劃

王婧,劉輝平,金澈清

(華東師范大學(xué)計(jì)算機(jī)科學(xué)與軟件工程學(xué)院,上海200062)

傳統(tǒng)的路徑規(guī)劃算法大多以長(zhǎng)度、時(shí)間或代價(jià)等為度量標(biāo)準(zhǔn)搜索起止點(diǎn)間的最優(yōu)路徑,不適于解決有位置限制的路徑規(guī)劃需求,如搜索有序或無(wú)序地經(jīng)過(guò)全部或部分用戶指定的位置點(diǎn)或位置點(diǎn)類(lèi)別的最短路徑.本文主要針對(duì)這類(lèi)應(yīng)用場(chǎng)景,利用正則表達(dá)式表示復(fù)雜的限制性路徑規(guī)劃需求,形式化定義了基于正則表達(dá)式的限制性路徑規(guī)劃問(wèn)題并設(shè)計(jì)了通用的解決框架,在此框架基礎(chǔ)上提出了基本的限制性路徑規(guī)劃算法BCRP(Basic Constrained Route Planning)以及加入剪枝策略的改進(jìn)的限制性路徑規(guī)劃算法ICRP(Improved Constrained Route Planning),有效減少了搜索空間.最后通過(guò)在真實(shí)路網(wǎng)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果證明了方法的高效性.

限制性路徑規(guī)劃;正則表達(dá)式;最短路徑

0 引言

路徑規(guī)劃問(wèn)題旨在圖中尋找一條或多條從起點(diǎn)到終點(diǎn)并滿足一定度量標(biāo)準(zhǔn)如長(zhǎng)度、時(shí)間、代價(jià)或油耗等的最優(yōu)路徑,已經(jīng)在GPS導(dǎo)航、智慧交通、物流運(yùn)輸、無(wú)人機(jī)駕駛、旅游路線設(shè)計(jì)和通信路由等多個(gè)領(lǐng)域得到了廣泛應(yīng)用[1-6].傳統(tǒng)的路徑規(guī)劃算法主要根據(jù)度量標(biāo)準(zhǔn)定義的邊的權(quán)重來(lái)尋找具有最小權(quán)重和的路徑作為最優(yōu)路徑,除此之外現(xiàn)實(shí)生活中還存在大量對(duì)位置有多樣性限制的路徑規(guī)劃需求.如圖1所示為一個(gè)道路交通網(wǎng)絡(luò)的一部分,每個(gè)點(diǎn)代表一個(gè)興趣點(diǎn)(POI,Point of Interest),表示該點(diǎn)所屬的類(lèi)別;每條邊表示興趣點(diǎn)間的一條單向道路,邊上的數(shù)字表示該邊的權(quán)重(這里為道路的長(zhǎng)度).假設(shè)Tom結(jié)束了一天在A點(diǎn)的工作后,想先去一家餐廳吃飯,然后去電影院或酒吧放松一下(由于時(shí)間有限這二者只能擇其一),最后回到位于H點(diǎn)的家,他希望規(guī)劃一條滿足上述位置限制要求的最短路徑.

圖1 限制性路徑問(wèn)題的一個(gè)示例Fig.1 An example of the constrained route planning problem

日常生活中像這樣對(duì)位置點(diǎn)和位置點(diǎn)類(lèi)別有順序、多選等限制的路徑規(guī)劃需求十分常見(jiàn),也已有一些研究工作關(guān)注:最優(yōu)路徑查詢[7-13]搜索從查詢點(diǎn)出發(fā)經(jīng)過(guò)指定類(lèi)別集合的最短路徑,主要關(guān)注位置點(diǎn)類(lèi)別的無(wú)序、有序、部分有序等限制;文獻(xiàn)[14-16]查找從起點(diǎn)到終點(diǎn),途徑指定關(guān)鍵詞集合且滿足行程預(yù)算的路徑,忽略了途徑點(diǎn)的順序限制,加入關(guān)鍵詞匹配度、路徑流行度等考量因素更適于具體的應(yīng)用場(chǎng)景.現(xiàn)有工作僅是研究限制性路徑規(guī)劃問(wèn)題的子集或者特殊情況,不能解決對(duì)位置點(diǎn)既有經(jīng)過(guò)的順序限制,又有多選需求的路徑規(guī)劃.

鑒于此,本文研究在圖中搜索從給定起點(diǎn)到終點(diǎn),并對(duì)途徑位置點(diǎn)和類(lèi)別有順序、多選等多重限制的最優(yōu)路徑問(wèn)題.考慮到此類(lèi)路徑規(guī)劃需求中富含多種語(yǔ)義信息,引入正則表達(dá)式來(lái)表達(dá)查詢.正則表達(dá)式是表示字符串匹配模式的字符序列,常用來(lái)檢索或替換特定文本,利用其已有的運(yùn)算符定義可以表達(dá)路徑規(guī)劃查詢中的多種限制,且其解析后的有限自動(dòng)機(jī)也可以輔助篩選符合條件的路徑.首先,本文形式化定義了基于正則表達(dá)式的限制性路徑規(guī)劃問(wèn)題CRPP(Constrained Route Planning Problem);接著結(jié)合自動(dòng)機(jī)理論和Dijkstra最短路徑算法,提出了一個(gè)解決CRPP的通用框架;在此基礎(chǔ)上設(shè)計(jì)了一個(gè)基本的限制性路徑規(guī)劃算法BCRP(Basic Constrained Route Planning),并通過(guò)加入剪枝策略提出了改進(jìn)的限制性路徑規(guī)劃算法ICRP(Improved Constrained Route Planning),減少了搜索空間并提升了處理性能.

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

(1)提出并形式化定義了基于正則表達(dá)式的限制性路徑規(guī)劃問(wèn)題,即找到圖中從指定起點(diǎn)到終點(diǎn),并滿足個(gè)性化位置限制條件,如順序或無(wú)序經(jīng)過(guò)給定位置點(diǎn)或類(lèi)別集合的全集或子集的最短路徑,利用正則表達(dá)式完整準(zhǔn)確地表達(dá)復(fù)雜的限制性路徑查詢;

(2)設(shè)計(jì)了一個(gè)解決CRPP的通用框架,并基于此框架提出了基礎(chǔ)的和改進(jìn)的限制性路徑規(guī)劃算法,改進(jìn)的限制性路徑規(guī)劃算法通過(guò)剪枝策略顯著提升了時(shí)間和空間效率;

(3)應(yīng)用真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明方法的可行性和高效性.

本文內(nèi)容組織如下:第1節(jié)介紹相關(guān)工作,第2節(jié)給出了問(wèn)題的形式化定義,第3節(jié)敘述了通用的解決框架,在此框架的基礎(chǔ)上第4節(jié)闡釋了兩種限制性路徑規(guī)劃算法BCRP和ICRP,第5節(jié)介紹了實(shí)驗(yàn)及實(shí)驗(yàn)結(jié)果,最后第6節(jié)總結(jié)了全文.

1 相關(guān)工作

最優(yōu)路徑查詢起源于最短路徑問(wèn)題,由于考慮了多種限制性因素,因此相比最短路徑問(wèn)題更有實(shí)際意義.李飛飛等[7]提出了在空間數(shù)據(jù)庫(kù)中的路徑規(guī)劃查詢TPQ(Trip Planning Query),空間數(shù)據(jù)庫(kù)中的每個(gè)空間對(duì)象有位置和類(lèi)別信息,TPQ的目的是尋找從起點(diǎn)到終點(diǎn),經(jīng)過(guò)給定點(diǎn)類(lèi)別集合中每個(gè)類(lèi)別至少一個(gè)空間對(duì)象的最短路徑,是廣義旅行商問(wèn)題的特例. TPQ中用戶不能指定希望經(jīng)過(guò)的類(lèi)別順序,且文獻(xiàn)[7]采用近鄰搜索的思想給出問(wèn)題的近似解.Sharifzadeh等人[8]研究的最優(yōu)順序路徑查詢OSR(Optimal Sequenced Route Query),用來(lái)尋找從某一點(diǎn)開(kāi)始,嚴(yán)格按照指定順序經(jīng)過(guò)給定點(diǎn)類(lèi)別集合中每個(gè)類(lèi)別至少一個(gè)點(diǎn)的最短路徑,并給出了在歐式空間適用的LORD和R-LORD算法以及在路網(wǎng)中適用的PNE算法.文獻(xiàn)[9-10]通過(guò)研究OSR問(wèn)題空間的幾何學(xué)性質(zhì),基于泰森多邊形對(duì)給定的類(lèi)別順序進(jìn)行預(yù)處理,構(gòu)建了一系列AW-Voronoi Diagrams來(lái)有效解決OSR查詢.文獻(xiàn)[11]研究的通用最短路徑問(wèn)題本質(zhì)上為指定終點(diǎn)且嚴(yán)格有序的OSR,使用了動(dòng)態(tài)規(guī)劃的思想更適用于路網(wǎng)等大規(guī)模圖中.不同于OSR定義點(diǎn)類(lèi)別的全序,Chen等人[12]提出了一種多規(guī)則部分有序路徑MRPSR(Multi-rule Partial Sequenced Route)查詢,只有部分有序的類(lèi)別集合被定義.文獻(xiàn)[13]解決從起點(diǎn)出發(fā)經(jīng)過(guò)一個(gè)用戶定義的類(lèi)別集合的最優(yōu)路徑查詢,支持不同類(lèi)別間的部分順序限制.上述研究主要關(guān)注最短路徑上位置點(diǎn)的類(lèi)別特征,僅支持對(duì)位置點(diǎn)類(lèi)別及其經(jīng)過(guò)順序的限定,不能對(duì)位置點(diǎn)和類(lèi)別進(jìn)行多選等要求.

文獻(xiàn)[14]提出了一種多近似關(guān)鍵詞路徑MAKR(the Multi-Approximate-Keyword Routing)查詢,查詢中不僅定義了起點(diǎn)和終點(diǎn),也定義了一組(關(guān)鍵詞,閾值)鍵值對(duì),旨在搜索從起點(diǎn)到終點(diǎn),至少經(jīng)過(guò)每個(gè)關(guān)鍵詞的一個(gè)空間對(duì)象的最短路徑,且該空間對(duì)象與此關(guān)鍵詞的匹配度需高于指定閾值.關(guān)鍵詞感知的最優(yōu)路徑查詢KOR(Keyword-aware Optimal Route Query)[15-16]綜合考慮了關(guān)鍵詞覆蓋條件、代價(jià)約束和路徑流行度三方面因素,查找從起點(diǎn)到終點(diǎn),經(jīng)過(guò)指定關(guān)鍵詞集合中的點(diǎn)同時(shí)滿足行程預(yù)算且流行度最大的路徑,實(shí)現(xiàn)近似求解.上述針對(duì)關(guān)鍵詞的路徑查詢中,每個(gè)位置點(diǎn)關(guān)聯(lián)一個(gè)或多個(gè)關(guān)鍵詞,本質(zhì)上也可以轉(zhuǎn)化為類(lèi)別信息進(jìn)行處理.不同的是,MAKR和KOR只考慮了需經(jīng)過(guò)的點(diǎn)所屬的關(guān)鍵詞,并沒(méi)有考慮經(jīng)過(guò)的順序限制.而加入關(guān)鍵詞匹配度、路徑流行度等度量標(biāo)準(zhǔn)只適合包含這些特定信息的應(yīng)用場(chǎng)景.

同樣使用正則表達(dá)式的手段定義限制性路徑問(wèn)題,文獻(xiàn)[17]研究了形式化語(yǔ)言限制性最短路徑問(wèn)題.不同于本文考慮對(duì)位置點(diǎn)的限制,文獻(xiàn)[17]考慮的是對(duì)組成路徑的邊的限制,即結(jié)果路徑上邊的標(biāo)簽需滿足正則表達(dá)式.

通過(guò)分析發(fā)現(xiàn)現(xiàn)有研究工作主要集中于類(lèi)別信息,有些沒(méi)有考慮順序限制,有些給出的是問(wèn)題的近似解,有些額外考慮了路徑流行度等因素僅適用于具體場(chǎng)景的應(yīng)用,有些關(guān)注的是對(duì)路徑上邊的限制,還沒(méi)有工作考慮位置點(diǎn)及類(lèi)別的多選需求.本文面向更加通用的限制性路徑規(guī)劃問(wèn)題,全面考慮了位置點(diǎn)和類(lèi)別的經(jīng)過(guò)順序、多選等限制條件,上述問(wèn)題均可轉(zhuǎn)化為本文定義的基于正則表達(dá)式的限制性路徑規(guī)劃問(wèn)題加以解決.

2 問(wèn)題定義

定義1(圖)給定有向圖G(V,E),V代表節(jié)點(diǎn)集,E代表邊集.每個(gè)點(diǎn)v∈V有一個(gè)類(lèi)別信息v.c,每條邊e=(vi,vj)∈E為從vi∈V到vj∈V的有向邊.權(quán)值w(e)取決于使用的度量標(biāo)準(zhǔn),如在最短路徑場(chǎng)景中表示e的長(zhǎng)度,在最短時(shí)間場(chǎng)景中表示經(jīng)過(guò)e所需的時(shí)間.

G為廣義上的圖.當(dāng)G是路網(wǎng)時(shí)可化簡(jiǎn)為僅含有POI的子圖,此時(shí)V是POI點(diǎn)的集合, E是這些POI間最短路徑的集合.

定義2(限制性路徑查詢)限制性路徑查詢q是一個(gè)含有5種元素的正則表達(dá)式:起點(diǎn)、終點(diǎn)、V中位置點(diǎn)的集合、V中位置點(diǎn)類(lèi)別的集合以及操作符·、操作符|、操作符?、操作符+和().①連接操作符·可以省略,表示位置點(diǎn)或類(lèi)別間的順序關(guān)系;②選擇操作符|將可能的選擇劃分開(kāi)來(lái),表示多個(gè)位置點(diǎn)或類(lèi)別任選其一;③Kleene閉包操作符?表示經(jīng)過(guò)其前面的位置點(diǎn)或類(lèi)別零次或多次;④正閉包操作符+表示至少經(jīng)過(guò)其前面的位置點(diǎn)或類(lèi)別一次;⑤圓括號(hào)()定義操作符的范圍和優(yōu)先級(jí).

通過(guò)上述元素的排列組合,限制性路徑查詢可以表達(dá)豐富的限制性路徑規(guī)劃需求.由于可以將一個(gè)位置點(diǎn)視為一個(gè)單獨(dú)的類(lèi)別,因此位置點(diǎn)的處理可以轉(zhuǎn)化為類(lèi)別的處理,下面僅以位置點(diǎn)類(lèi)別為操作對(duì)象介紹限制性路徑查詢及其處理方法.

設(shè)正則表達(dá)式中第一個(gè)點(diǎn)為起點(diǎn)s,最后一個(gè)點(diǎn)為終點(diǎn)t,類(lèi)別集合C={c1,c2,…,cn},則q可以表示從s到t的路徑且:①嚴(yán)格有序經(jīng)過(guò)C通過(guò)sc1c2…cnt;②以任意順序經(jīng)過(guò)C通過(guò)s(c1c2…cn)|(c2c1…cn)|…|(cnc1…c2)t;③經(jīng)過(guò)C中任一個(gè)類(lèi)別通過(guò)sc1|c2|…|cnt;④經(jīng)過(guò)C中任一個(gè)類(lèi)別零次或多次通過(guò)s(c1|c2|…|cn)?t;⑤經(jīng)過(guò)C中任一個(gè)類(lèi)別至少一次通過(guò)s(c1|c2|…|cn)+t;⑥以不同限制條件經(jīng)過(guò)C通過(guò)上述規(guī)則的不同組合.如圖1例子中的限制性路徑查詢可表示為q=work·Restaurant·(C inema|B ar)·home,其中work,home是具體的位置點(diǎn),Restaurant,C inema,B ar代表POI類(lèi)別.

值得注意的是,閉包操作符?和+在實(shí)際最短路徑規(guī)劃中幾乎不會(huì)出現(xiàn).首先是日常生活中人們更傾向于要么經(jīng)過(guò)某個(gè)位置點(diǎn)或類(lèi)別要么不經(jīng)過(guò);其次在不含負(fù)權(quán)的圖中,經(jīng)過(guò)某點(diǎn)多次的路徑勢(shì)必不短于與該路徑其他部分相同而僅經(jīng)過(guò)該點(diǎn)零次或一次的路徑.如果出現(xiàn)上述需求,可以利用下列兩條規(guī)則將含有閉包操作符?和+的查詢化簡(jiǎn):

規(guī)則(1)的含義是某一個(gè)位置點(diǎn)或類(lèi)別出現(xiàn)零次或多次相當(dāng)于對(duì)路徑查詢沒(méi)有影響,可以從查詢中去掉;規(guī)則(2)的含義是某一個(gè)位置點(diǎn)或類(lèi)別出現(xiàn)一次或多次可以根據(jù)最短路徑性質(zhì)化簡(jiǎn)為出現(xiàn)一次.由此下文對(duì)限制性路徑查詢的處理主要考慮其他3種符號(hào)操作.

在傳統(tǒng)正則表達(dá)式和有限自動(dòng)機(jī)理論中,當(dāng)且僅當(dāng)字符串中的每個(gè)字符都在正則表達(dá)式中定義,才會(huì)被該正則表達(dá)式生成的有限自動(dòng)機(jī)接受.如只有“ACFI”或“ACGI”才能通過(guò)AC(F|G)I生成的有限自動(dòng)機(jī),相差一個(gè)字符都是不可接受的.但CRPP中查詢僅包含用戶關(guān)心的位置點(diǎn)或類(lèi)別,且在查詢中列出所有位置點(diǎn)或類(lèi)別也是無(wú)意義和不現(xiàn)實(shí)的.這是將正則表達(dá)式應(yīng)用到CRPP時(shí)的關(guān)鍵問(wèn)題,將在4.1節(jié)陳述解決方法.

定義3(限制性路徑規(guī)劃問(wèn)題)給定一個(gè)有向圖G(V,E)和一條限制性路徑查詢q,限制性路徑規(guī)劃問(wèn)題CRPP(G,q)在圖G中尋找滿足查詢q的最短路徑.

Tom的限制性路徑規(guī)劃問(wèn)題即:在圖1所示的圖中找到滿足q=work·Restaurant· (C inema|B ar)·home的最短路徑.實(shí)際上理想的路徑為長(zhǎng)度為11的A→D→C→F→H.

3 查詢處理框架

針對(duì)上述限制性路徑規(guī)劃問(wèn)題,通過(guò)正則表達(dá)式表達(dá)的限制性路徑查詢,結(jié)合Dijkstra最短路徑算法,本文提出了一個(gè)通用的查詢處理框架.選擇Dijkstra算法的原因在于: Dijkstra算法是最具代表性的求解非負(fù)帶權(quán)圖的最短路徑算法,程序設(shè)計(jì)簡(jiǎn)單,通用性強(qiáng),是現(xiàn)有眾多最短路徑算法的基礎(chǔ),方便擴(kuò)展到其他最短路徑算法上.本框架首先解析查詢q,運(yùn)用Thompson算法將正則表達(dá)式轉(zhuǎn)化為非確定性有限自動(dòng)機(jī)NFA,再用子集構(gòu)造法將NFA確定化為確定性有限自動(dòng)機(jī)DFA,然后將DFA最小化,最后將解析結(jié)果DFA與G一起作為限制性路徑規(guī)劃算法的輸入,通過(guò)一個(gè)類(lèi)Dijkstra算法來(lái)計(jì)算G中滿足q的最短路徑.

NFA和DFA都用狀態(tài)轉(zhuǎn)移表表示,給定狀態(tài)和類(lèi)別,轉(zhuǎn)移的結(jié)果為狀態(tài)轉(zhuǎn)移表中(狀態(tài),類(lèi)別)的值,即下一個(gè)狀態(tài);如果表中不存在對(duì)應(yīng)的項(xiàng),該類(lèi)別就不是針對(duì)當(dāng)前狀態(tài)的一個(gè)可轉(zhuǎn)移類(lèi)別.對(duì)查詢q=work·Restaurant·(C inema|B ar)·home而言,解析后的DFA可以表示為圖2的狀態(tài)轉(zhuǎn)移表或圖3的狀態(tài)轉(zhuǎn)移圖.圖3中圓圈表示狀態(tài),初始狀態(tài)冠以“?”,雙圈表示終結(jié)狀態(tài),箭弧表示狀態(tài)轉(zhuǎn)移的方向,弧上的標(biāo)記表示該狀態(tài)轉(zhuǎn)移的輸入.

圖2 示例查詢解析后的狀態(tài)轉(zhuǎn)移表Fig.2 The state transition table

圖3 示例查詢解析后的狀態(tài)轉(zhuǎn)移圖Fig.3 The state transition diagram

因此可以通過(guò)狀態(tài)轉(zhuǎn)移表來(lái)檢查路徑是否符合限制性條件:當(dāng)且僅當(dāng)以該路徑上點(diǎn)的順序可以驅(qū)動(dòng)有限自動(dòng)機(jī)從初始狀態(tài)到接受狀態(tài),即終結(jié)狀態(tài),那么這條路徑是符合限制性路徑查詢的路徑.

4 限制性路徑規(guī)劃算法

在上節(jié)提出的查詢處理框架的基礎(chǔ)上,本節(jié)介紹限制性路徑規(guī)劃算法,包括基本算法BCRP和它的改進(jìn)算法ICRP.

4.1 基本的限制性路徑規(guī)劃算法BCRP

BCRP算法以類(lèi)Dijkstra算法為主線來(lái)尋找最短路徑,同時(shí)用限制性路徑查詢解析后的狀態(tài)轉(zhuǎn)移表過(guò)濾不符合限制條件的路徑.不直接使用Dijkstra算法的原因在于:Dijkstra算法中被標(biāo)記為訪問(wèn)過(guò)的點(diǎn)不會(huì)在后續(xù)過(guò)程中被擴(kuò)展,因?yàn)楸粯?biāo)記時(shí)對(duì)應(yīng)的路徑一定是從s到該點(diǎn)的最短路徑.而在CRPP中,兩點(diǎn)間的最短路徑不一定是符合限制條件的路徑,即Dijkstra算法不足以解決CRPP.因此在更新s到某點(diǎn)的距離時(shí),也應(yīng)將其他可達(dá)路徑保存,這樣所有可能成為符合限制條件最短路徑的路徑都會(huì)被考慮在內(nèi).對(duì)此本文提出的類(lèi)Dijkstra算法為:首先設(shè)置s為當(dāng)前點(diǎn)并標(biāo)記,接著更新所有標(biāo)記點(diǎn)的直接可達(dá)點(diǎn)到s的距離并保存其路徑,持續(xù)選取目前擁有最短距離的點(diǎn)為當(dāng)前點(diǎn)并標(biāo)記,直到到達(dá)狀態(tài)轉(zhuǎn)移表的終結(jié)狀態(tài),此時(shí)對(duì)應(yīng)的路徑即是符合限制性條件的最短路徑.

在定義2中已經(jīng)提到,傳統(tǒng)的正則表達(dá)式是字符串的完全匹配,而CRPP中查詢只包含用戶關(guān)心的位置點(diǎn)或類(lèi)別,因而是一種部分匹配.對(duì)此,定義一個(gè)額外的任意狀態(tài)arb,表示不在狀態(tài)轉(zhuǎn)移表中的一個(gè)不關(guān)心的狀態(tài);且為每條路徑的狀態(tài)轉(zhuǎn)移增加nowstate和paststate兩個(gè)屬性,nowstate表示擴(kuò)展過(guò)程中的當(dāng)前狀態(tài),paststate表示上一個(gè)非任意狀態(tài).對(duì)于恰好滿足當(dāng)前狀態(tài)轉(zhuǎn)移條件的點(diǎn),直接按照狀態(tài)轉(zhuǎn)移表進(jìn)行轉(zhuǎn)移;對(duì)于其類(lèi)別不在當(dāng)前狀態(tài)轉(zhuǎn)移條件中的點(diǎn),由于其后節(jié)點(diǎn)有可能滿足狀態(tài)轉(zhuǎn)移條件,因此先將其nowstate標(biāo)記為arb.當(dāng)擴(kuò)展nowstate為arb的路徑時(shí),根據(jù)其paststate屬性進(jìn)行轉(zhuǎn)移.

為了更好地實(shí)現(xiàn)上述方法,使用最短路徑長(zhǎng)度增序的優(yōu)先級(jí)隊(duì)列h來(lái)存儲(chǔ)s到各點(diǎn)的路徑. h中每個(gè)元素是一個(gè)五元組item(vnode,path,mindist,nowstate,paststate),vnode代表當(dāng)前節(jié)點(diǎn),path和mindist分別是s到vnode的路徑及長(zhǎng)度.算法1展示了BCRP(G,T)算法:先從起點(diǎn)s開(kāi)始擴(kuò)展,只要h非空,就不斷取出隊(duì)首元素,直到其nowstate到達(dá)終結(jié)狀態(tài),這時(shí)隊(duì)首元素代表的路徑即為符合正則表達(dá)式的最短路徑.其中,通過(guò)調(diào)用算法2 BCRPGetlinks(G,T,h,itemi)擴(kuò)展當(dāng)前點(diǎn)的所有連接點(diǎn)并將它們加入到h中,算法3 SetItemState(T,linknode,itemi,itemk)根據(jù)上述規(guī)則設(shè)置新擴(kuò)展元素的轉(zhuǎn)移狀態(tài).

BCRP算法的執(zhí)行過(guò)程可以通過(guò)優(yōu)先級(jí)隊(duì)列的變化過(guò)程表示.圖4為BCRP算法針對(duì)圖1所示的限制性路徑規(guī)劃問(wèn)題的前五步執(zhí)行過(guò)程(深色元素表示此時(shí)的最短路徑,需在下一步被擴(kuò)展).實(shí)際上BCRP相當(dāng)于持續(xù)找下一條s到t的最短路徑然后檢查其是否符合限制要求,直到當(dāng)前最短路徑是符合條件的,故結(jié)果的正確性是顯而易見(jiàn)的,但也因此十分低效.下節(jié)介紹的ICRP算法主要針對(duì)此問(wèn)題,通過(guò)加入剪枝策略進(jìn)行改進(jìn).

圖4 圖1中例子的BCRP算法執(zhí)行過(guò)程Fig.4 BCRP algorithm execution process of the example in Fig.1

4.2 改進(jìn)的限制性路徑規(guī)劃算法ICRP

通過(guò)分析發(fā)現(xiàn)在BCRP運(yùn)行過(guò)程中有大量的冗余項(xiàng),即隊(duì)列中已存在比該項(xiàng)更優(yōu)的項(xiàng)被加入優(yōu)先級(jí)隊(duì)列.這不僅是對(duì)內(nèi)存和計(jì)算資源的浪費(fèi),更重要的是在后續(xù)的步驟中冗余項(xiàng)可能被擴(kuò)展,將導(dǎo)致持續(xù)的不必要的計(jì)算.如在圖4的第4步,當(dāng)考慮加入itemj(C,A→D→C,6,4,3)時(shí),隊(duì)列中已經(jīng)存在了一個(gè)關(guān)于點(diǎn)C的項(xiàng)itemi(C,A→B→C,9,4,3),兩項(xiàng)的nowstate和paststate屬性均相同意味著滿足相同的限制條件,而itemi的路徑長(zhǎng)度更長(zhǎng),故itemi是一個(gè)冗余項(xiàng).基于上述觀察,設(shè)計(jì)了以下兩種剪枝策略.

剪枝策略當(dāng)考慮同一點(diǎn)v的兩條路徑(即優(yōu)先級(jí)隊(duì)列中的兩項(xiàng))itemi和itemj時(shí):

(1)如果itemi.nowstate=itemj.nowstate/=arb,更長(zhǎng)的候選路徑應(yīng)該被剪枝;

(2)如果itemi.nowstate=itemj.nowstate=arb且itemi.paststate=itemj.paststate,更長(zhǎng)的候選路徑應(yīng)該被剪枝.

證明:由于兩條路徑的當(dāng)前擴(kuò)展結(jié)點(diǎn)均為v,假設(shè)itemj.mindist＜itemi.mindist,從s到t符合條件的最短路徑為itemi.path+P ath(v,t),P ath(v,t)代表從v到t的路徑(這里+表示路徑的連接),即可以通過(guò)P ath(v,t)從itemi.nowstate(當(dāng)itemi.nowstate/=arb時(shí))或itemi.paststate(當(dāng)itemi.nowstate=arb時(shí))到達(dá)endS tate.又由于兩條路徑處于相同的狀態(tài)(當(dāng)nowstate/=arb時(shí)為nowstate,否則為paststate),故itemj也可以通過(guò)P ath(v,t)到達(dá)endS tate,即itemj.path+P ath(v,t)也符合限制性條件.由于itemj.mindist＜itemi.mindist,那么itemj.path+P ath(v,t)比itemi.path+P ath(v,t)短,與條件沖突.即如果itemj.path+ P ath(v,t)不是符合限制性條件的最短路徑,itemi.path+P ath(v,t)也不可能是.因此itemj總是比itemi更優(yōu),將itemi剪枝不會(huì)影響算法的正確性.

為實(shí)現(xiàn)上述剪枝策略,除為所有點(diǎn)維護(hù)一個(gè)全局優(yōu)先隊(duì)列h外,還為每個(gè)點(diǎn)v設(shè)計(jì)一個(gè)以最短路徑長(zhǎng)度增序的局部?jī)?yōu)先級(jí)隊(duì)列ownheap來(lái)存儲(chǔ)所有s到v的路徑.全局優(yōu)先隊(duì)列中僅需存儲(chǔ)處理中的節(jié)點(diǎn),每次取當(dāng)前最短路徑即為從全局隊(duì)列中取出隊(duì)首節(jié)點(diǎn)的隊(duì)首元素.算法4展示了ICRP算法的處理流程,與BCRP類(lèi)似,ICRP也從s點(diǎn)開(kāi)始擴(kuò)展,持續(xù)取全局優(yōu)先級(jí)隊(duì)列隊(duì)首元素直到其到達(dá)終結(jié)狀態(tài),此時(shí)對(duì)應(yīng)的路徑即為符合條件的最優(yōu)路徑.如果h為空則不存在符合條件的路徑,否則將通過(guò)算法5中的ICRPGetlinks(G,T,h,nodei,itemi)擴(kuò)展隊(duì)首元素,擴(kuò)展過(guò)程中會(huì)根據(jù)剪枝規(guī)則判斷新的擴(kuò)展路徑是否是冗余項(xiàng),只有非冗余項(xiàng)才會(huì)保留在該節(jié)點(diǎn)自己的局部?jī)?yōu)先級(jí)隊(duì)列中.

同樣針對(duì)圖1中的例子,圖5展示了ICRP算法運(yùn)行過(guò)程的前五步.通過(guò)比較ICRP和BCRP的部分運(yùn)行過(guò)程,可以發(fā)現(xiàn)冗余項(xiàng)被排除.由于BCRP的正確性是顯而易見(jiàn)的,ICRP通過(guò)使用剪枝策略減少了搜索空間,只會(huì)提升算法效率而不會(huì)破壞算法的正確性,因此ICRP的正確性也被證明.

圖5 圖1中例子的ICRP算法執(zhí)行過(guò)程Fig.5 ICRP algorithm execution process of the example in Fig.1

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

本節(jié)使用真實(shí)的路網(wǎng)數(shù)據(jù)進(jìn)行實(shí)驗(yàn).所有算法均由Java語(yǔ)言編程實(shí)現(xiàn)且運(yùn)行在處理器為Intel Core i5-4460 3.20 GHz,內(nèi)存16 G,Windows操作系統(tǒng)的PC機(jī)上.

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

數(shù)據(jù)集使用California真實(shí)路網(wǎng)數(shù)據(jù)[7](21 048個(gè)點(diǎn),21 693條邊),為每個(gè)點(diǎn)隨機(jī)分配一個(gè)正整數(shù)c(0≤c≤19)代表其所屬類(lèi)別,并隨機(jī)抽取部分節(jié)點(diǎn)及它們相關(guān)的邊生成原圖不同的子圖(節(jié)點(diǎn)數(shù)目num)來(lái)考察圖規(guī)模對(duì)算法的影響以及算法在不同結(jié)構(gòu)圖上的適用性.

查詢?yōu)椴皇Р樵兊囊话阈?設(shè)q的形式化格式為s(c1|c2|…|ck)1()2…()j?1t,其中,s,t分別代表起點(diǎn)和終點(diǎn);連接運(yùn)算符分隔開(kāi)多個(gè)括號(hào),表示需依順序經(jīng)過(guò)的多個(gè)類(lèi)別;每個(gè)括號(hào)中多個(gè)以選擇運(yùn)算符隔開(kāi)的類(lèi)別表示選其一.假設(shè)每條查詢有j個(gè)需要順序連接的類(lèi)別,每個(gè)類(lèi)別有k種選擇(j,k均為正整數(shù)).實(shí)驗(yàn)首先使用默認(rèn)參數(shù),通過(guò)隨機(jī)選擇s,t和類(lèi)別來(lái)生成20條基本查詢,接著通過(guò)調(diào)整參數(shù)j,k生成新的隨機(jī)查詢,最大限度地保證變量唯一性.

表1詳細(xì)展示了實(shí)驗(yàn)的具體設(shè)置,非特殊說(shuō)明都采用默認(rèn)值.

表1 實(shí)驗(yàn)設(shè)置Tab.1 Settings of experiments

5.2 實(shí)驗(yàn)結(jié)果

由于第4節(jié)中已經(jīng)證明了算法的正確性,因此在實(shí)驗(yàn)階段主要關(guān)注算法的有效性,體現(xiàn)在查詢響應(yīng)時(shí)間和擴(kuò)展結(jié)點(diǎn)數(shù)目?jī)蓚€(gè)方面.查詢響應(yīng)時(shí)間代表算法的處理效率,擴(kuò)展結(jié)點(diǎn)數(shù)目表示有多少可能的路徑被驗(yàn)證,代表查詢空間的規(guī)模.由于據(jù)我們所知尚沒(méi)有相關(guān)工作解決與我們定義相同的限制性路徑規(guī)劃問(wèn)題,因此本文主要對(duì)BCRP和ICRP算法進(jìn)行對(duì)比實(shí)驗(yàn)來(lái)考察剪枝策略對(duì)算法有效性和性能的影響.

圖G對(duì)算法的影響通過(guò)抽取子圖中點(diǎn)的數(shù)目num來(lái)考察G的結(jié)構(gòu)和規(guī)模對(duì)算法的影響.圖6(a)和7(a)展示了隨著圖中點(diǎn)數(shù)目的增多,算法的搜索空間和處理時(shí)間也隨之增加,這是由于大圖中兩點(diǎn)之間最短路徑中點(diǎn)的個(gè)數(shù)普遍多于小圖.同時(shí)當(dāng)圖規(guī)模增大時(shí),BCRP和ICRP間的性能差異也越來(lái)越大,這是由于擴(kuò)展階段連接點(diǎn)的數(shù)目持續(xù)增加,ICRP對(duì)不符合條件的路徑進(jìn)行剪枝,而B(niǎo)CRP中不符合條件的路徑會(huì)被持續(xù)擴(kuò)展,帶來(lái)了大量無(wú)用計(jì)算.

限制性路徑查詢q對(duì)算法的影響q對(duì)算法的影響主要體現(xiàn)在查詢的復(fù)雜性上,即限制條件的多少.實(shí)驗(yàn)主要考慮q中順序經(jīng)過(guò)類(lèi)別數(shù)目j和每個(gè)類(lèi)別可能的選擇數(shù)目k這兩個(gè)方面.圖6(b)、7(b)和6(c)、7(c)分別展示了j和k對(duì)算法的影響.可以直觀地看到,隨著j和k的增加,算法的性能有一定下降.對(duì)于j而言,數(shù)目越多表示路徑需要經(jīng)過(guò)的類(lèi)別越多,那么算法需要檢查限制條件的滿足情況而進(jìn)行的計(jì)算也隨之增多;對(duì)于k而言,每個(gè)類(lèi)別的選擇越多意味著需要考慮更多的可能路徑.

BCRP和ICRP算法的有效性分析假設(shè)運(yùn)行時(shí)間超過(guò)3 min就是不可接受的,在實(shí)驗(yàn)過(guò)程中發(fā)現(xiàn),只有在較小的圖上進(jìn)行較簡(jiǎn)單的查詢時(shí)BCRP算法才可以運(yùn)行出可以接受的結(jié)果,如當(dāng)num為5 k時(shí),BCRP算法尚能獲得較好的性能,但是增加到10 k時(shí),查詢的不可接受率幾乎達(dá)到50%,15 k時(shí)超過(guò)70%,當(dāng)q中限制性條件增加時(shí)也出現(xiàn)了相同的情況.對(duì)比ICRP算法,查詢的不可接受率為0.由上述實(shí)驗(yàn)結(jié)果可以看出,在所有情況中ICRP算法的性能都優(yōu)于BCRP,且隨著圖規(guī)模的增大和限制條件的增多,ICRP的性能下降相比BCRP十分緩慢.以上結(jié)果均表明了剪枝策略的有效性.

圖6 采用不同num,j,k時(shí)的平均響應(yīng)時(shí)間Fig.6 Average response time when varying num,j and k

圖7 采用不同num,j,k時(shí)的平均擴(kuò)展節(jié)點(diǎn)數(shù)目Fig.7 Average number of expanded nodes when varying num,j and k

6 總結(jié)與展望

本文研究了限制性路徑規(guī)劃問(wèn)題CRPP,首先通過(guò)利用正則表達(dá)式表示限制性路徑查詢的方式形式化定義了該問(wèn)題,接著設(shè)計(jì)了一種解決的通用型框架,然后提出了基本的限制性路徑規(guī)劃算法BCRP,并在此基礎(chǔ)上引入剪枝策略減少冗余路徑和計(jì)算代價(jià),最后通過(guò)大量的實(shí)驗(yàn)分析表明本文的方法是可行且高效的.未來(lái)的工作主要包括提升現(xiàn)有算法在大規(guī)模圖中的適用性.

[1]LIU H,JIN C,ZHOU A.Popular route planning with travel cost estimation[C]//Proceedings,Part II,of the 21st International Conference on Database Systems for Advanced Applications.New York:Springer-Verlag, 2016,9643:403-418.

[2]YUAN J,ZHENG Y,ZHANG C,et al.T-drive:Driving directions based on taxi trajectories[C]//Sigspatial International Conference on Advances in Geographic Information Systems.New York:ACM,2010:99-108.

[3]ZHENG Y,CAPRA L,WOLFSON O,et al.Urban computing:Concepts,methodologies,and applications[J]. ACM Transactions on Intelligent Systems and Technology,2014,5(3):38.

[4]ZHANG S,QIN L,ZHENG Y,et al.Ef f ective and effi cient:Large-scale dynamic city express[J].IEEE Transactions on Knowledge&Data Engineering,2016,28(12):3203-3217.

[5]LU H C,LIN C Y,TSENG V S.Trip-Mine:An effi cient trip planning approach with travel time constraints [C]//IEEE International Conference on Mobile Data Management.[S.l.]:IEEE,2011:152-161.

[6]MALVIYA N,MADDEN S,BHATTACHARYA A.A continuous query system for dynamic route planning[C]// IEEE,International Conference on Data Engineering.[S.l.]:IEEE Computer Society,2011:792-803.

[7]LI F,CHENG D,HADJIELEFTHERIOU M,et al.On trip planning queries in spatial databases[J].Journal of Combinatorial Optimization,2005,31(1):1-16.

[8]SHARIFZADEH M,KOLAHDOUZAN M,SHAHABI C.The optimal sequenced route query[J].The VLDB Journal,2008,17(4):765-787.

[9]SHARIFZADEH M,SHAHABI C.Additively weighted voronoi diagrams for optimal sequenced route queries [J].Workshop on Spatio-Temporal Database Management,2006.

[10]SHARIFZADEH M,SHAHABI C.Processing optimal sequenced route queries using voronoi diagrams[J].Geoinformatica,2008,12(4):411-433.

[11]RICE M N,TSOTRAS V J.Engineering generalized shortest path queries[C]//IEEE International Conference on Data Engineering.[S.l.]:IEEE Computer Society,2013:949-960.

[12]CHEN H,KU W S,SUN M T,et al.The multi-rule partial sequenced route query[C]//ACM Sigspatial International Symposium on Advances in Geographic Information Systems.USA:DBLP,2008:1-10.

[13]LI J,YANG Y,MAMOULIS N.Optimal route queries with arbitrary order constraints[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(5):1097-1110.

[14]YAO B,TANG M,LI F.Multi-approximate-keyword routing in GIS data[C]//ACM Sigspatial International Conference on Advances in Geographic Information Systems.New York:ACM,2011:201-210.

[15]CAO X,CHEN L,CONG G,et al.Keyword-aware optimal route search[J].Proceedings of the VLDB Endowment,2012,5(11):1136-1147.

[16]CAO X,CHEN L,CONG G,et al.KORS:Keyword-aware optimal route search system[C]//IEEE,International Conference on Data Engineering.[S.l.]:IEEE,2013:1340-1343.

[17]BARRETT C,JACOB R,MARATHE M.Formal language constrained path problems[J].Computing,1998, 30(3):234-245.

(責(zé)任編輯:張晶)

Constrained route planning based on the regular expression

WANG Jing,LIU Hui-ping,JIN Che-qing
(School of Computer Science and Software Engineering, East China Normal University,Shanghai 200062,China)

Traditional route planning algorithms,which mainly focus on metrics such as the distance,time,cost,etc.to fi nd the optimal route from source to destination,are not suitable for solving route planning requirements with location constraints.For example, finding the shortest path passing the whole or a part of user-de fi ned location categories in order or disorder.Mainly focusing on these scenarios,this paper formalizes the constrained route planning problem on the basis of the regular expression generated by user requirements and gives a general framework to solve this problem.Based on this,a basic constrained route planning algorithm(BCRP)and an improved constrained route planning algorithm(ICRP)are proposed while ICRP reduces the search space using pruning rules. Finally,extensive experiments on real road network datasets demonstrate the effi ciency of our proposal.

constrained route planning;the regular expression;the shortest path

TP391

A

10.3969/j.issn.1000-5641.2017.05.015

1000-5641(2017)05-0162-12

2017-06-20

國(guó)家重點(diǎn)研發(fā)計(jì)劃重點(diǎn)專(zhuān)項(xiàng)(973)(2016YFB1000905);國(guó)家自然科學(xué)基金(61370101, 61532021,U1501252,U1401256,61402180)

王婧,女,碩士研究生,研究方向?yàn)榛谖恢玫姆?wù).E-mail:jingwang@stu.ecnu.edu.cn.

金澈清,男,博士生導(dǎo)師,研究方向?yàn)榛谖恢玫姆?wù).E-mail:cqjin@sei.ecnu.edu.cn.