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