關(guān)鍵詞最優(yōu)路徑查詢的分段拓展算法
2022-06-16 05:24:18劉蒙蒙牛保寧
計(jì)算機(jī)工程 2022年6期
劉蒙蒙，牛保寧，楊 茸
（太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院，山西晉中 030600）
0 概述
隨著人們對旅游路線需求的多樣化，路徑查詢不只是常見的最短路徑查詢，人們通常會綜合考慮路徑時間開銷、路徑覆蓋的興趣點(diǎn)等其他因素［1-3］?？紤]如下的場景：當(dāng)用戶想要去某些地方旅游時，希望找到一條從指定地點(diǎn)出發(fā)，途經(jīng)滿足用戶指定的興趣點(diǎn)，最后到達(dá)終點(diǎn)的路徑，該路徑在滿足游客的行程預(yù)算（以下稱為代價閾值）的前提下，所用時間越短越好。
關(guān)鍵詞最優(yōu)路徑查詢［3-4］（Keyword-aware Optimal Route query，KOR）是一種在滿足關(guān)鍵詞全覆蓋、路徑代價閾值約束下，路徑時間開銷最小的路徑查詢類型，常用于旅行規(guī)劃。KOR 求解的途徑是路徑拓展，現(xiàn)有求解算法本質(zhì)上都是廣度優(yōu)先搜索——搜索規(guī)模隨搜索深度指數(shù)級增加?？s小搜索規(guī)模主要的優(yōu)化策略有近似支配剪枝［3］、可行解目標(biāo)值剪枝［3］、關(guān)鍵詞頂點(diǎn)拓展［5］、全局優(yōu)先拓展［3］和最小代價剪枝［6］。這些優(yōu)化策略在搜索深度淺的情況下是有效的，但是在搜索路徑長或搜索深度較深的情況下搜索規(guī)模仍然難以控制。因此，避免長路徑拓展過程中搜索深度過深是解決這一問題的關(guān)鍵。
受人類在規(guī)劃長路線時先選取必須要經(jīng)過的數(shù)個重要地點(diǎn)，然后分別針對各段路徑進(jìn)行規(guī)劃的啟發(fā)，本文提出一種關(guān)鍵詞最優(yōu)路徑查詢的分段拓展算法（SE-KOR），SE-KOR 根據(jù)<關(guān)鍵詞：頂點(diǎn)>的關(guān)鍵詞倒排索引表，構(gòu)建｛起點(diǎn)→關(guān)鍵詞頂點(diǎn)1→……→關(guān)鍵詞頂點(diǎn)n→終點(diǎn)｝的關(guān)鍵詞頂點(diǎn)路徑，將路徑分割為以關(guān)鍵詞頂點(diǎn)為邊界點(diǎn)的多段路徑，并分別拓展，降低搜索深度，以避免搜索規(guī)模爆炸的問題。最終將各段路徑拼接成完整的路徑。
1 相關(guān)工作
路徑拓展算法分為啟發(fā)式搜索和廣度優(yōu)先搜索。啟發(fā)式搜索代表算法KDR［7］和Greedy［3］通過得分函數(shù)僅對關(guān)鍵詞覆蓋的頂點(diǎn)拓展，具有較高的執(zhí)行效率，但返回結(jié)果本質(zhì)上是關(guān)鍵詞頂點(diǎn)的最優(yōu)排序，不是具體路徑。廣度優(yōu)先搜索代表算法KSRG［5］僅對關(guān)鍵詞頂點(diǎn)拓展，具有較高的執(zhí)行效率，但返回結(jié)果依舊是最優(yōu)關(guān)鍵詞頂點(diǎn)序列，在后續(xù)優(yōu)化中，KSRG［6］利用Skyline 路徑實(shí)現(xiàn)具體路徑查詢，但預(yù)處理工作獲取Skyline 路徑的時空開銷巨大；KORL［6］利用樹形索引將大圖分而治之并在預(yù)處理中求取Skyline 路徑，在拓展階段需要對壓縮圖進(jìn)行復(fù)原計(jì)算，產(chǎn)生大量中間拓展操作；OSScalling［3］、BucketBound［3］進(jìn)行鄰邊拓展，在面臨長路徑搜索時，易出現(xiàn)搜索規(guī)模過大而耗時較長的問題。
在剪枝策略方面，現(xiàn)有策略主要有支配、近似支配、可行解目標(biāo)值、全局優(yōu)先拓展、關(guān)鍵詞頂點(diǎn)拓展和最小代價剪枝。OSScalling［3］、BucketBound［3］運(yùn)用支配、可行解目標(biāo)值和全局優(yōu)先拓展對中間路徑剪枝。KSRG［5］提出關(guān)鍵詞頂點(diǎn)拓展，跳過與關(guān)鍵詞不相關(guān)的節(jié)點(diǎn)并利用近似支配剪枝。KORL［8］提出最小代價剪枝，剪去不滿足代價閾值的中間路徑，但現(xiàn)有剪枝策略不控制路徑拓展方向。
除上述KOR 算法外，其他關(guān)鍵詞的查詢也得到廣泛研究?；陉P(guān)鍵詞的最優(yōu)位置查詢［9-11］查找關(guān)鍵詞全覆蓋下距離各點(diǎn)最近的位置，空間組關(guān)鍵詞查詢［12-14］檢索最接近查詢位置且頂點(diǎn)間距離最短的關(guān)鍵詞頂點(diǎn)序列。室內(nèi)關(guān)鍵詞感知路徑規(guī)劃［15-16］研究復(fù)雜室內(nèi)場景下的關(guān)鍵詞覆蓋路徑查詢問題。多用戶空間關(guān)鍵詞［17-18］路線查詢針對多用戶查找關(guān)鍵詞全覆蓋、代價最小的路徑，對多用戶場景下的KOR 具有啟發(fā)意義，但以上算法不適用于KOR問題。
為解決路徑拓展不具體和長路徑搜索耗時長的問題，本文提出關(guān)鍵詞最優(yōu)路徑查詢的分段拓展算法（SE-KOR），構(gòu)建關(guān)鍵詞頂點(diǎn)路徑作為路徑邊界，將路徑劃分為多段分別拓展，并且采用局部代價閾值剪枝，保證路徑拓展沿關(guān)鍵詞頂點(diǎn)路徑方向。本文算法的創(chuàng)新點(diǎn)如下：
1）針對廣度優(yōu)先搜索方式遍歷頂點(diǎn)、查找興趣點(diǎn)耗時長的問題，提出一種基于關(guān)鍵詞倒排索引表構(gòu)建關(guān)鍵詞頂點(diǎn)路徑的方法；以關(guān)鍵詞頂點(diǎn)為邊界點(diǎn)，把該路徑分為多段并分段拓展，降低搜索深度，從而降低搜索規(guī)模，縮短執(zhí)行時間。
2）針對現(xiàn)有剪枝策略不控制路徑拓展方向的問題，本文提出局部代價剪枝，控制路徑的走向沿著關(guān)鍵詞頂點(diǎn)路徑的方向拓展，并綜合利用近似支配剪枝、可行解目標(biāo)值剪枝和全局優(yōu)先拓展，加速拓展過程。
2 KOR 及其求解框架
求解KOR 是一個NP-hard 問題［3］，約束條件分別為關(guān)鍵詞全覆蓋、滿足代價閾值以及目標(biāo)值最優(yōu)化。本節(jié)給出KOR 定義，介紹KOR 求解框架。
2.1 符號說明
為方便閱讀，首先給出常用符號的說明，如表1所示。
表1 符號說明表Table 1 Symbol description table
2.2 問題定義
關(guān)鍵詞最優(yōu)路徑查詢主要基于路網(wǎng)，路網(wǎng)可以抽象成如圖1 所示的查詢圖。
圖1 查詢圖結(jié)構(gòu)Fig.1 Query graph structure
定義1（查詢圖）［3］G=(V，E)由頂點(diǎn)集V和邊集E構(gòu)成。任意v∈V表示興趣點(diǎn)，v的地理位置用經(jīng)緯度表示，記為v.loc，v的關(guān)鍵詞集合表示為v.φ={v.w1，v.w2，…}。連接鄰接點(diǎn)vi和vj的路徑(vi，vj)稱為邊，記為e，e∈E。每條邊有兩個屬性：代價值b(vi，vj)和目標(biāo)值o(vi，vj)。
如圖1 所示，通常代價值表示邊的長度，用括號外的數(shù)值表示；目標(biāo)值表示經(jīng)過邊所需要的時間，用括號內(nèi)的數(shù)值表示。表2 列出圖1 中各頂點(diǎn)對應(yīng)的關(guān)鍵詞集合［5］。
表2 頂點(diǎn)關(guān)鍵詞信息Table 2 Vertex keywords information
定義2（路徑）p=(v0，v1，…，vn)表示一條從v0出發(fā)，經(jīng)過v1，v2，…，vn-1，到達(dá)vn的路徑，p覆蓋的關(guān)鍵詞表示為p.φ=。
根據(jù)定義2，路徑p的代價值和目標(biāo)值分別為：。
定義3（KOR）一個KOR 查詢Q是一個四元組Q=(vs，vt，φ，Δ)，vs、vt、φ和Δ 分別表示路徑起點(diǎn)、終點(diǎn)、覆蓋的關(guān)鍵詞集合和代價閾值。用ps，t表示從vs到vt的路徑集合，pcand表示滿足關(guān)鍵詞全覆蓋和代價閾值的可行路徑p的集合，即pcand={p|p∈ps，t∩p.φ?Q.φ∩b(p)≤Δ}，則KOR的最優(yōu)路徑popt=。
2.3 KOR 求解框架
現(xiàn)有KOR 求解方法的核心是路徑拓展，以降低路徑拓展代價為目標(biāo)，組合運(yùn)用多種剪枝策略，預(yù)先計(jì)算剪枝時的代價值和目標(biāo)值。KOR 的求解框架如圖2 所示，包括預(yù)處理和路徑拓展兩部分。預(yù)處理部分預(yù)先計(jì)算路徑拓展過程中用到的路網(wǎng)中任意兩個頂點(diǎn)間的最小代價值和最小目標(biāo)值，避免不同KOR 的重復(fù)計(jì)算；在路網(wǎng)更新時同步更新。路徑拓展部分綜合運(yùn)用多種剪枝策略，盡可能地降低拓展代價。剪枝策略分為路徑剪枝和可行解剪枝兩方面。路徑剪枝包括支配剪枝、目標(biāo)修正的近似支配剪枝、全局優(yōu)先拓展剪枝等。這些剪枝策略可以單獨(dú)或組合運(yùn)用，以低的代價得到可行解集合。然后利用可行解剪枝中的可行解目標(biāo)值剪枝獲取最優(yōu)解。
圖2 KOR 求解框架Fig.2 KOR solution framework
KOR 的求解過程主要是路徑拓展的過程。為方便描述路徑拓展過程，下面先給出路徑標(biāo)簽和標(biāo)簽操作的定義。
定義4（路徑標(biāo)簽）對任意從vs拓展至vi的路徑p，在頂點(diǎn)vi處構(gòu)建路徑標(biāo)簽，4 個 參數(shù)分別代表路徑p覆蓋的關(guān)鍵詞集合、修正目標(biāo)值、目標(biāo)值和代價值。路徑標(biāo)簽簡稱標(biāo)簽。
定義5（標(biāo)簽操作）由頂點(diǎn)vi的標(biāo)簽向它的鄰接頂點(diǎn)vj拓展生成新標(biāo)簽。新標(biāo)簽根據(jù)的當(dāng)前頂點(diǎn)vi到頂點(diǎn)vj的o、b構(gòu)建，滿足以下條件：
KOR 求解過程如下：
1）從起點(diǎn)開始鄰邊拓展，對于拓展到新的頂點(diǎn)，記錄從起點(diǎn)到該頂點(diǎn)的一個標(biāo)簽，如中包括已經(jīng)包含的關(guān)鍵詞、修正目標(biāo)值、o、b，并計(jì)算該標(biāo)簽的全局優(yōu)先度，優(yōu)先度越小，優(yōu)先級別越高，然后入隊(duì)。
2）根據(jù)全局優(yōu)先拓展策略，選擇優(yōu)先級最高的路徑標(biāo)簽出隊(duì)，向下一個頂點(diǎn)拓展。
3）根據(jù)支配剪枝或者近似支配剪枝策略，判斷當(dāng)前路徑是否被支配，若被支配則舍棄，繼續(xù)下一輪拓展，否則入隊(duì)。
4）如果當(dāng)前路徑滿足關(guān)鍵詞全覆蓋和代價閾值，若此時可行解集合中為空，當(dāng)前標(biāo)簽進(jìn)入可行解集合，否則與現(xiàn)有可行解對比，保留目標(biāo)值最小的可行解，即可行解目標(biāo)值剪枝。
5）以此類推，直到優(yōu)先隊(duì)列中所有標(biāo)簽為空，返回一個目標(biāo)值最小的可行解作為最優(yōu)解。
兩個部分相關(guān)定義及定理如下：
1）預(yù)處理
預(yù)處理階段包括兩部分：（1）利用Floyd［19］算法，計(jì)算查詢圖中任意兩頂點(diǎn)間的最小代價值b(vi，vj)及最小代價值對應(yīng)的目標(biāo)值oσ(vi，vj)和最小目標(biāo)值o(vi，vj)及最小目標(biāo)值對應(yīng)的代價值bτ(vi，vj)，同時記錄G=(V，E)中的最小代價值bmin和最小目標(biāo)值omin，并保存在內(nèi)存中；（2）關(guān)鍵詞倒排索引［20］構(gòu)建，將興趣點(diǎn)的所有關(guān)鍵詞信息{v.w1，v.w2，…}組合成非重合的關(guān)鍵詞集合，構(gòu)建關(guān)鍵詞倒排索引表，記錄關(guān)鍵詞對應(yīng)的興趣點(diǎn)，如表3 所示。
表3 關(guān)鍵詞倒排索引表Table 3 Keyword inverted index table
2）路徑拓展策略
本文算法基于上述算法框架，用到的拓展策略有目標(biāo)修正的近似支配剪枝和全局優(yōu)先拓展剪枝。
定義6（目標(biāo)修正）給定查詢圖G=(V，E)和查詢Q=(vs，vt，φ，Δ)，已知標(biāo)簽，最小代價值bmin，最小目標(biāo)值omin，其修正目標(biāo)值為被稱為修正比例，其中0<ε<1。
修正目標(biāo)值用于近似支配剪枝。
定理1每個頂點(diǎn)最多存儲標(biāo)簽的個數(shù)為［3］：
其中：k=|φ|為關(guān)鍵詞個數(shù)。
證明首先給定k個查詢關(guān)鍵詞，最多有2k個關(guān)鍵詞子集。其次給定代價閾值Δ，算法檢查一條路經(jīng)的邊數(shù)不超過。其中，bmin為查詢圖G中最短邊的代價值。因此，在G中路徑的目標(biāo)值以為界。綜上，每個頂點(diǎn)最多存儲的路徑標(biāo)簽為Lmax=，其他具有相同目標(biāo)值的標(biāo)簽都會被近似支配。
定理2經(jīng)過目標(biāo)修正獲得的最優(yōu)解pos目標(biāo)值與實(shí)際最優(yōu)解popt的目標(biāo)值有如下關(guān)系：o(pos)≤·o(popt)［3］。
證明由定義6 可知，，0<θ<1，以下將、o(vi，vj)分別簡稱為和o。推導(dǎo)可知，，因此（e為p中的邊），繼而：
定義7（近似支配）假設(shè)給定一個稍大于1 的參數(shù)α（如α=1.1），路徑pi、pj的起點(diǎn)和終點(diǎn)相同，若pj.φ?pi.φ且，則路徑pj被pi近似支配，pj被剪枝。
定理3經(jīng)過近似支配的最優(yōu)解pdom的目標(biāo)值與pos的目標(biāo)值有如下關(guān)系：o(pdom)≤α·o(pos)［6］。
證明由定義7 可知，pj被pi近似支配時，被放大α倍，同理對于pdom和pos有關(guān)系：o(pdom)≤α·o(pos)。
定理4pdom的目標(biāo)值與popt的目標(biāo)值有如下關(guān)系：o(pdom)≤·o(popt)。
證明由定理3 可知，o(pdom)≤α·o(pos)，聯(lián)立定理2 可得o(pdom)≤α·o(pos)≤·o(popt)。
定義8（全局優(yōu)先級）從vs到vt的最小目標(biāo)值為o(vs，vt)。設(shè)置參量β（1<β<2），標(biāo)簽的全局優(yōu)先度表示為，全局優(yōu)先度越小，全局優(yōu)先級越高。
3 SE-KOR 算法
SE-KOR 的核心思想是構(gòu)建關(guān)鍵詞頂點(diǎn)路徑，將路徑按照關(guān)鍵詞頂點(diǎn)的次序分為多段并分段拓展。因此，本節(jié)重點(diǎn)介紹關(guān)鍵詞頂點(diǎn)路徑的構(gòu)建和分段拓展的關(guān)鍵技術(shù)。
3.1 關(guān)鍵詞頂點(diǎn)路徑的構(gòu)建
按照KOR 的求解框架，預(yù)處理階段已經(jīng)計(jì)算出查詢圖中任意兩頂點(diǎn)間的b(vi，vj)、o(vi，vj)，保證了任意兩頂點(diǎn)之間都是可達(dá)的。因此，對于查詢Q=(vs，vt，φ，Δ)，在構(gòu)建關(guān)鍵詞頂點(diǎn)路徑時，可以隱藏查詢圖G=(V，E)中沒有被φ覆蓋的頂點(diǎn)，保留起點(diǎn)、終點(diǎn)和φ覆蓋的頂點(diǎn)，形成查詢的關(guān)鍵詞頂點(diǎn)查詢圖G′。針對G′進(jìn)行拓展，獲取滿足關(guān)鍵詞全覆蓋和代價閾值的關(guān)鍵詞頂點(diǎn)路徑。
定義9（關(guān)鍵詞頂點(diǎn)）給定查詢Q=(vs，vt，φ，Δ)，若關(guān)鍵詞wi∈vm.φ，則稱vm是包含關(guān)鍵詞wi的一個頂點(diǎn)，簡稱關(guān)鍵詞頂點(diǎn)。
定義10（關(guān)鍵詞頂點(diǎn)路徑）給定Q=(vs，vt，φ，Δ)，φ={w1，w2，…，wn}，從vs開始不斷檢查未覆蓋的關(guān)鍵詞，并向相應(yīng)的頂點(diǎn)拓展，獲得從vs擴(kuò)展到vt的、滿足關(guān)鍵詞全覆蓋和代價閾值的路徑，不失一般性，記為，稱為關(guān)鍵詞頂點(diǎn)路徑。
定理5給定任意可行路徑，都存在一條關(guān)鍵詞頂點(diǎn)路徑與其一一對應(yīng)。
證明可行路徑指滿足關(guān)鍵詞全覆蓋、代價閾值的路徑，由定義10 可知，關(guān)鍵詞頂點(diǎn)路徑同樣滿足上述約束條件。
定義11（局部代價閾值）在構(gòu)建過程中，每拓展至一個關(guān)鍵詞頂點(diǎn)，記錄到達(dá)當(dāng)前節(jié)點(diǎn)的代價值，稱為局部代價閾值。
1）針對查詢圖G=(V，E)和查詢Q=(vs，vt，φ，Δ)，隱藏沒有被φ覆蓋的頂點(diǎn)，保留起點(diǎn)、終點(diǎn)和φ覆蓋的頂點(diǎn)，形成查詢的關(guān)鍵詞頂點(diǎn)查詢圖G′。在實(shí)現(xiàn)過程中，可以直接根據(jù)關(guān)鍵詞倒排索引列表獲取關(guān)鍵詞頂點(diǎn)，形成查詢圖G′。
2）在G′上利用廣度優(yōu)先搜索，拓展?jié)M足關(guān)鍵詞全覆蓋和代價閾值的路徑，記為關(guān)鍵詞頂點(diǎn)路徑。
下文用一個實(shí)例說明關(guān)鍵詞頂點(diǎn)路徑的構(gòu)建過程。在如圖3 所示的查詢圖中，顏色和形狀（菱形和三角形）相同的頂點(diǎn)包含相同的關(guān)鍵詞，虛線連接的是關(guān)鍵詞頂點(diǎn)路徑。
圖3 關(guān)鍵詞頂點(diǎn)路徑示意圖Fig.3 Schematic diagram of keyword vertex path
圖4 關(guān)鍵詞頂點(diǎn)路徑構(gòu)建示意圖Fig.4 Schematic diagram of keyword vertex path constructio
1）在vs處構(gòu)建初始標(biāo)簽。
2）從起點(diǎn)開始向所有關(guān)鍵詞頂點(diǎn)拓展，構(gòu)建從vs到關(guān)鍵詞頂點(diǎn)的標(biāo)簽，并計(jì)算全局優(yōu)先度后入隊(duì)。
3）選取全局優(yōu)先級最高的標(biāo)簽出隊(duì)，這里假設(shè)v1頂點(diǎn)處的出隊(duì)，此時已經(jīng)包含關(guān)鍵詞w1，向尚未包含的關(guān)鍵詞w2覆蓋的頂點(diǎn)v3、v4拓展構(gòu)建標(biāo)簽，并判斷新標(biāo)簽是否滿足代價閾值和近似支配條件，若滿足則入隊(duì)，否則被刪除。
4）繼續(xù)選取優(yōu)先級別最高的標(biāo)簽拓展，重復(fù)過程3），直至拓展至終點(diǎn)vt，選取滿足關(guān)鍵詞全覆蓋、代價閾值和目標(biāo)值最小的標(biāo)簽記為。
拓展結(jié)果體現(xiàn)在如圖5 所示的G′中，v2、v4是在構(gòu)建時被舍棄的關(guān)鍵詞頂點(diǎn)。
圖5 關(guān)鍵詞頂點(diǎn)路徑示例Fig.5 Keyword vertex path example
3.2 分段拓展和拓展方向的控制
分段拓展補(bǔ)充起點(diǎn)到關(guān)鍵詞頂點(diǎn)、關(guān)鍵詞頂點(diǎn)之間以及關(guān)鍵詞頂點(diǎn)到終點(diǎn)之間的路徑，如圖5 中vs→v1、v1→v3、v1→vt的路徑。
對每一分段采用廣度優(yōu)先搜索，根據(jù)局部代價閾值、可行解目標(biāo)值的約束分別對其進(jìn)行拓展。在關(guān)鍵詞頂點(diǎn)路徑的基礎(chǔ)上拓展，搜索規(guī)?？s減至僅與關(guān)鍵詞頂點(diǎn)路徑中相關(guān)的頂點(diǎn)的局部圖，很大程度上降低了路徑查詢中搜索的規(guī)模。
在分段拓展過程中的一個問題是：需要避免分段之間的交叉，即控制拓展方向避免分段之間的交叉。一種解決方案是：利用已經(jīng)求出的局部代價閾值，進(jìn)行局部代價閾值剪枝，約束每一段路徑的代價值，從而達(dá)到控制路徑方向，避免分段路徑的交叉。
在對每個分段拓展時，將代價閾值約束條件替換為局部代價閾值。如圖6 所示，在拓展分段vs→v1時，判斷從vs經(jīng)過白色頂點(diǎn)到v1的上下兩條路徑p1、p2的代價值b(p1)、b(p2)是否小于等于v1處的局部代價閾值，若是則入隊(duì)，否則被舍棄。如此，路徑拓展方向朝向違背的方向時，會被即時剪枝，避免各分段路徑的交叉，控制拓展方向。
圖6 分段拓展示意圖Fig.6 Schematic diagram of segmented expansion
3.3 查詢近似度分析
現(xiàn)有算法通過鄰邊拓展求取途徑關(guān)鍵詞頂點(diǎn)，且滿足代價閾值時點(diǎn)與點(diǎn)之間的最短路徑，將其劃分為子問題可以看作是以關(guān)鍵詞頂點(diǎn)為界的每一段路徑的拼接。本質(zhì)上鄰邊拓展方法是邊拓展邊判斷一個頂點(diǎn)是否為關(guān)鍵詞頂點(diǎn)。由定理5 可知，任意一條可行路徑與一條關(guān)鍵詞頂點(diǎn)路徑一一對應(yīng)。而SE-KOR 根據(jù)關(guān)鍵詞倒排索引表直接獲取關(guān)鍵詞頂點(diǎn)，并依據(jù)預(yù)處理求取目標(biāo)值最小關(guān)鍵詞頂點(diǎn)路徑以及代價值最小關(guān)鍵詞頂點(diǎn)路徑作為路徑分段依據(jù)，進(jìn)行分段拓展，大幅減小了搜索規(guī)模。因此，SE-KOR 算法具有可行性。
由上式可知，使用SE-KOR 算法返回的與最優(yōu)解誤差在最壞情況下不超過，α是一個稍大于1 的數(shù)值，在可控范圍內(nèi)。
3.4 算法描述
SE-KOR 算法由計(jì)算關(guān)鍵詞頂點(diǎn)路徑的comKeywordVertexPath()函數(shù)和分段拓展的主程序兩部分組成。
SE-KOR 算法主程序如下：
運(yùn)行示例：給出Q={v1，v10，
下面分析算法的時間和空間復(fù)雜度：
1）時間復(fù)雜度
2）空間復(fù)雜度
在分段拓展過程中，將路徑劃分為s+1（s+1≥1）段路徑。假設(shè)整條路徑需要遍歷n（n≤|V|）個節(jié)點(diǎn)，當(dāng)路徑被劃分為s+1 段時，則每段路徑平均遍歷個節(jié)點(diǎn)，因此每個頂點(diǎn)標(biāo)簽個數(shù)的上界為，則s+1段路徑共需維護(hù)個標(biāo)簽，空間復(fù)雜度為。
4 實(shí)驗(yàn)結(jié)果與分析
上文已經(jīng)給出SE-KOR 的實(shí)現(xiàn)過程和算法步驟，本節(jié)通過實(shí)驗(yàn)驗(yàn)證SE-KOR 在執(zhí)行時間上的優(yōu)越性，并對執(zhí)行時間與近似度進(jìn)行分析。
4.1 實(shí)驗(yàn)設(shè)定
實(shí)驗(yàn)設(shè)計(jì)如下：
1）實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集
實(shí)驗(yàn)環(huán)境：win10，運(yùn)行在Intel?CoreTMi7-8550U處理器和16 GB 內(nèi)存上。算法使用Java 在IntelliJ IDEA 上實(shí)現(xiàn)。數(shù)據(jù)從公開的路網(wǎng)數(shù)據(jù)集中下載，并隨機(jī)生成關(guān)鍵詞信息。數(shù)據(jù)集信息如表4 所示。
表4 不同規(guī)模數(shù)據(jù)查詢Table 4 Data query of different scales
2）實(shí)驗(yàn)設(shè)計(jì)
由于KORL 的預(yù)處理階段與SE-KOR 的預(yù)處理有所不同，且面向大規(guī)模數(shù)據(jù)集，Greedy、KSRG 沒有實(shí)現(xiàn)具體路徑的查找，因此僅與OSScalling、BucketBound 算法對比。針對關(guān)鍵詞個數(shù)、代價閾值、查詢圖規(guī)模等查詢因素，設(shè)置實(shí)驗(yàn)1～實(shí)驗(yàn)3，取平均查詢時間和平均近似度為評價標(biāo)準(zhǔn)。
實(shí)驗(yàn)1關(guān)鍵詞個數(shù)不同時算法的執(zhí)行時間
控制數(shù)據(jù)集和代價閾值不變，改變關(guān)鍵詞個數(shù)。查詢圖為G3，代價閾值為40 km，關(guān)鍵詞個數(shù)為2、4、6、8，分別對3 個算法進(jìn)行測試，隨機(jī)提交5 個查詢，取平均執(zhí)行時間和平均近似度。
實(shí)驗(yàn)2代價閾值不同時算法執(zhí)行時間
控制數(shù)據(jù)集和關(guān)鍵詞個數(shù)不變，改變代價閾值。查詢圖為G3，關(guān)鍵詞個數(shù)是4，代價閾值為45 km、55 km、65 km、75 km、85 km，分別對3 個算法進(jìn)行測試，隨機(jī)提交5 個查詢，取平均執(zhí)行時間和平均近似度。
實(shí)驗(yàn)3查詢圖規(guī)模不同時算法的執(zhí)行時間
控制關(guān)鍵詞個數(shù)和代價閾值不變，改變查詢圖規(guī)模。代價閾值為55 km，關(guān)鍵詞個數(shù)為6，分別對3 個算法進(jìn)行測試，隨機(jī)提交5 個查詢，取平均執(zhí)行時間和平均近似度。
4.2 實(shí)驗(yàn)結(jié)果
本節(jié)分別給出3 個查詢因素下SE-KOR 的執(zhí)行時間和近似度的實(shí)驗(yàn)結(jié)果，并加以分析。
4.2.1 不同查詢因素下算法的執(zhí)行時間
不同查詢因素下算法的執(zhí)行時間主要有以下3 種：
1）不同關(guān)鍵詞個數(shù)下算法的執(zhí)行時間實(shí)驗(yàn)1 結(jié)果如圖7 所示，隨著關(guān)鍵詞個數(shù)的增長，SE-KOR 的執(zhí)行時間明顯短于對比算法，當(dāng)關(guān)鍵詞個數(shù)為2 時，SE-KOR 執(zhí)行時間至少縮短8.0%。OSScalling 是鄰邊拓展，當(dāng)關(guān)鍵詞個數(shù)增加時，搜索規(guī)模也隨之增加。雖然BucketBound 將優(yōu)先級隊(duì)列劃分為多個bucket，但鄰邊拓展的本質(zhì)沒變。而SE-KOR 將路徑劃分為多段，有效降低搜索規(guī)模，縮短了執(zhí)行時間。
圖7 不同關(guān)鍵詞個數(shù)下算法的執(zhí)行時間Fig.7 Execution time of algorithm under different keyword numbers
2）不同代價閾值下算法的執(zhí)行時間
實(shí)驗(yàn)2 結(jié)果如圖8 所示，當(dāng)代價閾值增大時，查詢時間呈先增長后穩(wěn)定的趨勢，且SE-KOR 的執(zhí)行時間較BucketBound 至少縮短61.0%。針對另外兩種算法，當(dāng)代價閾值持續(xù)增加時，最優(yōu)解不會發(fā)生變化，查詢時間由高趨于穩(wěn)定。而SE-KOR 的查詢時間與構(gòu)建關(guān)鍵詞頂點(diǎn)路徑有關(guān)，因此查詢時間的峰值點(diǎn)與另外兩種算法有所不同，但走向基本一致。
圖8 不同代價閾值下算法的執(zhí)行時間Fig.8 Execution time of algorithm under different cost thresholds
3）不同查詢圖規(guī)模下算法的執(zhí)行時間
實(shí)驗(yàn)3 結(jié)果如圖9 所示，隨著查詢圖規(guī)模的增大，SE-KOR 的查詢時間較另外兩種算法緩慢增長，且SE-KOR 執(zhí)行時間至少縮短57.7%。隨著查詢圖規(guī)模不斷增大，另外兩種算法因大量中間拓展操作，造成搜索規(guī)模越來越大。而SE-KOR 將路徑劃分為多段拓展，能有效避免拓展過程中產(chǎn)生的大量拓展操作，從而顯著縮短執(zhí)行時間。
圖9 不同查詢圖規(guī)模下算法的執(zhí)行時間Fig.9 Execution time of algorithm under different query graph scales
4.2.2 不同查詢因素下的近似度分析
不同查詢因素下的近似度分析主要有以下2 種：
1）不同關(guān)鍵詞個數(shù)下的近似度分析
實(shí)驗(yàn)1 的近似度曲線如圖10 所示，在不同關(guān)鍵詞個數(shù)下，SE-KOR 的近似度與另外兩種算法相差無幾，甚至?xí)霈F(xiàn)優(yōu)于BucketBound 的情況。而OSScalling、BucketBound 求的近似解在實(shí)際最優(yōu)解處波動。
圖10 不同關(guān)鍵詞個數(shù)下算法的近似度Fig.10 Approximation of algorithm under different keyword numbers
2）不同代價閾值下的近似度分析
實(shí)驗(yàn)2 的近似度曲線如圖11 所示，在不同代價閾值的約束下，SE-KOR 的近似度趨于穩(wěn)定，而另外兩種算法的近似度有所浮動。這是因?yàn)榇鷥r閾值越大，前期構(gòu)建路徑邊界時越容易找到目標(biāo)值最小關(guān)鍵詞頂點(diǎn)路徑。而另外兩種算法依舊是逐步篩選中間路徑，直到找到近似最優(yōu)解，因此會有波動。
圖11 不同代價閾值下算法的近似度Fig.11 Approximation of algorithm under different cost thresholds
5 結(jié)束語
針對現(xiàn)有KOR 算法在搜索長路徑時執(zhí)行時間較長的問題，提出SE-KOR 算法將路徑劃分為多段并分別拓展。SE-KOR 算法根據(jù)關(guān)鍵詞倒排索引列表對關(guān)鍵詞頂點(diǎn)拓展，獲得目標(biāo)值最小關(guān)鍵詞頂點(diǎn)路徑以及代價值最小關(guān)鍵詞頂點(diǎn)路徑，以此為依據(jù)，將路徑以關(guān)鍵詞頂點(diǎn)為邊界節(jié)點(diǎn)，把路徑劃分為多個分段。在分段拓展中采用局部代價閾值以及綜合運(yùn)用近似支配、可行解目標(biāo)值剪枝、全局優(yōu)先拓展等剪枝策略加速拓展。實(shí)驗(yàn)結(jié)果表明，SE-KOR 算法能夠顯著縮短執(zhí)行時間，且不損失精度。下一步將對現(xiàn)有單源［21-23和全源［24-26］最短路徑進(jìn)行研究，提出合適拓展策略降低各個分段路徑的關(guān)聯(lián)度，并行拓展每個分段路徑，最終將各分段路徑拼接，形成完整的路徑。
