用启发式算法求解最短路径问题

吉林大学学报(工学版) ›› 2011, Vol. 41 ›› Issue (01): 182-0187.

用启发式算法求解最短路径问题

李雄飞,张海龙,刘兆军,王仁彪

吉林大学计算机科学与技术学院,长春 130012

收稿日期:2008-09-25 出版日期:2011-01-01 发布日期:2011-01-01
通讯作者: 刘兆军（1973-）,男,讲师.研究方向:数据库与智能网络.E-mail:zhaojun@jlu.edu.cn E-mail:zhaojun@jlu.edu.cn
作者简介:李雄飞（1963-）,男,教授,博士生导师.研究方向:数据库与智能网络.E-mail:lxf@jlu.edu.cn
基金资助:
“十一五”国家科技支撑计划重大项目(2006BAK01A33)

Problem for shortest path problem based on heuristic algorithm

LI Xiong-fei, ZHANG Hai-long, LIU Zhao-jun, WANG Ren-biao

College of Computer Science and Technology, Jilin University, Changchun 130012, China

Received:2008-09-25 Online:2011-01-01 Published:2011-01-01

摘要/Abstract

摘要：

提出了一种带有启发信息的邻接表结点存储结构模型，给出了结点间权值计算的具体评判函数，依据评判函数值优化邻接表中节点的相对位置。基于最短路径问题提出了带有启发信息的遗传算法思想，将启发信息加入到了初始种群生成过程中，提出了新的交叉方法。通过模拟仿真得到了算法的性能参数,并将本文算法和Dijkstra算法进行比较，结果表明，在求解数据规模比较大的最短路径问题时，本文算法具有更高的执行效率。

关键词: 计算机应用, 最短路径, 遗传算法, 启发信息, Dijkstra算法

Abstract:

An adjacency list storage model with heuristic information is proposed. An evaluation function to calculate the weight among nodes was derived. The relative position of the node in the adjacency list was optimized using the evaluation function. The process of initial population with heuristic information and chromosome coding, and the strategy of dynamic adjustment of the fitness function were presented. The main performance parameters were obtained by simulation, and the proposed algorithm was compared with the Dijkstra algorithm. Experiment results show that the proposed algorithm possesses higher efficiency when solving the optimization problem of shortest path with high spatial complexity.

Key words: computer application, shortest path, genetic algorithm, heuristic information, Dijkstra algorithm

中图分类号:

TP391.3

李雄飞,张海龙,刘兆军,王仁彪. 用启发式算法求解最短路径问题[J]. 吉林大学学报(工学版), 2011, 41(01): 182-0187.

LI Xiong-fei, ZHANG Hai-long, LIU Zhao-jun, WANG Ren-biao. Problem for shortest path problem based on heuristic algorithm[J]. 吉林大学学报(工学版), 2011, 41(01): 182-0187.

参考文献

相关文章 15

[1]	吴蔚楠,崔乃刚,郭继峰,赵杨杨. 多异构无人机任务规划的分布式一体化求解方法[J]. 吉林大学学报(工学版), 2018, 48(6): 1827-1837.
[2]	刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[3]	王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[4]	金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[5]	赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[6]	刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[7]	焦玉玲, 张鹏, 田广东, 邢小翠, 邹连慧. 基于多种群遗传算法的自动化立体库货位优化[J]. 吉林大学学报(工学版), 2018, 48(5): 1398-1404.
[8]	欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[9]	刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[10]	桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[11]	刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[12]	车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[13]	赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[14]	黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[15]	傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed