最短路徑查詢用于返回圖中兩點之間的最短路徑,是圖數(shù)據(jù)管理中的核心操作之一,一直以來都是研究者關注的熱點問題。最短路徑查詢廣泛應用在各種道路交通網(wǎng)絡、社會網(wǎng)絡、生物信息網(wǎng)絡中對數(shù)據(jù)進行分析。隨著實際中數(shù)據(jù)圖規(guī)模的不斷增大和應用領域的不斷擴張,最短路徑查詢處理效率的進一步提升是亟待解決的關鍵問題。本文針對無向無權圖的最短路徑查詢問題進行研究,具體研究如下:首先,針對實際中數(shù)據(jù)圖比較稀疏且服從冪律分布的特點,提出對原始圖進行分割,分別處理的策略。該策略首先從原始圖中刪除單枝路徑來得到一個規(guī)�？s減的圖。對單枝路徑,利用頂點在路徑中的相對位置對頂點進行編碼,快速計算路徑內(nèi)頂點間的最短距離。對簡化圖,構建基于簡化圖的地標標簽索引,用于快速求解簡化圖上頂點對的最短路徑。其次,基于單枝路徑索引和簡化圖索引,提出一種高效的最短路徑求解方法。該方法的基本思想是:給定兩個查詢點,如果這兩個點同時位于單枝路徑或簡化圖中,則用相應的單枝路徑索引或地標標簽索引進行快速求解;否則,先查找兩個頂點在簡化圖上的基點,通過計算基點之間的最短路徑,以及基點和查詢點的最短路徑來得到最終的查詢回答結果。最后,利用現(xiàn)實當中的數(shù)據(jù)... 

【文章來源】：燕山大學河北省

【文章頁數(shù)】：58 頁

【學位級別】：碩士

【部分圖文】：

無向無權圖

第3章基于簡化圖的索引構建策略17引階段，需要構建每個頂點的標簽索引，沒有考慮到頂點之間的相互關系，使得算法存在冗余遍歷以及儲存了冗余的最短路徑信息。圖3-1無向無權圖G表3-1圖G的2-hop標簽索引V2-hoplabelv1{(v1,0),(v2,2),(v3,1),(v4,1),(v5,1),(v6,2),(v7,2),(v8,3),(v9,4),(v10,3),(v11,4),(v12,5)}v2{(v2,0),(v3,1),(v5,1),(v6,2)，(v7,3),(v8,2),(v9,3),(v10,1),(v11,2),(v12,4)}v3{(v3,0),(v8,3),(v9,4),(v10,2),(v11,3),(v12,5)}v4{(v4,0),(v5,1),(v7,1),(v8,2),(v9,3),(v10,3),(v11,4),(v12,4)}v5{(v5,0),(v8,1),(v9,2),(v12,3)}v6{(v6,0)}v7{(v7,0)}v8{(v8,0),(v9,1)}v9{(v9,0)}v10{(v10,0),(v11,1)}v11{(v11,0)}v12{(v12,0)}基于以上構建標簽索引的問題，本章根據(jù)PLL算法構建2-hop標簽索引方法的基礎上進行完善以及改進，目的是通過減少遍歷數(shù)據(jù)圖的次數(shù)以及減少冗余的標簽索引，從而降低最短路徑查詢的搜索空間，同時提高最短路徑中頂點對的查詢處理性能。本章所提出的標簽索引構建策略，即ConstructPrune算法。該算法主要思想是針對實際中數(shù)據(jù)圖比較稀疏且服從冪律分布的特點，提出對原始數(shù)據(jù)圖進行分割，分別處理的策略。該策略首先從原始圖中刪除單枝路徑來得到一個規(guī)模縮減的圖。

第3章基于簡化圖的索引構建策略19列。定義3.4(簡化圖)：不包含單枝路徑的數(shù)據(jù)圖稱為簡化圖。簡化圖是一個復雜圖，其圖的特性是稠密，并且不包含單枝路徑。其中在原數(shù)據(jù)圖中刪除單枝路徑后，基點仍存在于原數(shù)據(jù)圖中。在簡化圖中，每個頂點的頂點度都會大于等于2。例如圖3-3中，是將圖3-1中圖G中刪除所有的單枝路徑所得到的，由頂點v1、v2、v3、v4，v5、v6以及彼此相連的邊所組成的圖是原數(shù)據(jù)圖的簡化圖。定理3.1：如果原數(shù)據(jù)圖是一個連通圖，經(jīng)過刪除某個或所有的單枝路徑(不包含基點)后的簡化圖依然也是一個連通圖。證明：在單枝路徑中基點的頂點度至少為3，其中的至少1個是單枝路徑上的點，去掉單枝路徑并沒有對非單枝路徑上的點和邊做任何改動，不影響連通性。因此，若原數(shù)據(jù)圖為一個連通圖，簡化圖也是一個連通圖。證畢。定義3.5(簡化圖標簽索引)：在簡化圖中，依次對各個頂點進行廣度優(yōu)先遍歷，根據(jù)2-hop標簽索引來構建最短路徑標簽索引，該標簽索引為L(v)，該索引包含若干個二元組(u,)，其中u表示為數(shù)據(jù)圖中另一結點，表示v到u的最短距離。定義3.6(頂點優(yōu)先級)：假設有一數(shù)據(jù)圖G，其中在一個最短路徑生成樹G-Tree中，將樹結點的子樹寬度與在圖G中的頂點度的大小相乘作為頂點的優(yōu)先級順序，優(yōu)先級越高的頂點，在算法中其處理順序越優(yōu)先。例如圖3-2，是對圖3-1所求得的最短路徑樹，按優(yōu)先級數(shù)值降序，各頂點的排列為：v2，v5，v3，v10，v6，v8，v4，v11，v1，v9，v7，v12。圖3-2圖G的最短路徑樹

【參考文獻】：
期刊論文
[1]路網(wǎng)環(huán)境下訪問序列受限的多標簽路線查詢算法[J]. 張金增,文潔,孟小峰.  計算機學報. 2012(11)



本文編號：3386725