点线搜索逐步扩展的公交线路查询模型及算法

1、点线搜索逐步扩展的公交线路查询模型及算法摘要第29届奥运会明年8月将在北京举行，北京市的交通网络十分庞大，其中大部分人将会乘坐公共交通工具，包括公汽、地铁等出行。观众从一个地方到另一个地方需要查询可达的方式及路线，那么如何选择路线才可以适合观众的要求？本文针对任意输入两个站点，可以迅速查询到可达方式及路线的问题，分为仅仅考虑公汽线路之间的乘坐和转乘，同时考虑公汽和地铁之间的乘坐和转乘，公汽、地铁、步行混合交通出行三种情况，给出线路选择的模型与算法，并应用Matlab软件编程实现，检验了模型与算法是合理、高效的。该问题的关键是解决如何在多线路、多方式、多站点的复杂网络中任意选择两个站点，快速找到

2、出行方式和路线的问题。为此通过所给线路和站点的数据，巧妙构造一个带有查找特征“站点线路关系”的矩阵，把所有站点进行编号，作为矩阵的列的编号；把所有线路区分上行、下行进行编号作为矩阵的行的编号。矩阵中元素的填法为：与列的站点编号对应，将每条线路在运行途中的第一个站点标注为1，第二个站点标为2，不经过的站点标为0依此类推，直到最后一个站点。实际上构造了一个有向图。这样构造的矩阵的优点是：能反映每条线的运行方向、可判断任意两站之间的站点数，横看为该条线路上的站点、竖看为该站点有几条线路通过；便于建立站点和线之间的“点线”对应关系，即找经过该点的线路和该线路对应的站点；而且该矩阵便于Matlab编程操

3、作。基于所构造的矩阵，可以构造基于集合理论的“逐步扩展搜索法”，对不同的出现方式、对任意两输入点毫无疏漏地查找直达线路、转乘点、转乘线路、转乘次数；把地铁线路和步行作为特殊线路加入表中，即可以顺序解决所提到的三个问题，这样建立的模型和算法简捷、耗时非常短，完全可以满足适时查询要求。根据人们选乘公交出行的偏好考虑时间最短、费用最省、尽可能的少转车，对查找到的站点和路线进行目标优化，最后给出结果。任意输入两个站点，三个问题的结果是：（1） 问题一，只考虑公汽线路时建立了模型与算法并利用所建模型求出了给定两个站的最优路线；（2） 问题二，同时考虑公汽与地铁线路时建立了模型与算法并利用所建模型求出了给

4、定两个站的最优路线；（3） 问题三，假设任意两站之间的人的步行时间为10分钟，在考虑可以步行转乘的情况下建立了模型与算法。并且比较得出若增加约束条件后最优路线可能改变的结论。用程序验证了当站点数和线路数比目前所给的站点数和线路数更多时，所提出这种“点线”逐步扩展搜索法在时间运行上几乎不受影响。关键词： 有向图 点线交替运算 逐步扩展搜索法 站点 路线一 模型的分析乘公交，看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。目前北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。为此，某公司准备研制开发一个解决公交线路选择问

5、题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。需要解决如下问题：1 仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用所建立的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762 同时考虑公汽与地铁线路，解决以上问题。3 假设又知道所有站点之间的步行时间，给出任意两站点之间线

6、路选择问题的数学模型。因为站点数和线路数较多，因此这是一个在高度复杂网络中查找线路的问题，一般情况下用图论和矩阵的相应方法建立模型求解。但本问题的拓扑结构复杂，可以有多种方法建立模型，大多数程情况下程序实现较为困难，特别是计算时间需要较长，不能适应适时快速查询的要求。为此需要寻求一种快速、高效的方法。问题涉及到的因素有人、道路、站点、车，还有省时、省钱的问题。解决问题的关键为站点和线路的查找，因此建立一个站点与线路相对应的邻接矩阵，构造有向图；又因为站点与线路的问题是元素与集合的问题，所以用集合理论来建立查找站点和路线，由站点找到线路，再进行优化，从而解决问题。二 问题初始化与模型假设1基本参

7、数设定A. 相邻公汽站平均行驶时间(包括停站时间)： 3分钟B. 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟C. 公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)D. 地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)E. 地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)F. 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟) 注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合2定义集合与矩阵A. 线集合： i=1，1040；B. 站点集合： i=1，3957；C. 矩阵，i=1041，1042时为地铁线，1043步行。前2到87列顺序记录线上所途径的站点，第88

8、列记录票价情况，单一票价记为-2，分段计价记为-1，地铁线记为-3，。D. 矩阵，其中若站不在Li线上则，否则表示站位于Li线上的站点次序。i =1，1043；j=1，39573假设以下几个条件：A. 公交车运行时间不因交通环境变化而改变。B. 乘环行公交到起始站乘客必须全部下车，重新乘车，视为换乘。C. 假设公交车的运量不受限制，车到站乘客即可上车。D. 假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)，只分别考虑一次地铁换公交，公交换地铁的时间，即13分钟。E. 假设人行走时的平均速度是一定的。F. 假设不论是公汽线，地铁线以及步行求最优解时只考虑单一因素。三 问

9、题的预处理该问题是要求给出公交查询系统的算法模型，便于乘客查询出行更加通畅、便利的乘坐路线。以节省时间、最短路程、转乘次数最少建立模型进行优化，以适应不同需求的乘客。该问题的重点在于找到直达，转乘一次可达，转乘两次以及两次以上可达的路线。我们首先对题目中的数据进行了处理。1线路重编号因为公交车的运行方式有三种：单程，上下行，环行。所以我们针对三类数据给出了三种处理方法。单程是公交车上行和下行的站点完全相同，上下行是公交车的运行的过程有不同的站点，环行则没有起始站和终到站的区别。这样我们把给出的520个编号的线路都分成了两条线，这两条线的编号相差520。单程：（以L001为例）上行：L001S0

10、619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710S0619S1914S0388S0348S0392S0429S0436S388512345678S3612S0819S3524S0820S3914S0128S07109101112131415那么它的另一条路线是下行：L521（L001的反向线）S0710-S0128-S3914-S0820-S3524-S0819-S3612-S3885-S0436-S0429-S0392-S0348-S0388-S1914 S0619S

11、0710S0128S3914S0820S3524S0819S3612S388512345678S0436S0429S0392S0348S0388S1914S06199101112131415上下行（以L111为例）上行：L111S3543-S0202-S1023-S2293-S3170-S1954-S1955-S1957-S2323- S2321- S2397S3543S0202S1023S2293S3170S1954S1955S1957S2323S2321S23971234567891011下行：L531S2397-S0147-S2321-S2323-S1957-S1955-S2962-S3

12、170-S2293 S2293-S1023-S3813-S3543S2397S0147S2321S2323S1957S1955S2962S317012345678S2293S1023S3813S35439101112环行：根据观察我们发现环行线有两种，可分别等价成两种不同的路线来考虑。总的思想是去环。单环（只是首尾相接的）：以L027为例，只需把他的首尾站去掉一个，然后当成只有去路的上行线来考虑。它所对应的“下行线”的编号即为L547，它不通过任何一个站点。第二种环：采用破圈法以L425为例。S1042-S0130-S3019-S0969-S3741-S1963-S3741-S3019-S04

13、77-S1042，由S1963站点分开为上下行线。上行：L425 S1042-S0130-S3019-S0969-S3741-S1963S1042S0130S3019S0969S3741S1963123456下行：L945 S1963-S3741-S3019-S0477-S1042S1963S3741S3019S0477S104212345据此，所有公交车都区分为上、下行线路。这样所有线路相当于有1040路单行公交车。这样做在计算中可以大大减少计算量：（1）按先后顺序编号，可以看出公交车的运行方向，且只有编号小的站可以到达编号大的站。（2）可以直接看出公交车各站点之间的距离。2站点处理题目给出

14、了3957个站点，若用关联矩阵建立任意两个点之间的关系，那么可以生成一个的矩阵，这样建立模型较为复杂。所以先建立了一个简单的矩阵B。它的行标为11043，列标为所有公交车线路中经过的最大站点数。它反映的是i线上的车站顺序，即（i，j）元上存放的是在i线上的站点号。并且在最后一列，增加一列，作为标志区分几种计价方式。与前定义集合与矩阵中的B同。3费用计算如果记录为-1，则为单一计价，此时费用c=1。如果记录为-2，则为分段计价，需判断d与站数20，40的函数关系，进而求出费用c。如果记录为-3，那么此时为地铁线路，这时判断两汽车站是否在同一地铁站点上，若在c=0，否则c=3。如果记录为-4此时代

15、表步行，c=0。四 模型建立1 算法思想利用基于集合理论的“逐步点线扩展搜索法”。核心思想：根据所建立的关联矩阵，根据站点和线路的对应关系，“点线点”或“线点线”转换，即乘客在s站点，欲到t站点，则遍历所有经过s站点的公交线路，并求该路线上的站点组成的集合。数学描述：设表示经过站点的线路集，i=1，3957； 表示经过第j条路线的站点集，j=1，3957。st两站有直达线示意图 1不需要转乘的情况：在关联矩阵中表现为和两个不同的站点在同一行内可找到，即在同一条线上，且矩阵对应元素不为零。集合描述为：对、两个不同的站点对应的站点集分别为和，如果，那么、两站点间有直达车，对直达线路进行优化，给出最

16、便捷的线路；如果，则说明这两个站点没有直达车，至少需要转乘。执行下一步程序。st两站需要一次转乘示意图k2需要转乘一次的情况：通过站点的所有线路不通过站点，而通过站点的所有路线都不通过站点。在关联矩阵中表现为、站点对应的不为零的数不在同一行。由通过站点的所有公交线路上的站点组成集合，通过站点的所有公交线路上的站点组成集合。然后求站点集之间的交集，则、两个站点的关系是需要转乘一次。那么设，即将通过s站点的所有线路上的站点求一个并集。即将通过t点的所有线路上的点求一个并集。为线上的站点的集合。，说明s, t两站点转一次车即可到达，转车点为，在进行优化，选择最便捷的。如果，那么一次转乘不能达到，考虑

17、转乘两次，转入下一步。st两站需要两次转乘示意图k1k23需要转乘两次：通过、两个站点的线路上的站点集没有交集，。集合描述为，设通过的线上的站点集为，通过站点的线上的站点组成的集合为，则通过中的站点集的所有线，与通中的站点的所有线求交集，所得线即为换乘线，它们上的站点的交集与过的线上的站点集的交为第一转乘点，与过站点的线上的站点集的交为第二转乘点；对转乘点进行优化，选择最便捷的。如果交集为空集，则说明通过两次转乘不能到达。至少需要转乘三次，转入下一步。依此循环，可找出换成任意次的换乘点。2 建立模型 按照以上所述的逻辑判断关系，可得到如下的寻找直达线或转车点的集合运算逻辑表。寻找直达线或转车点

18、的集合运算逻辑表对应站点集合对应线路集合判断交集合是否为空集对应线路集合对应站点集合输入站点A1输入站点B1A1对应的线路集合L（A1）直达线B1对应线路集合L（B1）L（A1）上的站点集合A2L（B1）上的站点集合B2A2对应的线路集合L（A2）B2对应线路集合L（B2）L（A2）上的站点集合A3一次转车点L（B2）上的站点集合B3A3对应的线路集合L（A3）B3对应线路集合L（B3）L（A3）上的站点集合A4二次转车点L（B3）上的站点集合B4A4对应的线路集合L（A4）B4对应线路集合L（B4）L（A4）上的站点集合A5三次转车点L（B4）上的站点集合B5输入站点起始A1和终点站B1，分

19、别得到对应的线路集L（A1）、L（B1），如果两线路集有交集，即为直达线路；如果无交集，再分别找出线集L（A1）、L（B1）对应的站点集A2、B2，又分别找出它们对应的线路集，L（A2）、L（B2），两组线路对应的站点集如果有公共交点，则为一次转乘点。如果没有交点，则需要转乘两次。依此进行下去，可以找到需要二次、三次转车的转车点，等等。综上所述，理论上可以求转乘任何有限次的站点及线路，但实际情况不需要如此。公交公司在设计线路时，设计了多数情况下如果不直达，转乘一次即可达到。少部分站点需要转乘两次到达，几乎就没有要转乘三次才到达的。如果要转乘三次才能到达，乘客会选择其它方式乘公交车。因此我们认为

20、即可。根据算法思想建立如下流程图。基于集合理论的“逐步点线扩展搜索法”流程图输入站点A，B判断站点A，B是否交交交遍历过站点A，B的所有路线，记为lA,lB判断路线lA,lB是否交YY遍历lA,lB上的所有点,记为PA,PB判断站点集PA,PB是否有其他线路相连NNNY有直达转乘一次可达转乘两次可达优化数据输出结果五 模型求解（不妨设求，站的最优路线，s，e=1，3957）问题一 只考虑公共汽车间的换乘问题1 选取直达路线1) 如果存在矩阵A中的i行，满足且，则说明到站经Li线可直达，经过的站点数为d=，时间为t=3*d，此时根据矩阵B中存储的关于i线的票价信息来判断费用。2) 直到矩阵A中找

21、不到满足上述条件的i值后，说明直达路线选取完毕，接着转入一次转乘的选取。2 选取一次转乘路线1) 如果矩阵A中的i行，无法找到满足且，则说明到站从Li线不可直达。2) 若矩阵A中j行存在,使得且,且则为转乘点，通过可实现从Li线到Lj线上的转乘，从而到达。3 选取两次转乘的路线1) 若矩阵A中j行不存在,使得且,且，则说明到站转乘一次不可达。2) 若矩阵i行存在且，j行存在且，k行存在且，则，为转乘点，可从Li转到Lj，再从Lj转到Lk上，从而实现二次转乘。4 判断两次以上转乘若以上条件都无法选择出线路，按照上述过程重复的搜索下去，直到n，即理论上的最大值。但是不在本模型的考虑范围之内，不予考

22、虑5 求最优化解集设我们所得到的集合为g=选择出的线路因为我们建立了三个标准：时间最短和路径最短要筛选两次，而转乘车的次数则不需要计算。Min时间（g），求得时间最短的方案；Min路径（g），求得路径最短的方案。具体的Matlab编程实现见附件1。说明：1给出的数据并非全部解，只是满足单一影响因素下的任意一组解。2若乘车路线大于520时，为减去520后的下行线或反向行驶线，若为1041，1042则分别为地铁线TT12若为直达线，则数据格式如下：i d c t表示s站在i线路上经过d个站到达e，总费用为c，总的时间为t。若为转乘一次可达的，则数据格式如下：i j k d1 d2 c t表示s站在

23、i线路上经过d1个站到达j站，在j站转乘k线路，经过d2个站到达e站。总费用为c，总的时间为t。若为转乘两次可达的，则数据格式如下：i j k l m c t表示s站在i线路上可到达j站，在j站转乘k线路，可到达l站，在l站转乘m线路则可到达e站。总费用为c，总的时间为t。问题一的部分结果：S359起点到终点S1828,只考虑公汽路线的如下：转一次时间最少的线路如下: L956 S1784 L687 31 1 3 101转一次费用最少的线路如下: L469 S304 L737 29 15 3 137转2次时间最少的线路如下: L123 S2903 L201 458 L41 3 73转2次费用最

24、少的线路如下: L15 S900 L137 1671 L41 3 1061557起点到终点481,只考虑公汽路线的如下：转2次时间最少的线路如下: L123 S2903 L201 458 L41 3 73转2次费用最少的线路如下: L604 S1919 L417 902 L254 3 115971起点到终点485,只考虑公汽路线的如下：转一次时间最少的线路如下: L533 S2184 L937 20 21 3 128转一次费用最少的线路如下: L119 S872 L937 17 31 3 149转2次时间最少的线路如下: L989 S2027 L201 S458 L 41 3 73转2次费用最

25、少的线路如下: L13 S345 L660 S2654 L469 3 11287起点到终点3676,只考虑公汽路线的如下：转一次时间最少的线路如下: L454 S3496 L729 11 9 2 65转一次费用最少的线路如下: L454 S1893 L729 12 10 2 71转2次时间最少的线路如下: L206 S88 L231 S427 L97 3 46转2次费用最少的线路如下: L21 S630 L231 S427 L97 3 528起点到终点73,只考虑公汽路线的如下：转一次时间最少的线路如下: L679 S2559 L464 21 5 3 83转一次费用最少的线路如下: L679

26、S400 L474 10 16 2 83转2次时间最少的线路如下: L198 S3766 L296 S2184 L345 3 67转2次费用最少的线路如下: L983 S3604 L736 S2800 L11 3 133148起点到终点485,只考虑公汽路线的如下：转2次时间最少的线路如下: L308 S36 L156 S2210 L937 3 106转2次费用最少的线路如下: L24 S345 L660 S2654 L469 3 121问题二 同时考虑地铁与公共汽车时任意两站的选择在本问中我们主要做了以下几个工作：1 在问题一的基础上，按照题中所给数据，增加矩阵，这是一个难点，我们在Matl

27、ab中巧妙的导入了外部数据，并且把地铁站和公交车站的信息转化为了公交车站和公汽线路之间，以及公交车之间的关系，从而在问题一矩阵的基础上增加了新的两行进行处理，而处理方法和问题一完全一样，不同的是计算费用情况。2 费用以及花费总时间的求法。上一步的增加矩阵为这一步提供了大大的方便。即在选择路线上按照问题一的方法进行。我们的具体做法是，把每个经过相同地铁站点的公交车站点标志为同一个号，它们之间的费用为0，所需考虑的只是一次公交换地铁和一次地铁换公交的换乘时间。而在不同地铁站之间的标号从前往后递增，排名在前的可到达排名在后的公交车站。3 按照解问题一的方法求解。由于地铁和公交车之间的换乘问题叫复杂，

28、所以我们在问题二中只考虑公交和地铁最多转乘一次，从而简化模型的求解。4 定义票价函数，需要区分单一票价线、分段记价线，具体计算公式如下：公交：，其中为经过的站点数。地铁：3元 最省钱的约束，两条线上的价格之和最小+3n（n=0(没有乘坐地铁)；n=1(乘坐地铁)）具体的Matlab编程实现见附件1。问题二部分解：3359起点到终点1828，公汽和地铁路线同时考虑的如下：转一次时间最少的线路如下: L956 S1784 L687 31 1 3 101转一次费用最少的线路如下: L469 S304 L737 29 15 3 1371557起点到终点481，公汽和地铁路线同时考虑的如下：无971起点

29、到终点485，公汽和地铁路线同时考虑的如下：转一次时间最少的线路如下: L533 S2184 L937 20 21 3 128转一次费用最少的线路如下: L119 S872 L937 17 31 3 1498起点到终点73，公汽和地铁路线同时考虑的如下：转一次时间最少的线路如下: L679 S2559 L464 21 5 3 83转一次费用最少的线路如下: L679 S400 L474 10 16 2 83148起点到终点485，公汽和地铁路线同时考虑的如下：无87起点到终点3676，公汽和地铁路线同时考虑的如下：一条直达费用最少的线路如下: L1042 10 3 38转一次时间最少的线路如下

30、: L1042 S427 L97 10 1 4 53转一次费用最少的线路如下: L454 S1893 L729 12 10 2 71 从结论中我们看出如果只考虑单一因素而不考虑其他因素，则会选出好多种方法，这时随便选出一条路线都可以满足要求。又从结果数据中，我们看到问题二和问题一比较，结论会有所变化。明显的从87起点到终点3676转一次车时，若只考虑公汽路线最短时间为65分钟，而考虑地铁线时时间为53分钟，由此说明路线越多，复杂程度越高，相应的选择会变优。问题三 考虑步行时任意两个站的选择本问的求解过程和问题二的基本类似，难点也是怎样加入第1043行记录。由于假设了所有站点之间的步行时间为已知

31、道，即在平均步行速度一致的情况下，把第1043行元素全部记为1，即两个站之间可以直接步行通过，把人步行做为一条线路来和公汽，地铁线进行转乘，从中选取最优值。从时间最短方面考虑时，选取时间最短的，从费用最省方面考虑时，由于步行不花钱，所以就步行。即只需建立时间最优的模型。问题三的模型1 增加1043行，并将其元素全部计为1；用来表示第i站到第j站步行所用时间。2 把人直接从第i站步行到第j站当作是直达线，其余都视为转车。3 把问题二中的循环控制条件从1：1042改为1：1043；4 计算直达情况；步行的直达时间为，公汽和地铁的按前述算法计算。5 计算转一次，即车转人或人转车的情况，假设k为中转站

32、，则总时间为步行到k站的时间加上坐车行驶的时间。6 因为不考虑钱只考虑时间因素，所以分别从前面两组数据里取得时间最短的路线信息，即为所求。7 转两次以上的类似处理。8 假若现在，所有的站点之间的步行时间全部已知，则可以进行筛选得出最优解。六 模型的结论和评价我们用的方法是基于逐步扩大搜索的方法，在n很小的情况下，优势是相当明显的，避免的对nn矩阵进行逐行逐列的搜索，缩小搜索范围，优化了算法的复杂度，算法在时间复杂度和空间复杂度上都具有相当大的优势，大大提高了算法的效率。从而我们就找出了直达，转乘一次可达，转乘两次可达的路线。但是符合条件的路线是很多的，还必须找出一个筛选的标准来筛选出一个或多个

33、最优解。筛选的标准可分为三个方面：费用最优（方便时间充裕节约型的观众），路线最短（方便赶时间的观众），以及转乘车数最少优先。而因为我们假设只考虑单一因素的影响，所以当对于同一因素筛选出多个值时，随便记录一个即可。通过我们的模型找到了任意两公交车站点之间转乘次数不大于二的所有路线，并可根据人们的实际需要查找出想要的路线。验证结论的正确性（见附件1）。结论的正确性是模型好坏最有力的证明。我们多次将数据带入原始的数据中进行验算，都得到正确得结果。因此，我们得模型是准确的，高效的。针对公共交通系统这样的大型错综复杂的网络，数据量大，对于普通模型与算法，理论上可以求解，但实际操作性不强。例如， Dijk

34、stra算法、蚁群算法、可达矩阵法等方法来求解，效率较低。我们所构造的带有查找特征的“站点线路关系”邻接矩阵，居于这个邻接矩阵可以根据集合理论建立一套快速查找点线关系的算法，由站点找到所需线路，由线路找到站点，从而找到所可能的直达线路、转乘点、转乘车次、转乘次数等，再根据省时和省钱的目的进行优化，给出所需结果。该模型从数据的处理到模型的建立处处体现了降低算法的复杂度，提高算法的效率的宗旨。对于不同的条件、仅仅考虑公汽、加入地铁线、再加入步行情况，可以方便地顺序解决。我们建立的模型和算法的最大优点是逻辑简单、运算速度快，所需运算时间非常短，这是普通方法不及之处。而且，如果再扩大站点数和增加线路，

35、只是邻接矩阵增加维数，但是我们的算法运算速度几乎不受影响，模型和算法具有普适性，完全能够满足乘客对大型复杂网络系统的快速查询要求。在寻找转乘次数的时候，我们只考虑了小于3次的，对的确要转乘3次或3次以上情况无法一次完成查询。在考虑乘地铁的时候，我们也考虑了只乘坐一次的情况，对于的确要乘坐两次地铁的情况也无法实现一次完成查询。同理步行的考虑也会出现欠缺。但是我们认为这两种情况属小概率事件，从一定程度上来说并不影响模型和算法普适性。七 参考文献1 韩中赓 数学建模方法及其运用 北京高等教育出版社 2005年 25-36页2 耿素云 屈婉玲 离散数学 北京 高等教育出版社 2005年 267-288

36、页3 姚东 王爱民 冯风 王朝阳 MATLAB命令大全 北京 人们邮电出版社 2000年 297-356页附件1计算问题一的函数Matlab中打开query_road.m文件，然后输入起始站s和终点站e的值执行,即可出现s到e的路线。%定义A，B矩阵函数，function f,g=zzzfd=fopen(1.txt);a=fscanf(fd,%d,88,1043);b=a;y=zeros(1043,3957);for i=1:1043 k=1; for j=2:87 if b(i,j)0 y(i,b(i,j)=k; k=k+1; end end endf=y;g=b;%function f=q

37、uery_road(s,e)s=2359;e=1828;clc;tic;Y,B=zzz;%直达aa=0;fprintf(%d起点到终点%d,只考虑公汽路线的如下：n,s,e)for i=1:1040 if (Y(i,s)0 d= Y(i,e)-Y(i,s); t=d*3; %费用计算 if B(i,88)=-2 c=1; else if d=20; c=1; else if d0siz=size(rr);if siz(1)1 mi=min(rr) disp(直达时间最少的线路如下: ) for i=1:siz(1) if rr(i,4)=mi(4) disp(rr(i,:) end enddi

38、sp(直达费用最少的线路如下: )for i=1:siz(1) if rr(i,3)=min1(3) disp(rr(i,:) end endelse if siz(1)=1 disp(一条直达费用最少的线路如下: ) disp(rr) endendend%转一次count=0;for i=1:1040 if Y(i,s)=0 continue; end for j=1:1040 if Y(j,e)0&Y(i,s)0 & Y(j,part(k)Y(j,e) if (i=17&j=537)|(i=213&j=733)|(i=273&j=793)|(i=407&j=927)|(i=408&j=92

39、8)|(i=412&j=932)|(i=425&j=945)|(i=505&j=1025) d1=Y(i,part(k)-Y(i,s); d2=Y(j,e)-Y(j,part(k); d=d1+d2; t=d1*3+d2*3; %费用计算 if B(i,88)=-2 c=1; else if d=20 c=1; else if d=40 c=2; else c=3; end end end disp(i,d,c,t) else d1=Y(i,part(k)-Y(i,s); d2=Y(j,e)-Y(j,part(k); t=d1*3+d2*3+5; %费用计算 if B(i,88)=-2 c1=1; else if d1=20 c1=1; else if d1=40 c1=2; else c1=3; end end end if B(j,88)=-2 c2=1; else if d2=20 c2=1; else if d20 size1=size(road);if size1(1)1min1=min(road);disp(转一次时间最少的线路如下: )for i=1:size1(1) if road(i,7)=min1(7) disp(road(i,:) end enddisp(转一次费用最少的线路如下: )for i=1:size1(1)