Dijkstra算法地铁站台出口路径的选择研究(3)
时间:2018-05-08 10:31 来源:毕业论文 作者:毕业论文 点击:次
由于地铁站台的种类繁多，所使用的结构都有所不同，不同的车站设计的也有所不同，虽然有路标指示，但是对于不熟悉该站的乘客来说，特别是对于像人民广场这样的大站，想要方便、直接的找到自己想要到达的出口还是有困难的。研究本课题的首要目的就在于此，为了方便乘客一目了然的找到一条最便捷的到达目的地的出口的路线。 而对于老人、孕妇、残障人士以及带大件行李的乘客来说，普通的路线可能就不适合他们，需要辅助自动扶梯或者升降电梯来方便出行。对于坐轮椅的人来说，更需要一条特殊的通道来通行。如何找到这些有特殊需要的路线，这就是研究本课题的第二个目的。 如果遇到故障或者突发状况时，比如升降梯坏了或者自动扶梯坏了，突发火灾等各种特殊情况，如何重新选择一条路线就变的尤为重要。在这样的状况下提供另外的安全线路就是本课题研究的目的所在。 1.2 国内外研究现状和水平 1.3 发展趋势 1.4 本文的研究内容 本课题是地铁站台出口路径的选择，本文主要研究的是地铁站台的在不同情况下的最短路径选择，通过分析地铁站台的站台情况（其中包括车厢信息，楼梯、自动扶梯、电梯信息，闸机信息，出口信息），结合最短路径算法研究出适合地铁站台出口路径选择的合适的最短路径算法，让乘客可以在正常、特殊和突发情况下可以选择合适的最短路径情况。 1.5 本文安排 本文一共分成6个章节，第一章是绪论，主要讲述了课题的目的和意义，国内外研究现状和水平以及课题的发展趋势。第二章是最短路径算法的介绍，分析了几种最短路径算法，讲述了选择Dijkstra算法的原因，然后具体讲述了Dijkstra算法。第三章是系统设计，主要讲述了整个课题的设计思路。先分析了本课题的重点和难点，然后讲述了设计的思路，数据库的设计和程序的设计。第四章是系统实现，主要讲述了系统是如何实现的，分析介绍主要的一些算法的实现。第五章是系统测试，模拟系统的使用过程，测试系统的功能。第优尔章是总结和展望，总结了这几个月来得到的时候和体会，以及希望弥补的程序的不足之处。 2 最短路径算法 2.1 最短路径算法概念[10] 最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括： 确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。 全局最短路径问题 - 求图中所有的最短路径。 2.2 几种最短路径算法的比较[14] 用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法。 最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 2.2.1 Floyd[7] 求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V^3)。 Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。 (责任编辑：qin) |