三、问题的分析
在对题目的分析的基础上,我们认为要满足不同需求的查询者对于公交线路的选择,
就要求我们在模型中解答各种不同需求。从实际出发考虑我们认为:查询者的主要需求
有以下几点:
首先是乘车的时间。交通工具是为公众提供便利,本模型服务的系统也是为观看奥
运而设计的,所以乘车时间就是本模型要考虑的最主要的因素。
其次是乘车的费用。不同的公交线路为乘客服务的费用在实际情况中是不相同的,
为乘客提供最少花费也是本模型设计的目的。
最后是换乘的次数。换乘虽然不能代表最少的乘车时间以及最小的乘车花费,但是
可以在最大程度上统一以上两个条件。所以本模型选择换乘次数作为模型的初次优化的
条件。因为在实际的情况中,换乘少不一定带来时间以及金钱的花费最少,而且公交线
路的设计规范要求一套网点内的任意两个站点都可以在换乘两次车以内达到。所以本模
型选者在要求换乘次数最少的情况下,适当的放松换乘次数的限制,在此同时要求换乘
的次数不要超过两次。
所以我们将所有的问题都转化为首先找到所有的换乘次数最少的情况下所有的线
路以及在换乘次数小于2的情况下,将换乘的次数加一之后的所有线路。在这些线路中
输出对于时间优先考虑的情况下,价格最少的线路;以及在价格优先考虑的情况下,时
间最短的线路。
3.1 第一问的分析
对于第一问,我们的模型I用广度优先搜索模型,使用换车次数作为搜索的步长,
给定换车的次数的初始值(一般为0),判定是否满足条件(能从起点到达终点),如果
满足则作标记,并且停止搜索。否则增加换车的次数,再判断,直到不满足限制条件。
比较不同换车次数的线路沿途停靠站点的多寡,停靠站点最少的线路为最优解。在换车
次数很少的情况下,广度优先算法的运算速度快,若换车次数大于一次,则需要很长的
时间才能得出结果,因此对模型进行了如下的优化,提出了模型II。
我们将整个公共汽车的交通网络信息整理成为一个有向图,其中的每一个结点代表
一个公共汽车站,每一个有向弧代表一个可以指经过一站就可以到达的该弧连接的两个
相邻的公共汽车站得公交线路号码。我们把根据换乘次数不同把有向图分成若干个层。
这样我们就可以知道我们的目标结点(目的地所在的结点)最少需要几次可以换乘达到。
同时此模型也可以在起点和终点同时分层搜索整个有向图。此模型能够找出任意两
点之间需要换乘的最小次数。从而避免了为不同换乘次数而设计不同的算法,在运算速
度上也得到很大的提高,具有更低一级的时间复杂度。特别是在高于一次换乘的运算中
较广度优先算法所需时间很短。我们称经过模型II为可双向搜索的分层拓扑结构模型。
因为模型II可以对于整个交通图可以在找到最少换乘之后继续增加换乘次数,那么
对于目标点指定换乘的模型改造就变得异常的简单。因为在多次换乘有可能会带来更快
的结果。所以我们模型II得出结论在运算速度以及灵活性上比较其他方法有巨大的优势。
3.2 第二问的分析
对于第二问,我们再加入地铁之后分析乘客在出行的时候的主要有两种选择。其一,