图论cumcm例 课件.pptVIP

模型的假设 对”最优”的理解有三个具有代表性的指标： 时间最短 花费最少 最方便（换乘次数最少） 不同的人群对最优的理解不同,需要根据实际定义.可以根据需要定义代价函数,三个指标的权重不同,代价值也不同。 以时间最短为例 模型的建立 G=(V,E) 每个车站：G的顶点 每条公交线路相邻两点的连线：G的边 边的权重：耗费时间 点的权重：换乘时间 并不是一个简单图，两点间可能有多条边 2007年 B题：乘公交，看奥运 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。 特点：1、站点8千多个，线路500多条 2、分换乘次数、坐车时间、坐车费用、坐车距离等角度考虑最优 3、有公汽和地铁一起考虑的问题 (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑公汽与地铁线路，解决以上问题。 3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。 审题：从特点看，有了一定的眉目，一个一个来，不要搞一个模型解决所有问题！ 不要盲目动，可以考虑第一个特点，8000多个站点作为图的顶点，用邻接矩阵来处理，运算了做个稍微估计，发现确实大（每得到一个想法想一下是否还有另一种方法）， 头脑灵活的同学会想到是否可以将线路作为图的顶点，这样矩阵的阶就只有500多阶！！！ 这两种想法暂且都保留意见，因为不知道后面的条件加上以后运用时哪个更复杂。 考虑第二个特点，角度很多，先只拿一个来分析！ 就考虑换乘次数吧， 这时如果用线路作为顶点来考虑，问题来了，因为原问题是考虑站点到站点间的换乘情况！ 别急于否定，站点是在线路上的，起始站 所在线路的集合记为S1，终到站所在线路的集合记为S2，在S1中任取一个线路作为起点， S2中任取一个线路作为终点（图：线路作为顶点，某线路可以换乘另一线路表示有边连接）（这里考虑仔细点的话可能是有向图），考虑换乘次数的话，边上权全取1，这时求最短路径就是行了。 麻烦的是这里手动编程得到图的信息的部分比较多！ 仔细考虑有新问题，这里的两条首尾相接的边 是否构成道路，也就是这两次换乘是否在现实生活中可行，比如 如果 与 在线路 中如果不是 在 前就不能换乘。这里 与 是站点。 因为线路有上行线与下行线之分！！ 仔细考虑，发现就算这样也不会影响计算最短路径，也就是路必须要加上这里的条件才成，但不影响计算，这个有兴趣的同学可以证明一个定理出来，这对建模来说当然是最好不过的事。 那考虑一个难点的，时间吧。 这时是否用线路作为顶点仍然可行呢？ 这时的图：线路作为顶点，某线路可以换乘另一线路表示有边连接，但是权这时是时间，但也许这两条线路可能有一段距离是雷同的，也就是换乘可以随意，也可能先在一个站点可以换乘，一段时间后又到某一站点可以换乘，这时处理成重边（即两点之间有多条边），权的处理要复杂点， 无前继和无后继的点处理成站点，把上面图边变成点，边能首尾相接表示有边连接，得下面图。 再来一个特点就是地铁的增加，这时就是要处理好地铁站点与地面站点之间的关系，这个对换乘次数没有影响，对时间当然有影响，可以依上类似处理，把走路的时间加入到相应的边上就可以了。 其他的比如说乘车费用和乘车距离等等在此不再罗列 如果我们同学能够克服这样一些一层层的障碍，比用站点作为顶点的图论处理要好很多。 下面写下传统做法： 问题的提出 2007CUMCM B题 乘公交，看奥运 给定若干条公交线路，以及在每条公交线路中任意相邻的两站之间所花费的时间。 并且给定乘客在任意站点换乘的耗时 要求给出任意两公汽站点之间线路选择问题的一般数学模型与算法，求出最佳的公交线路. 5 9 3 7 a c b(8)