[揭帖]2007数学建模B题论文基于广度优先算法的公交最优线路设计

ningyuangudu

总算有达人肯出来说话了 楼上很牛X啊
答案是有问题 不过也就只有第二问的第三组数据有问题(单就最短时间而言)
转乘三次，共98分钟：S0971-(等3分钟，94路上行，18分钟)->S0567-(转乘地铁，6分钟)->D1-(T1，35分钟)->D15-(转乘汽车，7分钟)->S2534-(156路上行，15分钟，转汽车5分钟)->S2210-(417路下行，9分钟)->S0485
这是我们的结果
其它的答案都对呢 我们没有异议
希望能起到一个抛砖引玉的效果 楼上贴答案吧

ssskkk

你思考过这种算法没有？？如果你没思考过就不要乱说。  这种广度优先算法的复杂度随换乘次数（n）的增加而指数增加（a.^n)，其中（n<=一个比较少的数），a是通过某个站的公交线，一般小于100条（其实我觉得题目的数据有点夸张，一个公交车站竟然通过100条线，除了公交总站之外，如果一个站有100条线通过，那你在公交站看站牌的时候一定会看晕），如果平均起来，a的值就更少，所以a.^n的结果也不会很大，算法是绝对可以满足实际要求。

yf1412

我就是用图论作的。如果不是限制换乘次数的次数的话，我们可以求出第一问第四小题的最优时间为59分钟（不考虑第一站等车的3分钟时间），不过换乘的次数比较多了，要4次换乘。不过同时我们还输出了基本上其他换乘次数的所有可能，文本文件输出大小约有400-500KB，按顺序排列，而这一切只要1秒钟不到的时间就可以完成了。所以图论是可以解决问题的。
我们做过试验了，就本题而言，可以至少换乘3次以上才能到达的任意两个站点几乎不存在。

dianslmm

本查詢系统实用中，第三问是必要的，解第三问时，要把步行看爲虚拟的公交车线路，换乘3次以上才能到达的任意两个站点是很常见的，若算法不能做到任意两个站点查詢在3秒钟內，那不会是个好方法。

CrossMan

我是楼主：

这个题结果不是最重要的，不同的数据假设和处理结果会有一定的出入，要的是思想。一问 和 二问 大家都是几乎差不多，关键是处理问题三难度较大，目前来说我还没有发现一个比较优秀的算法。我的目的在于讨论。

yf1412

第三问原题并没有问算法，只是问了建立模型。
有时候建立了模型也不见得能够用算法实现。
不过我倒是想再建立一张步行的有向图，然后再和我第一问、第二问的程序结合起来使用，可能可以解决问题。
我的第二问就是建立在我第一问的程序基础之上的。

ssskkk

其实你用图论来解，就是退化成一个最短路径问题，但你能拿这个最短路径来作为最后结果吗？在实际情况中用处不是很大（偶尔效果可能会好，但是最大的弱点是没考虑换乘次数）。所以你要把换乘次数考虑进去，就变成一个搜索所有路径然后从路径里面找最优的路径问题，如果是这样，本质上与广度优先算法一样，你仔细想想就知道。

yf1412

回复17#
其实我就是用广度优先树做的。双广度优先树。不过树中间加入了优化的概念，即根节点到树的每一个节点的路径是最优的。然后两棵树重叠起来就是路径了。
你说的换乘次数，我们组专门做过试验了。换乘存在两种情况。一种是必要换乘，就是两个点之间所必需的最小换乘次数。另一种是优化换乘，就是在必要换乘的基础上再考虑通过更多的换乘来达到时间或价格上的优化。单单考虑换乘次数是没有意义的，应该考虑必要换乘和优化换乘两者次数之比的大小问题。这就是考虑个人喜好了，比如你必须换两次车才能到，如果告诉你多换一次车可以减少一半的时间，并不是所有人都不愿意换。
还有，我已经提过了，我们输出的是多条路径表，而不是简单的一条路径。之所以提出那么一条路径只是为了方便评委比较算法的好坏而以。一般题目中的任意两个站点我们实际可以给出的路径大概有几十到上百条，只是由于不想使论文太臃肿就没有加了。
对于楼上提出的所有路径，首先就是限制死了换乘次数。而通过试验我们组发现本题的数据中任意两点大部分必要换乘次数是1至2次，但也有相当一部份是必要换乘次数是三次的（10%左右）。还有少量必要换乘次数是四到五次的。这仅仅是题目的数据 ，我们还要考虑算法的扩展性而不是自己的一厢情愿，必要换乘次数应该由对于原始数据的试验确定。而如果考虑优化换乘次数的话，那么计算量就更加可观了。呵呵，所以我想你所说的应该是在必要换乘次数的限制下来考虑路径的广度遍历，而在算任意一对点的时候是不知道必要换乘次数的，所以只能取最大的值了。
最后加一句吧，我的具体算法是图论加广度优先加模拟退火算法。

ssskkk

如果这样的话，就和我们的差不多。我们是在满足必要换乘的情况下再往上浮动1到2次换乘，然后才给出一个（几个）的优化方案。虽然这种算法并不能找出最短路径（因为不知道要加多少次换乘才达到最短路径），但是因为考虑到换乘次数的影响，我觉得比较符合实际。

深蓝世界

RE:楼上的那位,用退火算这个含步行的组合优化问题,结果不一定会好,因为就问题规模和难度而言都是可以找到在有限次转乘内都可达的路线.第三问也可归结为此(将一定范围内的站点收缩成一点,并在这样的范围内可以采用步行的策略),这样做的话问题的组合就会少很多,一定可以找到多项式时间解法,因此退火在此不一定合适.你不妨用你的算法给出一对顶点的特例,我们来看看结果到底如何,针对弟三问在本版中我们也给出一组特例你可以和我们的相比一下