求解关键路径的元胞自动机算法

• 来源期刊: 陕西师范大学学报（自然科学版）
• 学科: 工学
• 关键词: 元胞自动机 边表示活动网 关键路径
• 年，卷（期）: 2009,（6）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 19-22
• 页数: 4页
• 分类号: TP301.6
• 字数: 2725字
• 语种: 中文

摘要

利用元胞自动机的离散空间与并行计算特性,通过对元胞的抽象和局部规则的设计,借助于元胞状态的动态演化,解决了AOE网络(Activity on edge network)中多源点多汇点关键路径的求解,消除了基于拓扑排序和逆拓扑扫描的传统算法的线性化过程,并从算法上实现了AOE网最短路径与关键路径求解的统一.