文档介绍：该【多层分割算法在构建层次道路网络中的应用 】是由【青山代下】上传分享，文档一共【4】页，该文档可以免费在线阅读，需要了解更多关于【多层分割算法在构建层次道路网络中的应用 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..计算机应用研究 2016年3月 Application Research puters 多层分割算法在构建层次道路网络中的应用撖志恒,芮小平”,董承玮,宋现锋,王静,徐江。(,北京100049;,北京100038;,北京100098) 摘要:在大规模道路网络上使用“分层”策略构建层次道路网络能够显著降低路径规划算法的搜索空间,对分层道路网络进行分区可改进数据结构,进一步提升算法效率。现有多种网络图分割算法,介绍一类名为METIS 的多层分割算法,此类算法通过概化(coarsening phase)、分割(partitioning phase)、还原(uncoarsening phase)三阶段将网络图划分为均等分区,且算法效率高。将两种典型多层分割算法:多层递归二分算法(MLRB)及多层k 路分割算法(MLKP)应用于层次道路数据,以检验此类算法是否适用于强调拓扑连通性的道路网络的分区。结果分析表明,多层算法的分区结果并不适合层次道路网络构建,但多层分割的思想值得借鉴。关键词:路径规划;多层分割算法;多层递归二分算法;多层k路分割算法;分区中图分类号:; 文献标志码:A 文章编号:(2016) doi:.1001- Application of multi—level algorithms in constructing hierarchical work Han Zhiheng ,Rui Xiaoping”Dong Chengwei ,Song Xianfeng ,Wang Jing ,Xu Jiang ,( ofResources&Environment,University ofChineseAcademyofSciences,Beijing100049,China; and Mapping,Be ng 100038,China; Digital Huibo Technology Co.,Ltd.,Belting 100098,China) Abstract:While constructing large scale application of“hierarchy’’strategy is attractive for its efficiency in intensively reducing the solution space;Furthermore,parting the work into small regions would to now, many graph partition algorithms have ,the multi-level partition algorithm called METIS hasn’t used in hierarchical kind of algorithms usually consisted three phases,such as coarsening phase,partitioning phase and uncoarsening partition,the graph results in a group of regions which contain roughly the same number of verti— paper used two multi-level algorithms as multi—level recursive bisectioning(MLRB)and multi—level k-way partitio- ning(MLKP)to partition work,with the purpose of testing whether this kind of algorithms was suitable-for applications that emphasize the connection topology shows that the original multi—level algorithms are not suitable to road network,while the thought of“multi—level”process is valuable to refer. Key words:path planning;multi—level algorithms;MLRB;MLKP;graph partition 大致相同的区域,同时保持连接不同区域的切边数量最少或切O引言边上通信量最小,此类问题也称为k均分问题(k-balanced par- titioning) ,数学描述如下。输入的图表示为G=( , ),节随着现代交通网络的急剧扩张,为了在大规模道路网络上点数n=I I,边的权值w: 冗,k均分的结果为一系列互不实现路径规划服务,在构建基础数据结构时多对道路网络采用相接的节点集,…, ,满足V= u…u &vi f7 = “分层”策略 l2J。道路网络分层技术可显著降低路径规划算(i )。记( , )表示将G划分为个节点集,任一节点集中法可行解搜索空间,在控制路径规划问题的计算时间随网络规节点数不超过(n/k),plete,此类问题模呈非线性增长等方面的良好性能,已成为求解大规模网络中不能在多项式时间内找到最优解。k= 。一般而言,道路网络分(minimum bisection problem), ≥2且≥2时,已有O(1og n)倍层后,高一层级道路为低一层级道路的子集,较高层级包含数于最优解的近似算法,对于v<2并趋向于1的情况,文献[9] 据量小,较低层级的数据规模逐渐接近整个道路网络,路径规给出了多重对数倍于最优解的多项式算法。划算法在调用较低层级道路时依然有加载大量数据的问题。综合而言,针对k均分问题的算法可划分为三类。第一类针对这一问题,多将已分层数据再进一步分区。,以进一步算法由Leighton等人。。以及Simon等人提出,这类算法的减少搜索时加载的数据量。思路为先通过一种对分方法生成图的初始分割,之后在各区块对得到的分层道路进行分区,实质是对网络图进行分割。间交换节点来降低区块之间的关联,区块之间的关联无法降低图分割是最优化问题中的一种,分割的目标是将图划分为规模时完成分割。这类算法的执行效率及划分结节点果与初始收稿日期:2014—11·12;修回日期:2015—02—10 基金项目:国家科技支撑计划项目ig￣(2012BAC25B01);国家科技重大专项课题资助项目(2011ZX05039-004) 作者简介:撖志恒(1988·),男,河南平顶山人,硕士,主要研究方向为地理信息科学应用;芮小平(1975.),男(通信作者),江苏苏州人,副教授, 硕导,博士,主要研究方向为地理信息科学理论与应用(******@). :..·780· 计算机应用研究第33卷分割的好坏关系密切。第二类算法由Even等人及Konstan—复制到G 中。合并节点的目的是降低简化图的规模,因此需tin等人提出。文献[13]定义一系列称为spreading metrics 要找到G 的最大匹配来生成G…。的图操作函数,并将spreading metrics应用于线性规划松弛分割算法中,在k≥2且≥2时,将近似算法相对于最优解的近似因子界定在0(1og n);文献[9]给出了在<2并趋向于1的情况下的多项式算法,近似因子为O(1og n)。第三类算法则利用启发式信息提高算法效率,如被称为METIS的启发式多层网络分割算法’”J。这类算法一般包含三个步骤:图形合并、分割、还原。具体而言,先将原始图中节点按照某种规则合并,在合并后图上进行分割,之后将初始分割图还原得到原始图,得到最终分割结果。此类算法执行效率很高,并能得到较为均衡的分区结果,在实践中得到广泛应用。本文首先介绍两种多层分割算法的原理:多层递归二分算图2不同匹配方式法(muhilevel recursive bisectioning,MLRB)和多层k路分割算概化过程并不能持续不断进行,当G 中节点数较小(可以法(multilevel k-way partitioning,MLKP),之后使用北京地区道根据问题规模估计)或概化图前后差异不大时应终止概化过路网络进行分区测试,最后对结果进行分析,指出未来研究的程。下面介绍合并节点时采用的几种策略。方向。a)random matching(RM) 随机匹配的过程如下,随机访问中节点,如果节点尚1 多层分割算法未匹配,则随机选择/Z邻接节点中尚未匹配的节点,将边(/Z, )加入匹配边集合中,并标记节点“、为已匹配。如果“ 多层递归二分算法接节点都已匹配,则在随机匹配过程中”保持未匹配状态。算MLRB算法的思想比较简单,先通过概化将图简化为只有法的复杂度为0(IE1)。少数节点,二分得到简化图,之后将得到的分区细化,通过投影 b)light edge matching(LEM) 肇撬还原到原始图。在细化过程中,分区边界得到逐步改进,切边随机匹配计算图匹配方式简单、高效,本质是使用贪心策数逐渐降至最小,算法过程如图1所示。略来实现最大匹配,然而,分区的目标是最小化切边(或通信量),在匹配过程中选择边权重最大的边可更快地达到概化图的目标。和随机匹配中访问节点方式相同,以随机方式访问节点,但在匹配节点时,不再随机选择/Z邻接节点中尚未匹配的节点,而选择使得边( , )权重最大的节点。算法的复杂度和随机匹配相同,均为O(IEI)。C)heavy clique matching(HCM) 图论中的团(clique)指满足任意两个节点间都有边连接的节点集,团内部的节点具有良好的连通性,在分区时应倾向属于同一分区,此即HCM策略的核心。定义U为G的子图, 初始分割满足G =(U,Eu),定义edge density指标Ed=2 I J/(J U J (initial partitioning phase) 图1 多层分割算法过程示意图(I I一1)),当子图U趋向于团时, 趋向于1。简化过程中, 1)概化阶段(coarsening phase) HCM倾向于将具有高的节点匹配形成多重节点。在此过程中,图G转换为一系列逐渐变小的图G,,G2,…, 2)分割阶段(partitioning phase) G ,且满足I I>I I>…>I l。概化的方式主要有:ran—此阶段将概化图G 进行二分,获得较好的二分图P ,可dom matching(RM)、heavy edge matching(HEM)、light edge 以使用的算法包括谱二分法(spectral bisection)、几何二分法matching(LEM)等,如图2所示。在多数概化方式中,都需要(geometric bisection)binatorial methods)。由将G 中的节点集合并形成下一概化图G…中的一个节点。如于概化图规模一般较小,执行以上算法通常耗时很少。G 中的一个节点集经合并形成+ 中的节点,则节点成 3)细化阶段(uncoarsening phase) 为多重节点(muhinode)。为保证简化图的二分图能真实反映在细化阶段,需要从G 逐层投影到G ,G ,…,G ,G 原有图的节点权重特征,节点的权重等于节点集中所有中的每个节点都包含G 中的一个节点集,在投影过程中,将节点权重之和,为保证简化图中边的连通信息,节点集中的 G 中节点对应G 中的节点集的分区标记为+。[ ](比边作为节点的关联边集合。概化过程伴随着节点与边的合如,P [u]=P [ ],Vu∈)。在G 中,P 是局部最优并,合并边的思想可用匹配(matching)进行定义。图的匹配是的,投影到G 后则不能保证局部最优性。G 中有更多的节点一个没有公共端点的边的集合,集合中的任一个元素均不是自和边,相比G 有更高的自由度,因此可以用来对投影结果进环。图的最大匹配包含了尽可能多的相互独立的边。根据行改善。在实践中,Kernighan—Lin(KL)算法及其改进算法通常定义,从简化图G 到G…的过程可以描述为:找到G 的一个有很好的改善结果。基于KL的细化算法从分区中分别选择匹配,并将节点合并生成多重节点,未匹配的节点则直接从节点,之后交换节点的分区,若切边数下降则保留交换结果。:..·782· 计算机应用研究第33卷产生数据冗余,不利于路径规划中道路搜索。从分区结果对路[5][D].广州:华南径规划算法执行的便捷性上考虑,METIS的两种多层分割算法理工大学,2011. 并不适于层次道路网络中低层级网络的分区处理。[6]Tang Yuxin,Zhang Yunquan,Chen shortest path algo· rithm based on graph-partitioning and iterative correcting[c]//Proc of the 10th IEEE International Conference on Hi sh —puting :115·161. [7]Li Qingquan,Zeng voronoi-based hierarchical graph model of work for route planning[C]//Proc of the 1lth International IEEE Conference on Intelligent Transportation . [8]Kraut***r R,Naor J S,Schwartz graphs into ponents[C]//Proc of the 12th Annual ACM·SIAM Sym- posium on Discrete :4-6. [9]Konstantin A,Harald graph partitioning[J].Theory of 图6多层算法分区结果及存在问题(1) Computing Systems,2006,39(6):929—939. 【10]Leighton F,Makedon F,Tragoudas algorithms for VLSI partition problems[C]//Proc of IEEE International Symposium on Circuits and :2865—2868. [11]Simon H D,Teng good is recumive bisection?[J].SIAM Journal puter,1997,18(5):1436—1445. [12]秦旭彦,陆化普,[J].清华大学学报:自然科学版,2009,49(3):333—336. [13]Even G,Naor J,Rao S,et approximate graph partitioning algo—图7多层算法分区结果及存在问题(2) rithms[J].SIAM Joumal puter,1999,28(6):2187·2214. [14]Karypis G,Kumar k-way Partitioning Scheme for 3结束语 IrregularGraphs[J].Parallel puting,1998,48(1): 96—129. “分层”策略对于大规模道路网络中路径规划算法加速有[15]Karypis G,Kumar fast and high quality multilevel scheme for 重要意义,而对获得的层次道路进一步分区能再次提升算法效 partitioning iregular graphs[J].SIAM Journal on · 率。本文先介绍一类应用广泛的网络分割算法METIS,对其中 puting,1999,20(1):359—392. 两种具有代表性的算法:多层递归二分算法(MLRB)和多层k [16]Jcrgen B J,Gregory :theory,algorithms and applications [M].2 nd :科学出版社,2009. 路分割算法(MLKP)进行介绍,并详细说明两种算法核心的匹* } }} } { } 十{} { { 配策略。本文的创新在于将两种多层算法应用于分层道路的* * * * 分区中,实验中发现多层算法执行效率很高,得到的分区均衡, 但存在分割道路及破坏道路网络连通拓扑的缺点,这些缺点对在层次道路网络模型上执行路径规划算法有直接影响,不宜将:· 新闻专题阶段性摘要的生成研究: 原始的多层分割算法直接应用于道路网络分区。为使用此类* 夺基于LDA的互联网广告点击率预测研究* 算法进行分区,还需要对原始算法进行改进以避免其缺点。一* 夺基于不确定数据的可能频繁闭序列模式挖掘* 种可行的改进策略为层次策略。这种策略不对分区的均衡性: 峥基于标签相似度的不良信息多标签分类方法: 作出保证,而是利用道路网络中高等级道路分割低等级道路网对态强简单候选关键字算法研究: 络。一般而言,低等级公路汇聚到高等级公路,此种策略可以: 夺基于多策略的短文本信息流会话抽取: 避免分割道路,同时能保留原有道路网络的连通拓扑关系,形* 夸大数据下的快速kNN分类算法* 成的分区边界更加自然,更适宜于路径规划算法。此类基于层* 夺中文文本同频词统计规律及在关键词提取中的应用* 次策略的分区算法是未来构建层次道路网络模型中值得研究:4,K—S检验与mRMR相结合的基因选择算法: 的一个方向。夺基于用户评论的信任预测方法研究: : 争细菌觅食算法求解高维优化问题: 参考文献: * 夺异维学****人工蜂群算法* [1]陈玉敏,龚健雅,[J].武* 夺邻域结构为复杂网络的粒子群算法* 汉大学学报:信息科学版,2006,31(1):70-73. : 夺筛选和记忆相结合的粒子群算法: [2]李清泉,郑年波,徐敬海,[J].中国图象图形学报,2007,12(7):1280- : 夺交叉路121中一种智能的车辆实时调度算法: 1285 * 夸基于新鲜度的冷链物流配送多目标优化模型* [3]Jung S,Pramanik efficient putation model for hierar- * 啼基于多核系统NOC架构的静态列表调度算法: chicallv struetured topographical road maps[J].IEEE Trans on 夸基于时间帧的处理器PFair调度改进算法: Knowledge&Data Engineering。2002,14(5):1029—1046. : 夺基于位置标签与词性结合的组合词抽取方法: [4]宋青,[J].电子科技大* * * * 学学报,2012,41(2):176—184. ^ { }} } }}} } } 十} } }}十*