用元胞自动机求最短路径的一种新算法

• 作者: 孙强 戴志军
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 元胞自动机 最短路径算法 减最小剩余权 省略
• 年，卷（期）: 2009,（2）
• 所属期刊栏目: 智能、算法、系统结构
• 页码范围: 42-44
• 页数: 3页
• 分类号: TP311
• 字数: 2472字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2009.02.012

摘要

在一个基于元胞自动机模型的求图中一个顶点到另一个顶点的最短路径的算法的基础上,分析出:它的关键部分(即演化规则)中"减最小剩余权"这一重要步骤与求图中一个顶点到另一个顶点的经典的最短路径算法的基本思想相距甚远,应该省去.在提出的新算法中省去"减最小剩余权"这一重要步骤,这个改进较大地提高了算法的效率.最后通过举例子分别用两个算法进行求解,通过这些求解步骤的对比,明显看出本算法的正确性和高效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	戴志军	华东师范大学河口海岸科学研究院	77	808	17.0	23.0
2	孙强	华东师范大学计算机科学技术系	37	308	10.0	16.0