元胞自动机最短路径算法优化_任志国

《元胞自动机最短路径算法优化_任志国》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1007-4619(2015)01-0108-08JournalofＲemoteSensing遥感学报元胞自动机最短路径算法优化任志国，郭健，李爱光，王卉，阚映红信息工程大学测绘学院，河南郑州450052摘要:概括了当前GIS中最短路径算法，分析了元胞自动机在最短路径分析算法中的原理及应用现状，并从两个*方面对基于元胞自动机的最短路径算法进行优化即直线优化的元胞自动机最短路径算法。(1)将A算法中的启发函数引入元胞自动机模型，提出了直线优化元胞自动机最短路径模型;(2)考虑道路网特征对最短路径算法的影响，得出具有道路网自适应性的最短路径分析模型。最后选取不同形态特征的shp道路

2、网数据，验证了优化算法在实际应用中的适用性和高效性。*关键词:元胞自动机，A算法，直线优化，道路网特征，启发式搜索中图分类号:TM344．1文献标志码:A引用格式:任志国，郭健，李爱光，王卉，阚映红．2015．元胞自动机最短路径算法优化．遥感学报，19(1):108－115ＲenZG，GuoJ，LiAG，WangHandKanYH．2015．Optimalpathalgorithmenhancementbasedoncellularautomaton．JournalofＲemoteSensing，19(1):108－115［DOI:10．11834/jrs．20153129］1

3、引言索方式。目前公认的最短路径算法有Dijkstra算法和Floyd算法，尤其是Dijkstra算法，自1995年被提最短路径问题是计算机科学、地理信息系统和出以后产生了许多优化算法，如TQQ(Graphgrowth运筹学等学科研究的热点问题，其目的是研究、筹withtwoqueues)、DKA(theDijkstra'salgorithmimple-划一项网络工程该如何安排而使其运行效果最好，mentedwithapproximatebuckets)、DKD(theDijkstra's如制定一个从A地到B地运行时间最短或者运输algorithmimplementedwithd

4、oublebuckets)、相关边、费用最低的运输方案等(邬伦等，2001)。同时，日邻接节点、FIFO优先级队列、二叉堆和DIKB趋严峻的交通问题使得智能交通系统(ITS)思想应(Dijkstra'salgorithmimplementedwithbuckets)等。运而生，路线优化子系统虽在ITS应用中占有举足许多算法基于这些基本算法演化而来，在不同轻重的作用，但仍处于薄弱环节，路径分析功能也的系统、应用中建立相应的模型，很大程度上已经不强。如常见的交通调度系统中，最短路径分析模满足了现在的应用需求。但是，随着基础数据量和块主要是实现对最优路径的规划，而没有较为全面数据维度

5、的增加、应用需求的多样化发展，传统算地分析出沿路的交通设施和社会情况等，而这些应法已经难以满足这些要求，需要探索新的计算方法用正是我们需要进一步考虑的问题。因此，完善来解决这些问题。GIS最短路径问题具有重要的意义。近年来，计算机数据处理技术的发展为实现海学者针对最短路径问题展开了广泛而深入的量、多维、多源、异构数据的集成与融合提供了手研究，尤其在最短路径算法方面取得了一系列成段;高性能计算技术的发展为求解多维空间模型提果，它们在空间复杂度、时间复杂度、易实现性及应供了新契机。在算法层次上，智能计算方法的应用用范围等方面各具特色。目前，针对图的搜索策略使最短路径的分析过程实现了

6、从盲目搜索到启发主要有深度优先搜索、广度优先搜索和启发式搜式搜索的发展。目前，在最短路径分析中使用较多索，此外还有迭代法、动态规划和标号法以及神经的智能算法有神经网络、遗传算法和蚁群算法等。网络法等。鉴于3种主要搜索策略的不同特点，在元胞自动机作为一种高效的并行算法，在地学领域地理网络搜索、GIS路径分析中主要采用启发式搜(如城市规划、土地扩张等方面)的应用取得了良好收稿日期:2013-06-06;修订日期:2014-03-17;优先数字出版日期:2014-03-24第一作者简介:任志国(1986—)，男，硕士，现从事GIS空间分析和应用研究。E-mail:superrzg@1

7、63．com任志国等:元胞自动机最短路径算法优化109效果(黎夏等，2007)，如基于约束条件的元胞自动以无向图G(图1)为例，构造CA模型:A=(d，机土地利用规划布局模型成功地模拟了广西东兴S，N，f)，式中:元胞空间d={v1，v2，…，vn};元胞vx市的变化并进行了预测(杨小雄等，2007)。在最短邻居为N(vx)={(vx，v)∈E∨(v，vx)∈E∨v=vx}。路径分析中也有很大的应用前景。本文在总结道路最短路径算法建立的关键是制定元胞的演化网特征的基础上，借助元胞自动机强大的