公交查询系统的数学模型(3)

公交查询系统,07年全国赛B题

．５５６．黑龙江大学自然科学学报第２５卷车毛，从彳到Ｙ有直达车ｔ，按照直达车算法分别得站点数为ｃ。和ｃ。，用ｑ表示从Ｌ。转到厶的一次转车到达的总站数，则有

ｑ＝ｃＩ＋ｃｉ，（，＝１，２，３，…，ｒ）

所经站点总数最少为

ｃ：＝ｍｉｎ｛ｃ：，砭，…，Ｃ：｝

计算出相应的费用ｈ和ｒ…总费用为刊

最少费用为＝ｋ＋－（Ｊ＝１，２，…，ｒ）．

Ｒ：＝ｍｉｎ｛尺：，Ｒ；，…，Ｒ：｝

２．３两次转乘算法

若Ｑ，ｎＭｙ＝中，则此时至少要转两次车才可以到达终点，记Ｑ，为与鸠中的各条线路相交的线路的集合。

由假设，Ｑ，ｎＱ，≠中．对于Ｑ，ｎＱ，中的任意一条线路厶，则在鸩中至少存在一条线路厶与其相交，同样在Ｍ，中至少存在一条线路乙和厶相交，这样毛＋厶＋厶便是一个可行线路的组合。

假设有ｓ种这样的组合，类似一次转乘，求出厶和厶的第一个交点ｅ，Ｌｊ与ｋ的第一个交点，这样就相当于从戈到ｅ有直达车厶，从ｅ到，有直达车厶，从厂到Ｙ有直达车厶．

按照转一次车算法求出ｔ，Ｌ。，厶线路中相应的站点数Ｃ＾，ｃ；，ｃ。和费用“，ｒｉ，“．

按照ｃ；＝ｃ。＋ｃｉ＋ｃ。（Ｊ＝１，２，…，ｓ）计算出二次转车各种可行线路组合要经过的站点数，求出

ｃ：＝ｍｉｎ｛ｃ；，谚，…，ｃ：｝

则第ｍ种可行线路组合便是换乘两次时路程较短的线路。

利用Ｒ；＝“＋－＋ｈ（Ｊ＝１，２，…，ｓ）求出各种可行线路组合所需费用。

求出Ｒ：＝ｍｉｎ｛Ｒ；，尺；．…，碍｝就是相对比较省钱的线路组合。

利用ＶＢ编制可视化程序，实现查询结果，在可视化窗ｌＹｌ中只需输入起点站和欲到达站，便可根据查询者不同的要求给出相应的结果。

下面以北京公交线路为例，选取６组站点，运用此算法实现查询结果如下（其中耗时栏含等车时间３ｒａｉｎ）：

表１一次换乘最优路线

Ｔａｂｌｅ１ＯｐｔｉｍｕｍｒｏｕｔｅｗｉｔＩｌｏｎｅｔｒａｎｓｆｅｒ

表２二次换乘最优路线

Ｔａｂｌｅ２Ｏｐｔｉｍｕｍｒｏｕｔｅｗｉｔｈｔｗｏｔｒａｎｓｆｅｒ

３模型评价

针对本文的问题，如用Ｄｉｊｋｓｔｒａ标号法，把站点看成节点，把公交线路看成连接节点的路径，可以找到从起点ｚ到终点Ｙ的最短站点距离的线路，但Ｄｉｊｋｓｔｒａ标号法找线路时没有考虑有几个转折点的问题，即最后找到的线路可能路径较短，但要转很多次车；另外Ｄｉｊｋｓｔｒａ算法在节点数量较多的情况下计算的时间成倍甚至幂次增长【卜８｜，这就脱离了实际。一文中算法将对站点的搜索转化为对线路的搜索，从而将上万个数据的处理优化为对５００多个数据的处理，大大缩短了运算时间。不仅如此，而且更符合乘客的查询要求（线路）。经检验输入起点与终点，结果查询运算时间不超过３０ｓ。同时，所得结果必为由起点到终点的路径。在转车

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新资格考试认证公交查询系统的数学模型(3)全文阅读和word下载服务。