遗传算法和Dijkstra算法在动态权值系统中的比较

摘要：

针对遗传算法和Dijkstra算法在求解动态权值系统中最短路径时的性能问题,采用比较法,将两种算法应用在同一个实际游戏模型中,对其算法的稳定性、智能性、时间复杂度进行对比测试.游戏模型模拟了各种条件下的动态权值系统.为了使遗传算法更加可靠,通过优化其变异过程使得收敛速度更快,可靠性更高.实验数据表明,遗传算法在每张地图上的得分数以及算法所用时间普遍高于Dijkstra算法,从而得出遗传算法在求解动态权值系统中最短路径问题时稳定性和预期效果明显好于Dijkstra算法,但其时间复杂度较高的结论.

关键词：遗传算法、Dijkstra算法、最短路径、动态权值

所属期刊栏目：22

分类号：TP301.6(计算技术、计算机技术)

资助基金：陕西省科技攻关项目2009k01-53

在线出版日期：2013-01-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：21-24,28