1. 最佳公交线路查询算法 摘要：针对开发公交线路选择、自主查询的计算机系统问题，首先将所有 公交线路抽象为一个网络图， 建立网络图的相联矩阵， 采用双向树全局搜索算法， 设计出公交线路选择问题的自主快速查询系统。 针对问题 1，对查询者输入的任意一对起始站和终到站，要求给出整个公汽 网络中的最佳乘车路线，并告诉查询者所需的最少乘车时间及相应的费用的问 题。首先通过【附录 2】1.1 公交线路信息建立与公汽网络相关的矩阵。其次， 通过在整个路线网络中以起点站和终点站建立两棵树， 使用双向树全局搜索算法 遍历矩阵。通过访问元素在矩阵中的位置来寻求最佳乘车路线（角标算法） ，把 抽象网络图转化矩阵， 最后通过矩阵来建立公交线路选择自主查询系统的模型与 算法，并运用 MATLAB 编程计算出问题 1 的 6 条最优路线结果如下表： 项目 最 少 时间 线路 第一 趟路 线 第一次 转 车 站: 第二 趟路 线 转车次 数 第二次转 车 站 第三乘车 路线 费用 L436 S1784 L217 1 3 S3359→S1828 101 L084 S2563 L140 2 S1327 L072 3 S1557→S0481 106 L013 S2184 L417 1 3 S0971→S0485 128 L043 S1383 L282 1 3 S0008→S0073 113 L828 S1797 L442 2 S1478 L050 3 S0148→S0485 106 L454 S3496 L209 1 2 S0087→S3676 65 针对问题 2，要求在问题 1 的基础上考虑使用地铁，找一个算法来实现任意 两个站点间的最佳路线。我们对数据进行分析，对 11 种可能的情况应用所提出 的角标算法，然后用 MATLAB 编程计算出问题 1 的 6 条最优路线结果如下表： 最少 进入地 转乘地 转 乘地 须乘 转乘公 地铁转 费 时间 铁的公 铁的公 铁 的地 座的 共车的 乘公交 用 交线路 共车站 铁 车站 地铁 公共车 的路线 名 名 线路 站名 S3359→S1828 83.5 L015 S3068 D8 T1 S3262 41 5 S0971→S0485 S0008→S0073 S0148→S0485 S0087→S3676 95 L094 S567 D1 T1 4 37 L259 S 3874 D8 T2 4 86.5 L024 S1487 D2 T1 4 17 L021 S1427 D8 T2 4 不用地铁的情 最少 第一趟 第一次 第 二趟 转车 第二次 第三乘 费 况 时间 路线 转车站: 路线 次数 转车 站 车路线 用 S1557→S0481 106 L084 S2563 L140 2 S1327 L072 3 项目 线路 关键词：公交查询系统；角标算法；双向搜索；MATLAB； 连通路线； 1 最 优 路 线 选 择 地 铁 最 优 路 线

2. 一 问题重述 公交线路作为城市人员的运载主体已渗透到城市的每个角落， 构成庞大的立 体交通网络。每个市民对公交乘坐路线的了解显得十分必要。 全国人民翘首企盼的第 29 届奥运会明年 8 月将在北京举行，届时有大量观 众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括 公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市有两条 地铁 （T1 和 T2） 以及 800 条以上的公交线路， ， 使得公众的出行更加通畅、 便利， 但同时也面临多条线路的选择问题。 问题的数据给出了两条地铁路（T1 和 T2） ，以及 520 条公交线路和相应的各 个站点。针对工交线路有以下几方面的信息： （1） 每条公交线路的票价信息不同，分为分段计价和单一票制两种； （2） 对每一条公交线路， 当上行与下行所含的站点完全一致时(即按原路返 回),数据中没有下行；当下行所含的站点与上行不完全一致时（即不按原路返 回） ，数据中有下行出现；当起点站与终点站一样时（环行路线） ，数据以“环行” 两字开头。 两条地铁中，T2 是环行路线（以 D24 开始，同时以为 D24 结束） ，T1 与 T2 相交于两个站点 D12 和 D18（即在站 D12 或 D18 换乘地铁线） 。 相邻的公汽站和地铁站的平均行驶时间分别为 3 分钟和 2.5 分钟； 公汽换乘 公汽、 地铁换乘地铁、 地铁换乘公汽、 公汽换乘地铁的平均耗时分别为 5 分钟(其 中步行时间 2 分钟)、4 分钟(其中步行时间 2 分钟)、7 分钟(其中步行时间 4 分 钟)和 6 分钟(其中步行时间 4)。 现要求在以上的数据信息的条件下， 设计出一个解决公交线路选择问题的自 主查询计算机系统。设计这样一个系统，其核心是线路选择的模型与算法，应该 从实际情况出发考虑，为了满足查询者的各种不同需求。需要解决如下问题： 问题 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数 学模型与算法。并根据附录数据，利用模型与算法，求出以下 6 对上车站→下车 站之间的最佳路线；(1) S3359→S1828 (2) S1557→S0481 (3) S0971→S0485 (4) S0008→S0073 (5) S0148→S0485 (6) S0087→S3676，并要有清晰的评价 说明。 问题 2、同时考虑公汽与地铁线路，解决以上问题。 问题 3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选 择问题的数学模型。 二 问题分析 针对问题 1，在仅考虑公汽线路时，需要解决的问题是：对查询者输入的任 意一对起点站和终点站， 给出整个公汽网络中的最佳乘车路线，并告诉查询者所 需的最少乘车时间及相应的费用， 若需转车的路线要给出转车次数及具体的转车 方案， 或转车次数和费用尽量少时相应的耗时量，若有转车的路线要给出转车次 数及具体的转车方案。考虑需要设计的是查询系统，所以查询最优路线的时间应 该作为检查所实际的系统是否好坏的一项重要的指标。很明显，时间越段，效果 越好。所以问题的关键是怎样设计出一种好的算法，在保证解尽量靠近最优时， 2

3. 查询所花的时间最少。 考虑到实际情况， 我们一般认为从起始站到终到站，乘客主要考虑的是乘车 过程所花的时间。然后考虑乘车是否方便（尽量少转车） ，一般认为最多转两次。 针对问题 2，通过对数据的分析得知，两条地铁中，T2 是环行路线（以 D24 开始，同时以为 D24 结束） ，T1 与 T2 相交于两个站点 D12 和 D18（即在站 D12 或 D18 换乘地铁线） 。每一个地铁站对应一些公交站点，要解决的问题是：对查 询者输入的任意一对起点站和终点站（可能会有地铁站，也可能没有） ，给出最 佳的乘车路线。对起始点和终到点进行遍历搜索，得到两个点的所有分支。 对 地铁站所对应的公共汽车站， 都进行遍历搜索得到各个地铁站的公交所连接的路 线， 按照连通规则判断出连通路线， 并将 1 组起始站、 起始站所连的地铁公交站、 终到站所连的地铁公交站、终到站的角标存放到矩阵 T 3 当中。 问题 3 是在前两问的基础上，假设知道所有站点之间的步行时间，给出任意 两站点之间线路选择问题的数学模型，因为没有给出具体的步行时间，所以不需 要对模型进行求解。 三 基本假设及符号说明 基本假设： 1、假设任何两个站点都可通过转乘各种公交到达； 2、假设两条地铁可以换乘，且只须够一次票，同一地铁站对应的任意两个 公汽站之间可以通过地铁站换乘(无需支付地铁费)； 3、假设乘坐公交最多只转两次车； 4、假设从每个公汽到地铁都不需转车； 符号说明： A ：表示站牌矩阵， A 的每一行是一个站牌，表示一条单向行车路线； T1 ：表示在算法中用来记录不用转车的所有可行路线的信息，T1 的每一行表 示不转车的一条可行路线； 作为一个向量， 在算法中用来记录不用转车的每条可行路线的站的数量； Y1 ： 表示在算法中用来记录转一次车的所有可行路线的信息，T1 的每一行表 T2 ： 示转一次车的一条可行路线； 作为一个向量， 在算法中用来记录转一次车的每条可行路线的站的数量 Y2 ： 3

4. 表示在算法中用来记录转两次车的所有可行路线的信息，T1 的每一行表 T3 ： 示转两次车的一条可行路线； 作为一个向量， 在算法中用来记录转两次车的每条可行路线的站的数量： Y3 ： tt 1i ：表示不用转站第 i 条可行线路对应的乘车时间； F 11 ：表示在第一算法模块（只计算直达和转一次车情况的算法模块）中用 来存储起始站树各个子树的矩阵， F 11 的一行表示一个第一级分支及该分支上的 一个第二级分支， 它存储一个根节点及一个分叉点的脚标（这两个点在矩阵中的 一个位置） 。 F 12 ：表示在第一算法模块（只计算直达和转一次车情况的算法模块）中用 来存储起始站树的矩阵， F 12 的一行表示一个第一级分支，它存储一个根节点脚 标（这个点在矩阵中的一个位置） 。 F 22 ：表示在第二算法模块（只计算转两次车情况的算法模块）中用来存储 终到站树的矩阵， F 22 的一行表示一个第一级分支及该分之上的一个第二级分 支，它存储一个根节点及一个分叉点的脚标（这两个点在矩阵中的一个位置） 。 F 31 ：表示在第三算法模块（只计算转地铁情况的算法模块）中用来存储起 始站与地铁车站连接线路矩阵， 11 的一行表示一条起始站与地铁站相连的路线， F 它存储起始站在 A 中一个脚标及一个地铁车站分别在 A ， B(或C ) 中的脚标（这 三个点在对应矩阵中的一个位置） 。 T 1 ：表示在第一算法模块（只计算直达和转一次车情况的算法模块）中用 来记录每条可行路线的起始站， 转车站及终到站的脚标（即该站点在矩阵中的位 1 置） T 的每一行表示一条可行路线的起始站，转车站及终到站的脚标； ， T 2 ：表示在第二算法模块（只计算转两次车情况的算法模块）中用来记录 每条可行路线的起始站， 转车站及终到站的脚标 （即该站点在矩阵中的位置） T 2 ， 的每一行表示一条可行路线的起始站，转车站及终到站的脚标； tt 1 ：表示第一算法模块各通路对应的乘车时间； min t ：算法中用来记录最优路线所需时间； 四 模型建立及求解 4.01 算法分析 现在我们设计全局最优的同时考虑算法的执行时间的优化算法。 首先把整个 公汽路线抽象为一个网络图，在网络中同时从起点站和终点站双向搜索最优路 径。为分析的方便，先给出在整个公交网络中双向搜索最佳路线的示意图。 4

5. 起点 终点 表示需一次转车的车站 表示需两次转车的车站 表示公汽路线 在上图中， 以起点和终点为根节点的两棵树，在树的分支中会出现很多公共 的节点。在图中起点和终点在同一线路上的，说明不需要转车就能到达，起点和 终点由两条折线构成，说明需要一次转车，折点表示转车站（图中用带斜线的椭 圆） ，起点和终点由三条折线构成，说明需要两次转车，折点表示转车站（图中 用黑色椭圆） 。但是整个公汽路线是一个相当庞大的网络，不利于搜索最佳乘车 路线。 因此考虑以具体的每条路线为矩阵的一行，具体的站名为矩阵的每个元素 建立矩阵， 通过访问元素在矩阵中的位置来寻求最佳乘车路线，从而把对抽象网 络图的研究转化为对具体矩阵的研究。通过矩阵来实现具体的算法。 4.02 算法设计基础 1.1 根据对问题 1 的分析再结合看奥运时的实际情况，多数人在选择公交路 线时，会优先考虑乘车的时间及乘车是否方便（转车次数尽量少） ，其次是费用， 因此先考虑在限制转车次数不超过两次的情况下使时间最短的优化算法， 由于公 交网络相当庞大， 可能会出现满足以上条件的多个最优解，然后在这些最优解中 选择费用最低的。 对上图的分析， 可以建立起点到终点的双向搜索算法的模型，但由于网络图 太过于庞大， 甚至无法画出完整的网络图。如果用图论的方法来设计算法会相当 复杂， 所以结合对问题 1 的分析，把对抽象网络图的研究转化为对具体矩阵的研 究， 这使得不改变算法思想的情况下，把一个无法完成的网络图通过建立与其相 联系的矩阵来实现等价的算法。 1.2 首先通过【附录 2】1.1 公交线路信息建立如下的矩阵：矩阵的每行表示 一条路线（即一个站牌的信息） ，以路线最长的站的数量为矩阵的列，长度不够 的路线其后用 0 补足，矩阵中的每个元素是一个站名，用此方法分别建立的上行 矩阵和下行矩阵如下； 上L001  S0619 S1914 S0128 S0710  0 0     上L002  S3748 S2160 S1968 S0004  0 0      0 0     上L519  S0036 S0203 S1462 S3414  0 0  5    上L520  S0600 S2861S2645 S1848  0 0  

6. 上行线路矩阵 下L001  S0710 S0128  S1914 S0619 下L002  S0004 S1968 S2160 S3748         下L519  S3414 S1462 S0203 S0036  下L520  S1848 S2027 S2861 S0600   0 0   0 0  0 0   0 0  0 0   下行路线矩阵 通过上行线路和下行线路构造整个网络路线矩阵 A 见附件[1]，矩阵 A 的简略 形式如下； 上L001  上L002    上L519 上L520   下L001 下L002    下L519  下L520   S0619   S3748     S0036  S0600   S0710   S0004     S3414  S1848  S1914 S0128 S0710  0 0   S2160 S1968 S0004  0 0    0 0   S0203 S1462 S3414  0 0  S2861S2645 S1848  0 0   S0128  S1914 S061  0 0   S1968 S2160 S3748  0 0    0 0   S1462 S0203 S0036  0 0  S2027 S2861 S0600  0 0   对应于图 1 中的双向树搜索算法， 在矩阵中的任意选择两个元素分别作为起 点站和终点站，搜索它们最优路径，从起点站在矩阵的位置开始，向右按行发散 搜索，从终点站在矩阵中的位置开始，向左按行发散搜索。这样就使双向树搜索 算法转化在矩阵中得到实现。 因为矩阵的一行就是一条路线， 且行车方向总是向右， 那么若一个站 S ' 在另 一个站 S 同行的右侧，则公交车可以由 S 到达 S ' ，但不能由 S ' 到达 S ，可称为 S 到 S ' 的连通，记为 S  S ' 。由此可推出 S ij , S kt 满足 i  k且j  t ,则 S ij  S kt 。由 此引出在寻找通路时并不需要直接由一个站点搜索到另一个站点， 只要这两个点 的角标满足以上规则即可（下面将该规则称为连通规则） 。那么，一个站点的角 标就具有判断其所在行右侧所有站点能否与其连通的足够条件。 也就是给定一个 点 S ，在矩阵 A 中搜索出该点所有的位置，也就对应于在网络图形中生成了一级 分支。 在一级分支上的站点就是该分支产生下一级分支的分叉点，对分叉点再进 行搜索就可生成下级分支， 依次类推对第 n 层分支上的所有站点进行搜索就生成 第 n  1 层分支。 另一方面所有的交通路线构成一个以站点为顶点， 路线为边的一 个网络图， 而一个图对应着一个矩阵，本题的交通网络图所对应的矩阵就是矩阵 那么在交通网络图中寻找两站点的最佳乘车路线就等价于对矩阵 A 进行遍历 A， 搜索最佳路线。基于上述讨论，对根节点按上述方法进行 n 次操作就生成 n 层的 树，那么生成树法就可由此引入到路线搜索中。 6

7. 在一个网络图中搜索全局最佳路线， 传统上有深度优先 [1] 和宽度优先 [ 2 ] 两种 算法，都是属于单向搜索，那么对于本题若从起始站经过 n 次转车才能到达终到 站，就需要生成 n 层的树，也就是对应于节点 n 次生成分支，那么就要对矩阵进 n 行 n 趟遍历搜索。而如过采用双向搜索，就有若 n 为奇数则只须搜索  1 次， 2 n 若 n 为偶数则只须搜索 次，显然有若最佳路线必须经过 n 次转车才能连通，那 2 么在最佳路线上就有 n  1 个节点 S 0 , S1 , S 2  S n ， 从起点开始搜索就有进行一次搜 索则可使 S 0  S1 ，此时也就生成了一个 1 层的树， S 0 是根节点上， S1 是一个叶 点，进行第二次搜索使 S 0  S1  S 2 ，此时生成一个 2 层的树，那么经过 n 次 搜索就能使 S 0  S1  S 2    S n ，也就生成了 n 层的树，若同时从起点和重 点进行搜索，则经过一次搜索就使 S 0  S1 ， S n1  S n ，那么若 n 为偶数，则节 点数就为奇数，此时经过 n 次 搜 索 最 后 通 过 与 Sn 连 通 最 优 路 线 2 2 S0  S1   S n   S n1  S n ，若 n 为奇数，则节点数就是偶数此时进行 2 n 次 2 搜索使得 S0  S1   S n , S n 2   S n1  S n 两条通路在 S n , S n  2 之间不能连 2 2 2 2 同，那么只需再对 S n 进行一次搜索，或对 S n  2 再进行一次反向搜索就能使整条 2 2 线路连同得到最佳路线。下面再对 n 层的树和两棵 观图形对比其总节点数，如图 5。 7 n 层进行比较，首先利用直 2

8. 如 图5 由图 5 明显可一看出对于一个 4 层的二叉树其二分之一层树还没有其四分之 一大。 那么我们进一步对树层与运算量的关系进行分析，先考虑每个节点每次都 n 增生出 k 个节点的情况。那么显然有第 n 层的节点树为 k n ，总节点树为 z   k i i 1 n 那 么 对其连续化分析 ，就有 z   k i  1 n 2 k k ，那么 z  ln k ' kn k ，那么其二分 之一层枝树就有 ln k n 2 z' k  k ，当 k或n 较大时, 就有 k n  k 2  k ,则原式近  n z k k n n n  z' k 2 1 似为  n  k 2  n ，而在本题中矩阵的规模较大图形网络复杂，分支多， z k k2 z'  1  z '  z ，那么就算 z 是有 2 * z ' 也远小于 z ， 由此可知对本题使用双向搜索， 其运算效率将得到很大的 提高。本算法由于是通过连通原则判断两个节点是否连通,故而本算法是对边进 行搜索，而不是对点进行搜索，边的信息是有分叉点的脚标描述，在算法中时间 值也都是通过脚标算式进行计算,减少循环量，对每个问题至少减少一层循环。 也就是若 k 是每个节点的平均分支树，那么 k 值较大 4.03 算法描述 8

9. 算法 1：通过上面的整个网络路线矩阵 A 来实现具体的算法； 1） 通过终端输入要查询的起始站与终点站，遍历矩阵 A 中，在 A 搜索所有 的起始站与终点站，并用一个数组来记录这些起始站和终点站在 A 中的具体位 置。 2） 从起点站的每个位置按行车路线的方向在 A 中发散，每个终点位置按行 车路线的反方向在 A 中发散，当按起点方向与终点方向发散到有共同的节点，说 明已找到可行的路线； 2.1 若可行路线上的所有站在矩阵 A 同一行（表示不需要转车） ，并把所有 这种路线所经过的站名存入矩阵 T1 ； 用向量 Y1  ( y1i , y1i y1i ) 记录所经过的车站数 量，并转步骤 3.1； 2.2 若可行路线上的所有站在矩阵 A 不同两行上（表示需一次转车） ，并把 所有这种路线所经过的站名存入矩阵 T2 ； 用向量 Y2  ( y 2 j , y 2 j y 2 j ) 记录所经过的 车站数量，并转步骤 3.2； 2.3 若可行路线上的所有站在矩阵 A 不同的三行上（表示需两次转车） ，并 把所有这种路线所经过的站名存入矩阵 T3 ；用向量 Y3  ( y31, y32 y3n ) 记录所经过 的车站数量，并转步骤 3.3； 3.1 ）通过 Y3 中 记录的每个数据 计算每一条可行路线所需的时间 tt 1i ， tt i  3 y1i 并通过 T1 记录的信息计算每条可行路线的费用，转步骤 4； 3.2）通过 Y2 中记录的每个数据计算每一条可行路线所需的时间 tt 2 j ， tt 2 j  3 y 2 j  5 ；并通过 T2 记录的信息计算每条可行路线的费用，转步骤 4； 3.3）通过 Y3 中记录的每个数据计算每一条可行路线所需的时间 tt 3n ， 并通过 T3 记录的信息计算每条可行路线的费用， 转步骤 4； tt 3n  3 y3n  10 ； 4） 通过比较可行路线来寻找最优路线，并通过最优路线在 Tk (k  1,2,3) 矩阵 中记录的信息算出最优路线对应的费用 p ， 记最优解为 min t , min t  (tt i , tt j , tt n ) ； 若 min t  tt i 则转步骤 5.1，若 min t  tt j 则转入步骤 5.2，否则转入步骤 5.3； 5.1）输出步骤 4 求的最优解，通过最优解按 min t  (tt i )  T1 返回输出，然 后找到最优路线在 T1 中记录的所经过路线，并输出具体所经过的每一个站；不需 要转车；再输出此时的路线对应的费用，最后结束算法； 5.2）输出步骤 4 求的最优解，通过最优解按 min t  (tt j )  T2 返回，然后 9

10. 找到最优路线在 T2 中记录的所经过路线， 并输出具体所经过的每一个站。 再输出 此时的路线对应的费用和输出需要转一次车，最后结束算法； 5.3）输出步骤 4 求的最优解，通过最优解按 min t  (tt n )  T3 返回，然后找到最 优路线在 T3 中记录的所经过路线， 并输出具体所经过的每一个站。 再输出此时的 路线对应的费用和输出需要转两次车，最后结束算法； 4.04 对算法 1 的改进 4.04.1 考虑从实际情况进行算法优化，影响人们选择公交的因素除了乘坐 时间以外， 多数人考虑的应该是乘车是否方便，而乘车的方便程度可以通过转车 的次数来衡量，所以从转车次数进行优化；下面分两种情况来优化；第一，当可 以行路线包含不转车路线与转一次车时，若优先考虑不转车的路线，可能存在这 样的路线， 转一次车所用的时间小于不转车的路线所用的时间，如果直接选择不 转车线将会导致求出的不是全局最优解，再从乘客角度考虑，转一次车的情况似 乎都能接受，也还算方便，所以考虑综合两种路线求全局最优路线。第二，当可 行路线包含三种路线（不转车，转一次车，转两次车）时，可以从两个方面考虑 优化路线， ①对乘客来说， 转两次车可能觉得比较麻烦， 从乘客的方便程度考虑， 尽量少转车。所以，在不转车和转一次车能够到达的情况下，优先乘坐不转车和 转一次车，如果不能到达，才考虑乘坐转两次车的情况；②从查询者的查询等待 时间考虑， 因为两次转车的算法复杂度远远大于一次转车的情况，计算时间在转 一次车的基础是成指数增长，将造成查询者的查询等待时间增加，所以，在不转 车和转一次车能够到达的情况下，优先乘坐不转车和转一次车，如果不能到达， 才考虑乘坐转两次车的情况。 基于以上的分析对前面的算法的第四步作如下改进；即对前面算法的步骤 4 分别就不转车和转一次车与转两次车的情况求最优路线 （当然可能不是时间的最 优解） ，并且优先考虑步骤 4.1，在步骤 4.1 无可行解时转步骤 4.2。 首先，步骤 3.1 与 3.2 结束后转步骤 4.1；步骤 3.3 结束与 4.1 无可行解时 转步骤 4.2； 4.1）通过比较可行路线来寻找最优路线，并通过最优路线在 Tk (k  1,2) 矩 阵中记录的信息算出最优路线对应的费用 p ， 记最优解为 min t , min t  (tt i , tt j , ) ； 若 min t  tt i 则转步骤 5.1，若 min t  tt j 则转入步骤 5.2； 4.2）通过比较可行路线来寻找最优路线，并通过最优路线在 T3 矩阵中记录 的信息算出最优路线对应的费用 p ，记最优解为 min t ；显然 min t  tt n ；转入步 骤 5.3； 4.04.2 对算法内部结构进行优化，①针对算法的步骤 1，在遍历矩阵 A 搜 索起点站和终点时，由矩阵 A 的构造特点，矩阵 A 的每一行表示一条公汽路线， 矩阵的列为最长线路中站的最大数量，这样构造的矩阵 1040 行，90 列；而站数 10

11. 少的路线只有 11 个， 对每条线路站数达不到 90 的用 0 不足 90 列； 因此矩阵 A 相 当庞大，在遍历矩阵 A 时需要的搜索范围太大，针对这一点，对步骤 1 作如下优 化；设置判断语句；在遍历矩阵 A 时，当碰到 A 中的元素为 0，该分支跳出循环， 不再往下搜索。 这样将使遍历矩阵 A 所用的时间在原来的基础是减少大半；②针 对步骤 2， 在搜索可行解时从离根节点 （起点站或终点站） 较近的节点开始搜索， 在已搜索过的节点做个标记， 当下次再搜索到该节点时不再搜索之前搜索过的路 线，这也将使计算量大大减少。基于以上的分析,改进后的算法如下； 算法 2 （1）输入要查询的起始站与终到站，遍历矩阵 A 中，在 A 中搜索所有的起始 站与终到站，并用一个数组来记录这些起始站和终到站在 A 中的具体位置。 2） 通过一趟循环找到起始站的每个位置，从而将行车路线的按行车方向在 每个终到站位置按同样方法按行车路线的反方向在 A 中发散，当按起 A 中发散， 点方向与终点方向发散到有共同的节点， 说明已找到可行的路线， 并把该起始站、 中转站及终到站的脚标依次存放到 T 1 中的一行； 3.1）根据 T 1 中记录的每个数据判断终到站脚标与中转站的脚标是否一一对 应相等，若相等则不需转车转入 3.2，若不相等则转入 3.3； 3.2） tt 1 (k )  3 * (T 1 (i,6)  T 1 (i,2)) 计算第 i 条可行路线所需的时间。 3.3）tt 1 (k )  3 * (T 1 (i,4)  T 1 (i,2)  T 1 (i,6)  T 1 (i,4))  5 计算第 i 条可行路线所 需的时间。 4） 通过比较可行路线来寻找最优路线，并通过最优路线在 Tk (k  1,2,3) 矩阵 中记录的信息算出最优路线对应的费用 p ，记最优解为 min t , ；若 min t  0 则转 步骤 5.1，若 min t  0 则(表示无可行解)转入步骤 5.2， ； 5.1）输出步骤 4 求的最优解，通过最优解按 min t  T i 返和输出，然后找 到最优路线在 T i 中记录角标信息，返回节点信息；通过节点信息搜寻矩阵 A ， 输出站点名,最后结束算法； 5.2）对起始站,终到站进行两趟遍历，生成两棵 2 层生成树,存储生成树的 2 级分叉的位置,在通过一趟利用连通原则搜寻可行解,存储可行解在矩阵 T 2 中,,转入步骤 4,求解最优解,再转入步骤 5.1 对以上优化后的算法画算法对应的流程图如下： 11

12. 开始 输入起始站、终到站 遍历矩阵搜寻起始站，获得一个第一级分支 产生分叉 遍历矩阵寻找二分支 标记该分支 N 判断是否已有标记点 判断是否完成二级分支遍历 遍 N 判断是否遍历某支的一级分支的所有部分 N 判断是否完成一级分支搜索 遍历矩阵搜寻终到站、获得一个第一级分支 N 判断是否完成一级分支搜索 根据联通条件，搜寻可行解 根据目标函数寻求最优解 Y 判断是否有可行解 遍历终到站的第一级分支 产生分叉点 遍历矩阵寻找二级分支 N N 判断是否完成二级分支的搜索 判断是否遍历某支一级分支上的上的全部分叉 判断是否完成对全部二级分支的搜索 根据联通条件搜寻可行解 根据时间算式得到各可行解的时间值 根据目标搜寻最优解 遍历与地铁相连的公车站 对各站产生分支 根据联通条件搜寻可行解 对各种连接组合计算时间值 搜索最优解 比较最优的解值 输出最终结果 结束 12 N

13. 根据以上流程图，运用 MATLAB 编写相应程序附件 [ 2 ] 计算问题 1 的 6 条路线 的最优解列表如下： 最 第一 第 一 第 二 转 车 次 第 二 第 三 乘 费用 项目 少 趟路 次 转 趟 路 数 次 转 车路线 时 线 车站: 线 车 站 线路 间 S3359→S1828 101 L436 S1784 L217 1 3 S1557→S0481 106 L084 S2563 L140 2 S1327 L072 3 S0971→S0485 128 L013 S2184 L417 1 3 S0008→S0073 113 L043 S1383 L282 1 3 S0148→S0485 106 L828 S1797 L442 2 S1478 L050 3 S0087→S3676 65 L454 S3496 L209 1 2 通过对问题 2 的分析知两条地铁中，T2 是环行路线（以 D24 开始，同时以 为 D24 结束） ，T1 与 T2 相交于两个站点 D12 和 D18 （即在站 D12 或 D18 换乘地铁 线） 。 4.4 算法二设计基础 首先，对地铁线路数据进行分析，明显有如图 6 所示的拓扑结构： D01 D02 D03 D04 D05 D06 D07 D08 D09 D10 D11 D12 D33 D32 D31 D13 D34 D30 D35 D14 D29 D28 D15 D36 D27 D14 D26 D37 D15 D25 D38 D24 D39 D18 D19 D20 D21 D22 D23 那么，要使用地铁线路，首先就要先到达地铁站。考虑到乘客如果转车到地 铁车站或从地铁站转车到达终到站， 会导致转车次数过多造成出行不便以及花费 过大。所以不必考虑通过转车连通地铁车站的情况，那么首先找到起始站、终到 13

14. 站与各个地铁车站的连通路线，如图 7 所示。 D 01 起 点 D 02 D 03 D 04 D 05 D0 6 D 07 D08 D09 D 10 D 11 D 12 D 33 D 32 D 31 D13 D 34 D 30 D 35 D14 D29 D28 D15 D 36 D27 D14 D26 D 37 D 15 D 25 D 38 D 24 D 39 D 18 D19 D 20 D21 D 22 终 点 D 23 搜寻连通路线的具体方法仍然使用双向搜索法，并将起始站到 T1 线路车站 通路的两个节点（起始站、地铁公交站）的在 A 中位置（角标）依次存放到矩阵 SH 1 的一行 中，再将该地铁公交站在 B 中的位置（角标）存入 SH 1 (i,5), SH 1 (i,6) 14

15. 当中。同样的再将起始站到 T2 线路车站的两个节点（起始站、地铁公交站）的 在 A 中位置（角标）依次存放到矩阵 SH 2 的一行 中，再将该地铁公交站在 C 中 的位置（角标）存入 SH 2 (i,5), SH 2 (i,6) 当中。又将终到站到 T1 线路车站通路的 两个节点（终到站、地铁公交站）的在 A 中位置（角标）依次存放到矩阵 ZH 1 的 一行 中，再将该地铁公交站在 B 中的位置（角标）存入 ZH 1 (i,5), ZH 1 (i,6) 当中。 最后将终到站到 T1 线路车站通路的两个节点（终到站、地铁公交站）的在 A 中 位置（角标）依次存放到矩阵 ZH 2 的一行 中，再将该地铁公交站在 C 中的位置 （角标）存入 ZH 2 (i,5), ZH 2 (i,6) 当中。通过图 7 以及矩阵 B ， C 结构的分析，可 以看出要求出起始站到终到站的各连通路线的时间值， 费用值可以通过角标运算 实现。要得到具体运算方法可先分析起始站只通过 T1 连通终到站，那么，总时 间=从起始站到地铁车站的时间+在 T1 上地铁的行使时间+从地铁车站到终到站 的时间+转车的总时间，而转车时间是由转车的次数及方式决定，那么对于每一 种情况而言是一个常数。 而其他三个时间由经过的站数和每一站的平均行驶时间 确定。 由此从起始站到第铁车站的时间是该通路铁路车站节点在 A 中的列角标减 去起始站节点的列角标再乘以公交车通过一站的平均时间。 因为铁路车站的列角 标 被 存 放 在 SH 1 (i,4) ， 起 始 站 的 列 角 标 存 放 在 SH 1 (i,2) 中 ， 那 么 该 段 时 间 同样的对于从地铁出站的公交车站到终到站的时间 t1  3 * (SH 1 (i,4)  SH 1 (i,2)) ， 相应的有 t 2  3 * (ZH 1 ( j,2)  ZH 1 ( j,4)) ，而地铁的行驶时间应该出站车站在 B 中 的行角标减去进站车站在 B 中的行角标再乘以地铁行驶平均时间同样的该角标 值分别存放在 ZH 1 (i,5) ， SH 1 (i,5) ，再考虑到地铁既可以沿矩阵 B 行角标增大的 方向行进， 又可以沿其方方向行进。所以时间应该是出站车站在 B 中的行角标减 去进站车站在 B 中的行角标再乘以地铁行驶平均时间的绝对值。 那么由上述分析 可知 t 3  2.5* | ZH 1 (i,5)  SH 1 (i,5) | 。 又考虑到在该情况下需要公交车转地铁一次, 地铁转公交车一次,那么就有转车总时间 t 4  5  7  12 。 将该时间存放到矩阵 tt 3 中的 k 列就有： tt 3 (1, k )  3 * ( SH 1 (i,4)  SH 1 (i,2)  ZH 1 ( j,2)  ZH 1 ( j,4))  2.5* | ZH 1 ( j,5)  SH 1 (i,5) | 12 那么进一步考虑起始站与终点站只通过 T2 连通的情况，那么首先对应的有 tt 3 (2, k )  3 * ( SH 2 (i,4)  SH 2 (i,2)  ZH 2 ( j,2)  ZH 2 ( j,4))  2.5* | ZH 2 ( j,5)  SH 2 (i,5) | 12 15

16. 但环行线路与线形线路还是有所不同的， 因为对于环行线路存在首尾相接的 特性， 所以需要考虑其由最小行标站行驶到最大行标站，或由最大的行标站行驶 到最小行标站的情况。对于这类其地铁行驶段的时间角标算式： ' t 3  2.5 * (18 | ZH 2 ( j,5)  SH 2 (i,5) |) 那么这种情况下其总时间就有 tt 3 (3, k )  3 * ( SH 2 (i,4)  SH 2 (i,2)  ZH 2 ( j,2)  ZH 2 ( j,4))  2.5 * (18 | ZH 2 ( j,5)  SH 2 (i,5) |)  12 在仅对通过 T1,T2 连通的情况分析之后， 进一步可以对转地铁的情况进行考 虑。 首先是考虑由起始站乘公交车到地铁车站转 T1 线路后又由 D12 站转 T2 线路， 最后出站乘公交车到终到站的情况。首先，要把该地铁路段视为两段，即通过 T1 到达 D12 站为一段，再由 D12 站转乘 T2 线路为另一段。那么有 t 3  2.5 * (| SH 1 (i,5)  12 |  | ZH 2 ( j,5)  4 |) ' t 3  2.5 * (| SH 1 (i,5)  12 | 18 | ZH 2 ( j,5)  4 |) 并且有 t 4  5  7  6  16 那么该种情况的总时间就有： tt 3 (4, k )  3 * ( SH 1 (i,4)  SH 1 (i,2)  ZH 2 ( j ,2)  ZH 2 ( j ,4)) 2.5 * (| SH 1 (i,5)  12 |  | ZH 2 ( j ,5)  4 |)  16 tt 3 (5, k )  3 * ( SH 1 (i,4)  SH 1 (i,2)  ZH 2 ( j ,2)  ZH 2 ( j ,4)) 2.5 * (| SH 1 (i,5)  12 | 18 | ZH 2 ( j ,5)  4 |)  16 同样的对在 D18 站转地铁的情况对应有： tt 3 (6, k )  3 * ( SH 1 (i,4)  SH 1 (i,2)  ZH 2 ( j ,2)  ZH 2 ( j ,4)) 2.5 * (| SH 1 (i,5)  18 |  | ZH 2 ( j ,5)  11 |)  16 tt 3 (7, k )  3 * ( SH 1 (i,4)  SH 1 (i,2)  ZH 2 ( j ,2)  ZH 2 ( j ,4)) 2.5 * (| SH 1 (i,5)  18 | 18 | ZH 2 ( j ,5)  11 |)  16 通过以上的分析， 可知对由起始站转 T2 再转 T1 最后转到终到站的总时间算 式对应有： tt 3 (8, k )  3 * ( SH 2 (i,4)  SH 2 (i,2)  ZH 1 ( j ,2)  ZH 1 ( j ,4))  2.5 * (| SH 2 (i,5)  4 |  | ZH 1 ( j ,5)  12 |)  16 tt 3 (9, k )  3 * ( SH 2 (i,4)  SH 2 (i,2)  ZH 1 ( j ,2)  ZH 1 ( j ,4))  2.5 * (18 | SH 1 (i,5)  4 |  | ZH 2 ( j ,5)  12)  16 16

17. tt 3 (10k )  3 * ( SH 2 (i,4)  SH 2 (i,2)  ZH 1 ( j ,2)  ZH 1 ( j ,4))  2.5 * (| SH 2 (i,5)  11 |  | ZH 1 ( j ,5)  18 |)  16 tt 3 (11, k )  3 * ( SH 2 (i,4)  SH 2 (i,2)  ZH 1 ( j ,2)  ZH 1 ( j ,4))  2.5 * (18 | SH 1 (i,5)  11 |  | ZH 2 ( j ,5)  18 |)  16 通过以上分析对本题建立了一个角标算式模型， 从而将大量的路线遍历运算 通过简单的算术运算取代， 这样就可以大大提高算法的性能。现对问题 2 的算法 描述如下： 4.05 算法 3 1、对起始点和终到点进行遍历搜索，得到两个点的所有分支。 2、对矩阵 B, C 中第二列右侧（包括第二列元素）的非零元素在 A 进行遍历 搜索，得到所有这些元素的 1 级生成树。并利用连通原则进行判断，找出所有通 路，并按上述存放方式存放通路中的节点信息。 3、运用以上所分析的 11 种时间角标运算式，对以上数据进行处理，就得到 了一条通路的一组运行时间值，将其存放到 tt 3 矩阵的一列上。 4、寻找其中的最小值。 5、再根据最小值通过反向运算，得到路线信息，并输出结果。 根据上面的算法，运用 MATLAB 编写程序见附件[5]对问题 2 进行计算，计算 结果如下表 项目 最少 进入地 转乘地 转 乘地 须乘 转乘公 地铁转 费 时间 铁的公 铁的公 铁 的地 座的 共车的 乘公交 用 交线路 共车站 铁 车站 地铁 公共车 的路线 名 名 线路 站名 83.5 L015 S3068 D8 T1 S3262 41 5 95 L094 S567 D1 T1 4 37 L259 S 3874 D8 T2 4 86.5 L024 S1487 D2 T1 4 17 L021 S1427 D8 T2 4 最少 第一趟 第一次 第 二趟 转车 第二次 第三乘 费 时间 路线 转车站: 路线 次 转车 站 车路线 用 数 106 L084 S2563 L140 2 S1327 L072 3 线路 S3359→S1828 S0971→S0485 S0008→S0073 S0148→S0485 S0087→S3676 不用地铁的情 况 S1557→S0481 最 优 路 线 选 择 地 铁 最 优 路 线 对于问题分析三 3,在考虑步行时间的情况下,假设人也是按照行车的路线 行动,只是任意转变路线没有任何花费,显然步行时间是要比公交车和地铁都要 慢得多,但若只是在行进一到两个车站间的路段,那么由于无须费用且时间损失 不是太大,那么可以在前两个模型的基础上增加一个判断算法,即由算法 4.1 或 4.2 输出的最终结果中,若只是一到两个站的路段那么判断为可以步行,那么对 相应的时间及费用进行从新计算. 17

18. 算法描述 1 得到由算法 4.1 或 4.2 输出的结果,转入步骤 2 2 利用脚标运算,判断在该最佳路线的节点上,否有只包含一道两个公交车 站的路段.若有转入步骤 3,否则终止算法,输出原结果. 3 将对应路段按照步行平均时间,及 0 费用计算出结果并输出该结果. 模型评价 本模型考虑在保证能对问题求出全局最优的条件， 尽量提高算法的运算速 度，以满足用户对快速，方便的需要。所以采取双向搜索以及，角标运算的方法 在不损失算法质量的前提下，减少了大量的运算量，大幅度提升运算速度，并尽 量优化算法结构， 对算法模块自动进行有选择的使用，在无必要的前提下不运行 大运算量的算法模块。在遍历过程中参考启发式算法，通过自动标记标记点，节 省运算次数，做到不做多余的运算，从而提高算法的执行效率。 参考文献： [1] Geogrge F.Luger 著，史忠植译，人工智能-杂问题求解的结构和策略， 北京：机械工业出版社，2004.1； [2] 苏金明等，MATLAB 6.1 实用指南，北京：电子工业出版社，2002.1。 18