[1]孙强 戴志军.用元胞自动机求最短路径的一种新算法[J].计算机技术与发展,2009,(02):42-44.
　SUN Qiang,DAI Zhi-jun.A New Shortest Path Algorithm Using Cellular Automata Model[J].,2009,(02):42-44.
点击复制

用元胞自动机求最短路径的一种新算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2009年02期
页码:
42-44
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
A New Shortest Path Algorithm Using Cellular Automata Model
文章编号:
1673-629X（2009）02-0042-03
作者:
孙强1 戴志军2
[1]华东师范大学计算机科学技术系[2]华东师范大学河口海岸科学研究院
Author(s):
SUN Qiang1; DAI Zhi-jun2
[1]Department of Computer Science and Technology, Fast China Normal University[2]Institute of Estuary and Coastal Research, East China Normal University
关键词:
元胞自动机; 最短路径算法; 减最小剩余权; 省略
Keywords:
cellular automata;  shortest path algorithm;  subtraction of the smallest surplus weight;  leave out
分类号:
TP311
文献标志码:
A
摘要:
在一个基于元胞自动机模型的求图中一个顶点到另一个顶点的最短路径的算法的基础上。分析出：它的关键部分（即演化规则）中“减最小剩余权”这一重要步骤与求图中一个顶点到另一个顶点的经典的最短路径算法的基本思想相距甚远，应该省去。在提出的新算法中省去“减最小剩余权”这一重要步骤，这个改进较大地提高了算法的效率。最后通过举例子分别用两个算法进行求解，通过这些求解步骤的对比，明显看出本算法的正确性和高效性。
Abstract:
On the base of one shortest path algorithm from one point to another point in a graph based on cellular automata model, it is pointed out that its critical step of ＂subtraction of the smallest surplus weight＂ in evolurion rule of the algorithm is far from

相似文献/References:

[1]王佳佳 李青 周美莲.基于元胞自动机的股票市场价格行为的研究[J].计算机技术与发展,2008,(09):187.
　WANG Jia-jia,LI Qing,ZHOU Mei-lian.Study on Price Behavior of Stock Markets with Cellular Automata[J].,2008,(02):187.
[2]王裕青 周美莲 李青.模拟驾驶行为的元胞自动机交通流模型[J].计算机技术与发展,2008,(09):248.
　WANG Yu-qing,ZHOU Mei-lian,LI Qing.A Cellular Automaton Model for Traffic- Flow Based on Driving Behaviors[J].,2008,(02):248.
[3]陈益富 卢潇 丁豪杰.对Dijkstra算法的优化策略研究[J].计算机技术与发展,2006,(09):73.
　CHEN Yi-fu,LU Xiao,DING Hao-jie.Optimized Strategy Research over Algorithm of Dijkstra[J].,2006,(02):73.
[4]陈育 陶平 张小英.大型商场人员安全疏散的计算机仿真研究[J].计算机技术与发展,2010,(10):211.
　CHEN Yu,TAO Ping,ZHANG Xiao-ying.Computer Simulation Research of Safety Evacuation Property in Super Shopping Mall[J].,2010,(02):211.
[5]杨奎奇 赵青 汪应宏.基于元胞自动机的中尺度交通模拟——以徐州市为例[J].计算机技术与发展,2011,(02):219.
　YANG Kui-qi,ZHAO Qing,WANG Ying-hong.Middle-Sized Dimension Traffic Flow Simulation Based on CA——Taking Xuzhou City for Instance[J].,2011,(02):219.
[6]肖勇杰 封卫兵 晁媛.基于LBM算法的大规模人群疏散研究[J].计算机技术与发展,2011,(07):21.
　XIAO Yong-jie,FENG Wei-bing,CHAO Yuan.Large-Scale Flow Evacuation Research Based on Lattice Boltzmann Method[J].,2011,(02):21.
[7]任环 蒋国平 胡海宏.考虑交通流量的SIR-CA病毒传播模型[J].计算机技术与发展,2011,(08):250.
　REN Huan,JIANG Guo-ping,HU Hai-hong.A SIR-CA Model for Epidemic Propagation Considering Traffic Flow[J].,2011,(02):250.
[8]康振环 王化雨.基于二维元胞自动机的图案设计方法研究[J].计算机技术与发展,2012,(01):111.
　KANG Zhen-huan,WANG Hua-yu.Design of Pattern Based on Two-Dimensional Cellular Automata[J].,2012,(02):111.
[9]张英辉,张水平,张凤琴,等.基于OpenStreetMap最短路径算法的分析与实现[J].计算机技术与发展,2013,(11):37.
　ZHANG Ying-hui,ZHANG Shui-ping,ZHANG Feng-qin,et al.Analysis and Implementation of Shortest Path Algorithm Based on OpenStreetMap[J].,2013,(02):37.
[10]张俊溪[],杨海粟[]. 基于层次聚类的离群点分析方法[J].计算机技术与发展,2014,24(08):80.
　ZHANG Jun-xi[],YANG Hai-su[].Outlier Analysis Method Based on Hierarchical Clustering[J].,2014,24(02):80.

备注/Memo

备注/Memo:
国家自然科学基金资助(40771200)孙强(1963-)，男．安徽合肥人,副教授，硕导，主要从事软件与算法研究；戴志军，副教授，硕导，主要从事河口海岸研究。
更新日期/Last Update: 1900-01-01