计算机应用研究2016，Vol.33Issue(3)：779-782,4.DOI:10.3969/j.issn.1001-3695.2016.03.031
多层分割算法在构建层次道路网络中的应用
Application of multi-level algorithms in constructing hierarchical road network
摘要
Abstract
While constructing large scale road network,the application of “hierarchy”strategy is attractive for its efficiency in intensively reducing the solution space.Furthermore,parting the road network into small regions would improve.Up to now, many graph partition algorithms have proposed.However,the multi-level partition algorithm called METIS hasn’t used in hierarchical road network.This kind of algorithms usually consisted three phases,such as coarsening phase,partitioning phase and uncoarsening phase.After partition,the graph results in a group of regions which contain roughly the same number of verti-ces.This paper used two multi-level algorithms as multi-level recursive bisectioning (MLRB)and multi-level k-way partitio-ning (MLKP)to partition road network,with the purpose of testing whether this kind of algorithms was suitable for applications that emphasize the connection topology of network.Result shows that the original multi-level algorithms are not suitable to road network,while the thought of “multi-level”process is valuable to refer.关键词
路径规划/多层分割算法/多层递归二分算法/多层k路分割算法/分区Key words
path planning/multi-level algorithms/MLRB/MLKP/graph partition分类
信息技术与安全科学引用本文复制引用
撖志恒,芮小平,董承玮,宋现锋,王静,徐江..多层分割算法在构建层次道路网络中的应用[J].计算机应用研究,2016,33(3):779-782,4.基金项目
国家科技支撑计划项目课题（2012BAC25B01）；国家科技重大专项课题资助项目 （）
