计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2015年
z1期
285-289
,共5页
重叠社团%双层路由%大规模道路网络
重疊社糰%雙層路由%大規模道路網絡
중첩사단%쌍층로유%대규모도로망락
Overlapping community%Double-layer routing%Large road networks
大规模道路网络中的最短路径快速搜索算法在交通系统的导航、交通分配等方面具有广泛的应用.现有的几种分层算法虽然在计算性能上比传统的算法有所改善,但仍存在计算量较大和计算效率较低等问题.提出了基于重叠社团划分的大规模道路网络双层路由算法,该算法在道路网络中探测基于重叠社团的分层结构,将整个网络划分为若干具有重叠节点的社团,并由此构成路网的双层结构:第一层为原始道路网络;第二层为社团连接逻辑层,其中的每一个点对应第一层的一个社团,第一层社团间的重叠节点和道路连接对应第二层节点间的连接.在此网络架构下,路由被分解为第二层社团节点间启发式的总体路由和第一层社团内部节点的局域路由.该算法提出将社团间的重叠节点作为相应两个社团之间的关键路由节点,并将其引入到基于社团的分层路由算法当中,可以有效地降低算法的搜索空间和计算复杂度,有效地提高了算法效率.几个真实城市路网的实验结果表明了本算法的有效性.
大規模道路網絡中的最短路徑快速搜索算法在交通繫統的導航、交通分配等方麵具有廣汎的應用.現有的幾種分層算法雖然在計算性能上比傳統的算法有所改善,但仍存在計算量較大和計算效率較低等問題.提齣瞭基于重疊社糰劃分的大規模道路網絡雙層路由算法,該算法在道路網絡中探測基于重疊社糰的分層結構,將整箇網絡劃分為若榦具有重疊節點的社糰,併由此構成路網的雙層結構:第一層為原始道路網絡;第二層為社糰連接邏輯層,其中的每一箇點對應第一層的一箇社糰,第一層社糰間的重疊節點和道路連接對應第二層節點間的連接.在此網絡架構下,路由被分解為第二層社糰節點間啟髮式的總體路由和第一層社糰內部節點的跼域路由.該算法提齣將社糰間的重疊節點作為相應兩箇社糰之間的關鍵路由節點,併將其引入到基于社糰的分層路由算法噹中,可以有效地降低算法的搜索空間和計算複雜度,有效地提高瞭算法效率.幾箇真實城市路網的實驗結果錶明瞭本算法的有效性.
대규모도로망락중적최단로경쾌속수색산법재교통계통적도항、교통분배등방면구유엄범적응용.현유적궤충분층산법수연재계산성능상비전통적산법유소개선,단잉존재계산량교대화계산효솔교저등문제.제출료기우중첩사단화분적대규모도로망락쌍층로유산법,해산법재도로망락중탐측기우중첩사단적분층결구,장정개망락화분위약간구유중첩절점적사단,병유차구성로망적쌍층결구:제일층위원시도로망락;제이층위사단련접라집층,기중적매일개점대응제일층적일개사단,제일층사단간적중첩절점화도로련접대응제이층절점간적련접.재차망락가구하,로유피분해위제이층사단절점간계발식적총체로유화제일층사단내부절점적국역로유.해산법제출장사단간적중첩절점작위상응량개사단지간적관건로유절점,병장기인입도기우사단적분층로유산법당중,가이유효지강저산법적수색공간화계산복잡도,유효지제고료산법효솔.궤개진실성시로망적실험결과표명료본산법적유효성.
