最优公交车选乘问题的算法分析及实现

摘要

本论文主要针对三个公交车换乘问题建立了合理的图模型然后设计了高效的算法，通过应用这些算法设计并实现了一个公交车查询系统。
　　 本文充分考虑了用户的需求，分别以最短路径（即最小时间）、最少换乘、最小费用三个目标函数提出了三个算法问题，然后针对这三个问题建立了图模型，通过对不同问题的性质和结构的分析，提出了一些图模型上数据压缩的方法。然后在这些图模型上设计了高效的算法，同时对这些算法进行了时间复杂度分析。对于最短路径问题，本文直接建立图上的最短路径模型，并用Dijkstra算法进行求解。对于最少换乘问题，本文建立了两个模型，一个是用车次最为顶点集建立的图模型，通过特殊赋值来得到一个最短路径问题，另一个则是用连接接矩阵的连乘来表示的连通性质的模型。对于最小费用问题，本文可以使用前面两个问题建立的相同模型，只是在边上赋的值不同，两个站点间的边的权值则为这两个站点间直达的最便宜公交车费用，这样，在建立的图模型下本文也仅仅只需要使用用Dijkstra算法进行一个最短路径问题的求解即可。
　　 最后本文设计并实现了一个公交车换乘系统，该系统采用B/S结构，而前台界面主要使用了Extjs库与HTML相结合的技术实现，后台数据库则用的是SQLSEVER2000。该系统拥有一般客户和管理员两个角色，一般客户能在不需要登录的情况下直接进行站点查询、线路查询、站站查询等，其中站站查询要求输入两个站点，然后根据上面提到的三个目标最短路径、最少换乘、最小费用查询两个站点间的最优乘车路线。而管理员则能对数据库里的车次、车站等信息进行更改等。