初中历史形成性结论总结

公交转车问题南京邮电大学理学院杨振华制作[e-mail]南京邮电大学数理学院杨振华制作[e-mail]公交转车问题针对市场需求，某公司准备研制开发一个解决北京市公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。公交：指公共交通工具，包括公共汽车与地铁。南京邮电大学数理学院杨振华制作[e-mail]公交转车问题1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线(1)S3359→S1828(2)S1557→S0481(3)S0971→S0485(4)S0008→S0073(5)S0148→S0485(6)S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。南京邮电大学数理学院杨振华制作[e-mail]基本参数设定相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。南京邮电大学数理学院杨振华制作[e-mail]公汽线路信息公汽运行方式（1）环形（2）上下行（有可能上下行路线一致）公汽收费方式（1）分段计价（2）单一票制1元南京邮电大学数理学院杨振华制作[e-mail]公汽线路信息文件列出了520条公汽线路，下面是其中的一条：L001分段计价。S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710该线路是分段计价，且上下行路线一致的。南京邮电大学数理学院杨振华制作[e-mail]地铁线路信息T1票价3元，本线路使用，并可换乘T2。D01-D02-D03-D04-D05-D06-D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21-D22-D23T2票价3元，本线路使用，并可换乘T1。环行：D24-D25-D26-D12-D27-D28-D29-D30-D31-D32-D18-D33-D34-D35-D36-D37-D38-D39-D24南京邮电大学数理学院杨振华制作[e-mail]地铁T1线换乘公汽信息D01：S0567，S0042，S0025D02：S1487D03：S0303，S0302D04：S0566D05：S0436，S0438，S0437，S0435D06：S0392，S0394，S0393，S0391D07：S0386，S0388，S0387，S0385D08：S3068，S0617，S0619，S0618，S0616D09：S1279D10：S2057，S0721，S0722，S0720D11：S0070，S2361，S3721D12：S0609，S0608D13：S2633，S0399，S0401，S0400D14：S3321，S2535，S2464D15：S3329，S2534D16：S3506，S0167，S0168D17：S0237，S0239，S0238，S0236，S0540D18：S0668D19：S0180，S0181D20：S2079，S2933，S1919，S1921，S1920D21：S0465，S0467，S0466，S0464D22：S3457D23：S2512南京邮电大学数理学院杨振华制作[e-mail]地铁T2线换乘公汽信息D24：S0537，S3580D25：S0526，S0528，S0527，S0525D26：S3045，S0605，S0607D12：S0609，S0608D27：S0087，S0088，S0086D28：S0855，S0856，S0854，S0857D29：S0631，S0632，S0630D30：S3874，S1426，S1427D31：S0211，S0539，S0541，S0540D32：S0978，S0497，S0498D18：S0668D33：S1894，S1896，S1895D34：S1104，S0576，S0578，S0577D35：S3010，S0583，S0582D36：S3676，S0427，S0061，S0060D37：S1961，S2817，S0455，S0456D38：S3262，S0622D39：S1956，S0289，S0291南京邮电大学数理学院杨振华制作[e-mail]问题分析从实际情况考虑，不同的查询者有不同的要求。在数学上体现出目标的不同。一般可以考虑转车次数、乘车费用、乘车时间这3个目标。问题可以归结为多目标优化问题。南京邮电大学数理学院杨振华制作[e-mail]问题分析如何处理上面的多个目标？多目标的处理最常用的方法是单目标化，即采用加权平均等方法将多个目标结合形成一个单一的目标。本问题中，单目标化并不合适，比较适当的方法是对每个目标寻求最佳线路，然后让乘客按照自己的需求进行选择。南京邮电大学数理学院杨振华制作[e-mail]模型建立我们先仅考虑公汽线路的情况。设N表示问题中的公汽站点数,即N=3957,A0＝(a(i,j,0))N×N是直达最小站数矩阵，当存在公共汽车从站点直达站点时，表示从直达的最小站数。否则该元素取为+∞。南京邮电大学数理学院杨振华制作[e-mail]模型建立令Am＝(a(i,j,m))N×N是m次转乘最小站数矩阵，其元素a(i,j,m)表示m次转车情形下，从Si到Sj的最小站数。显然},,1|)1,,()0,,(min{),,(jkikNkmjkakiamjia南京邮电大学数理学院杨振华制作[e-mail]最小转车次数模型对于给定的公汽站点Si与Sj，最小转车次数模型可以写为}),,(|min{mjiam南京邮电大学数理学院杨振华制作[e-mail]最小乘车时间模型转车次数为m时，从Si到Sj的总时间为5m+3a(i,j,m),（转一次车5分钟，每乘一站，用时3分钟）下面是最小乘车时间模型：),,(35),,(min0mjiammjitSm南京邮电大学数理学院杨振华制作[e-mail]最小乘车费用模型最小乘车费用模型可以写为如下的形式：},,,,,|)),(),(),(min{21211互不相等nnmmnnnnkkkjikkfjkfkif该模型是形式上的，对于求解没有实质性的作用。南京邮电大学数理学院杨振华制作[e-mail]最小转车次数模型求解对于给定的公汽站点Si与Sj，只要逐次求出(a(i,j,m))，直到其为有限值即可。}),,(|min{mjiam},,1|)1,,()0,,(min{),,(jkikNkmjkakiamjia在实际求解时，先根据公汽线路的数据将a(i,j,0)的数据存储在矩阵A0中。南京邮电大学数理学院杨振华制作[e-mail]最小转车次数模型求解算法一（逐次查找）对于给定的i,j,(1)若a(i,j,0)+∞,表明转车次数为0,否则转(2);(2)k从1到N进行搜索,若a(i,k,0)+∞,a(k,j,0)+∞,则转车次数为1,否则转(3);(3)k1,k2从1到N进行搜索,若a(i,k1,0)+∞,a(k1,k2,0)+∞,a(k2,j,0)+∞,则转车次数为2.},,1|)1,,()0,,(min{),,(jkikNkmjkakiamjia}),,(|min{mjiam南京邮电大学数理学院杨振华制作[e-mail]最小转车次数模型求解逐次查找算法的复杂度若只要转一次车,则循环的步数为N;若要转2次车,循环的步数为N2;若要转3次车,循环的步数为N3……由于N=3957,N3≈6.2×1010,普通计算机运行时间较长，若要转4次车，很难承受计算量!南京邮电大学数理学院杨振华制作[e-mail]最小转车次数模型求解算法二（存储逐次查找）(1)若a(i,j,0)+∞,表明转车次数为0,否则转(2);(2)求出矩阵A1＝(a(i,j,1))N×N,其每个元素通过上面的表达式,用k从1到N循环求得.若对给定的i,j,有a(i,j,1)+∞,表明转车次数为1;类似可以计算多次转车的情况注:矩阵A0,A1等计算后存储在计算机中,},,1|)1,,()0,,(min{),,(jkikNkmjkakiamjia南京邮电大学数理学院杨振华制作[e-mail]最小转车次数模型求解存储逐次查找算法的复杂度矩阵A1的计算:一共计算N2个元素,每个元素的计算要循环N步,计算量为N3.运行时间依然较长。优点：矩阵Am(m1)的计算工作量与A1一致!有可能计算转多次车.南京邮电大学数理学院杨振华制作[e-mail]最小转车次数模型求解在前面的两个算法中,每次循环都要进行N次.事实上,对给定的i,满足a(i,k,0)+∞的k是很少的,我们只要对这些k进行循环.在实际问题中,任何一个城市中,任何一个公汽站点所能到达的公汽站点只是城市中的一些“线”,相对于整个城市而言,数目是比较少的.},,1|)1,,()0,,(min{),,(jkikNkmjkakiamjia南京邮电大学数理学院杨振华制作[e-mail]最小转车次数模型求解算法三（有限搜索逐次查找）给出矩阵B,其第i行记录的是满足a(i,k,0)+∞的所有的“k”.将存储逐次查找算法中的k从1到N循环改为正对矩阵B第i行中的“k”进行循环.},,1|)1,,()0,,(min{),,(jkikNkmjkakiamjia南京邮电大学数理学院杨振华制作[e-mail]最小转车次数模型求解有限搜索逐次查找算法的复杂度矩阵Am的计算:一共计算N2个元素,每个元素的计算要循环的步数大大小于N,大约为N/10,计算量约为N3/10.一般的计算机可以实现.南京邮电大学数理学院杨振华制作[e-mail]最小转车次数模型求解对于题目中给出的六组公汽站点,其最小转车次数分别为(1)S3359→S18281(2)S1557→S04812(3)S0971→S04851(4)S0008→S00731(5)S0148→S04852(6)S0087→S36761南京邮电大学数理学院杨振华制作[e-mail]转车次数由于算法复杂性的问题,许多参赛队都假设“最多转2次车”,少数参赛队考虑转3次车,个别的参赛队考虑转4次车或更多.由于所给的6组站点最小转车次数为