交通运输网络的最短路线问题theshortestpathproblemoftransportationnetwork(附
摘 要摘 要最短路问题（shortest-path problem）若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。最短路径问题是图论解决的典型问题之一，可用来解决交通运输、管路铺设、线路安装、厂区布局和设备更新等实际问题。遗传算法，核心是达尔文优胜劣汰适者生存的进化理论的思想。在运用遗传算法时，我们先随机创造很多很多的解，然后找一个靠谱的评价体系，去筛选适应性高的解，再用这些适应性高的解衍生出更好的解，然后再筛选，再衍生。反复迭代一定次数，可以得到近似最优解。本文介绍了图论最短路径问题及遗传算法，并应用图论最短路径问题的分析方法，运用遗传算法，解决仓库选址的问题。 本文分四个部分来讨论 第一部分阐述交通运输网络的研究背景及意义； 第二部分介绍最短路径问题的基本思想及算法； 第三部分介绍遗传算法及其图论模型； 第四部分应用遗传算法实现最短路问题。关键词赋权图；最短路线；遗传算法
目 录
第一章 绪论1
1.1 研究背景1
1.2 交通运输最短路线问题研究意义1
1.3 交通运输最短路线问题国内外研究现状与发展1
1.4 本文的主要内容2
1.5 研究方法3
第二章 预备知识4
2.1 图的概念4
2.2 最短路问题4
2.2.1 交通运输模型问题的引入 4
2.2.2 最短路径问题5
2.2.3 最短路问题算法的基本思想及基本步骤5
第三章 遗传算法8
3.1 遗传算法的基本步骤8
3.2 适应函数10
3.3 遗传算法的应用11
结论15
致谢16
参考文献17
第一章 绪论
1.1 研究背景
最短路问题的研究在上个世纪60年代以前就卓有成效了,求解网络图上节点间最短路径时,目前国内外一致公认的较好算法有Dijkstra算法和Floyd算法。1959年，荷兰著名计算机专家迪杰斯特拉对赋权图的问题首次提出有效算法即Dijkstra算法,该算法能够解 *好棒文|www.hbsrm.com +Q: *351916072*
决两指定点间的最短路,也可以求解图中一特定点到其它各顶点的最短路。但这种算法并不能解决含有负权的图的最短路问题。因此Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。1975年美国Michigan大学J.Holland教授提出了遗传算法（Genetic Algorithm），并且出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》。遗传算法是一种模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是通过模拟自然进化过程搜索最优解的方法。遗传算法是一种通用的算法框架，有很强的适应性，可以忽略具体条件，得到近似最优解。
1.2 交通运输最短路线问题研究意义
最短路径的算法问题是图论中的核心问题之一，也是许多更深层次算法的基础。同时，最短路问题有着大量的实际运用的背景。最短问题与很多问题从表面上看并没有什么关系，但这些问题也可以归结为最短路问题。例如：线路安装、管路铺设、厂区布局和设备更新等实际问题。在更加注重效率的现在，如何快速的实现一些问题，诸如：必要的道路交通网，消防选址的高效性，企业生产的节约成本，网络数据传输的减少能耗，灾难发生时的快速逃生，抓捕罪犯时的最佳路线选择等问题。最短路问题作为这些问题的基础，可以作为一个参考。比如，可以利用最短路问题算出逃生时的最短路线，这样在灾难发生时，可以直接利用最短路线快速逃生，挽救更多生命。
1.3 交通运输最短路线问题国内外研究现状与发展
最短路径问题是图论研究中的一个长盛不衰的经典问题，它旨在寻找图中指定两结点间的最短路径。国内外大量专家学者都对此问题进行了比较深入的研究。
寻找最短路径就是：给出了一个连接若干个点的网络，在这个网络的两个指定点之间，找一条最短路径。最短路径不仅可以指一般物理意义上的距离最短,还可以引申到其它的度量,比如：费用、时间、线路容量等。最短路径算法的选择问题与实现问题是路线设计的基础问题,最短路径算法则是计算机科学与地理信息科学等领域的研究热点,很多与网络相关的问题都可以纳入最短路径问题的范畴中。
目 录
第一章 绪论1
1.1 研究背景1
1.2 交通运输最短路线问题研究意义1
1.3 交通运输最短路线问题国内外研究现状与发展1
1.4 本文的主要内容2
1.5 研究方法3
第二章 预备知识4
2.1 图的概念4
2.2 最短路问题4
2.2.1 交通运输模型问题的引入 4
2.2.2 最短路径问题5
2.2.3 最短路问题算法的基本思想及基本步骤5
第三章 遗传算法8
3.1 遗传算法的基本步骤8
3.2 适应函数10
3.3 遗传算法的应用11
结论15
致谢16
参考文献17
第一章 绪论
1.1 研究背景
最短路问题的研究在上个世纪60年代以前就卓有成效了,求解网络图上节点间最短路径时,目前国内外一致公认的较好算法有Dijkstra算法和Floyd算法。1959年，荷兰著名计算机专家迪杰斯特拉对赋权图的问题首次提出有效算法即Dijkstra算法,该算法能够解 *好棒文|www.hbsrm.com +Q: *351916072*
决两指定点间的最短路,也可以求解图中一特定点到其它各顶点的最短路。但这种算法并不能解决含有负权的图的最短路问题。因此Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。1975年美国Michigan大学J.Holland教授提出了遗传算法（Genetic Algorithm），并且出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》。遗传算法是一种模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是通过模拟自然进化过程搜索最优解的方法。遗传算法是一种通用的算法框架，有很强的适应性，可以忽略具体条件，得到近似最优解。
1.2 交通运输最短路线问题研究意义
最短路径的算法问题是图论中的核心问题之一，也是许多更深层次算法的基础。同时，最短路问题有着大量的实际运用的背景。最短问题与很多问题从表面上看并没有什么关系，但这些问题也可以归结为最短路问题。例如：线路安装、管路铺设、厂区布局和设备更新等实际问题。在更加注重效率的现在，如何快速的实现一些问题，诸如：必要的道路交通网，消防选址的高效性，企业生产的节约成本，网络数据传输的减少能耗，灾难发生时的快速逃生，抓捕罪犯时的最佳路线选择等问题。最短路问题作为这些问题的基础，可以作为一个参考。比如，可以利用最短路问题算出逃生时的最短路线，这样在灾难发生时，可以直接利用最短路线快速逃生，挽救更多生命。
1.3 交通运输最短路线问题国内外研究现状与发展
最短路径问题是图论研究中的一个长盛不衰的经典问题，它旨在寻找图中指定两结点间的最短路径。国内外大量专家学者都对此问题进行了比较深入的研究。
寻找最短路径就是：给出了一个连接若干个点的网络，在这个网络的两个指定点之间，找一条最短路径。最短路径不仅可以指一般物理意义上的距离最短,还可以引申到其它的度量,比如：费用、时间、线路容量等。最短路径算法的选择问题与实现问题是路线设计的基础问题,最短路径算法则是计算机科学与地理信息科学等领域的研究热点,很多与网络相关的问题都可以纳入最短路径问题的范畴中。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/jsjkxyjs/743.html
