菜单
　　

    摘要现代意义上的最优路径已不再仅仅是指地理意义上的距离最短，它还可以是指时间最少、费用最省、线路容量最大等等。由于Dijkstra算法的本质求解单源点到所有顶点对的算法，且当其用于求解单对顶点间的最优路径时，计算必然存在冗余的问题，因此本文描述了基于规则限制的双向Dijkstra算法，该算法根据实际中的限制因素，动态的构建网络，减少了链接数量，有效提高了寻找最优路径的效率。双向Dijkstra搜索算法的效率比传统Dijkstra算法平均提高40％以上，而且图的顶点越多，效果越盟显。通过实际应用表明，该算法可以很好地满足路径选择的需要。67353

    毕业论文关键词  最优路径  Dijkstra算法  双向搜索  

    毕业设计说明书（论文）外文摘要

    Title  City Transportation shortest path problem and the  algorithm research

    Abstract

    The optimal path no longer refers to the shortest distance in the modern sense, it can also refer to the least time,the least cost,the largest line capacity and so on.The essence of Dijkstra algorithm is to solve the distance of single source and all vertices , when it is used to find the optimal path,there must be redundancy problem.So this paper a two-way Dijkstra algorithm based on the limited rule.Relying on the actual constraints the algorithm constructs a network dynamically,reduces the number of links,and improves the efficiency of finding the optimal path.The efficiency of bi-directional Dijkstra Algorithm is generally more than 40% higher than that of the traditional Dijkstra Algorithm.The more vertexes there are on the map,the higher the efficiency will be.Through practical application ,it it show that the algorithm can be selected to meet to find the optimal path.

    Keywords   Optimal Path  Dijkstra Algorithm  Bidirectional Search

                             

     目 次

    1  绪论 1

    1.1  研究意义 1

    1.2  国内外最短路径算法的发展及其概况 1

    1.3 本文研究的问题及主题 4

    2最短路径问题分析 6

    2.1最短路径问题的分类和特点 6

    2.2最短路径的搜索策略 7

    2.2.1 深度优先搜索 7

    2.2.2 广度优先搜索 7

    2.2.3 启发式搜索 7

    3  Dijkstra经典算法 9

    3.1原理 9

    3.1.1 Dijkstra算法的原理 9

    3.1.2 Dijkstra算法的基本思想与步骤 9

    3.1.3 Dijkstra算法的优缺点 11

    3.2 Dijkstra算法与其他主流算法的比较 12

    3.2.1 A*算法 12

    3.2.2遗传算法 13

    3.2.3  搜索速度比较 13

    3.2.4搜索成功率比较 14

    4  基于Dijkstra算法的改进算法的研究 16

    4.1 双向Dijkstra算法的基本思路 16

    4.2算法描述 17

    4.3 算法优化

  1. 上一篇：TOPSwitch-GX小功率开关电源设计
  2. 下一篇：Matlab含柔性输电元件的电力系统潮流算法研究和程序设计

  1. MATLAB永磁同步电机矢量控制模型与算法设计

  2. MEMS基于SHARC型DSP的组合导航算法实现

  3. 城市地铁运行阶段变形监测的方案设计

  4. ARM自动售票机城市轨道交通中的AFC系统设计

  5. AT89S52单片机的交通灯设计

  6. 城市轨道交通枢纽行人特性分析

  7. C#图像预处理算法的研究与实现

  8. 大众媒体对公共政策制定的影响

  9. 酸性水汽提装置总汽提塔设计+CAD图纸

  10. 中考体育项目与体育教学合理结合的研究

  11. 电站锅炉暖风器设计任务书

  12. java+mysql车辆管理系统的设计+源代码

  13. 十二层带中心支撑钢结构...

  14. 当代大学生慈善意识研究+文献综述

  15. 河岸冲刷和泥沙淤积的监测国内外研究现状

  16. 乳业同业并购式全产业链...

  17. 杂拟谷盗体内共生菌沃尔...

　　

About

751论文网手机版...

主页：http://www.751com.cn

关闭返回