标识搜索算法在大型公交查询系统中的应用
标识搜索算法在大型公交查询系统中的应用
摘 要
近年来，城市的公交系统有了很大发展。尤其在大型城市，公交线路在城市交通运输的作用逐年凸现。公交系统畅通、便捷的特点加深了城市居民对其的依赖性。为此，提供一个高效、合理的公交线路自主查询计算机系统将对城市居民产生极大的积极作用。
在问题一中，本文首先对附件中520条公汽线路及其3957个站点的分布状况和排序进行分类存储，以方便模型随时调用和处理。然后分别建立了录入矩阵、运算矩阵及识别矩阵，为实现数据处理的智能化提供保证。根据公交系统的自运行规律，本文提出了标识搜索算法，分别对不同的录入矩阵加以标识，以便在公交系统的自运行阶段提取其内部关系，逐步靠近系统本质，从而有目的地搜索两两站点间的公交线路组合，大大简化了搜索步骤与减少了搜索次数。最后给出针对查询者各类需求的单目标最优选择策略集，以满足不同需求。
在问题二中，采用与问题一类似的建模思想，给出了相应的数学模型和算法。不同之处主要是：在地铁系统与公汽系统的综合存储中，巧妙地将地铁站点录入矩阵转化为复数域，保证原有公汽站点矩阵的稳定性。
在问题三中，又将问题二的结果作了进一步的推广。由于站点间少量的步行对线路的选择会带来更多的灵活性，所以本文在综合考虑步行策略对线路选择影响的情况下，提出了逆向标识搜索算法，在时间、车费和换乘次数三个方面满足了查询者的不同需求，从而找出了多角度下的最优的策略集。
利用本文提出的模型和算法，对问题一中所给出的6对起始站至终点站的最优路线进行了演算，效果良好。
关键字：公交自主查询系统，目标优化模型，标识搜索算法
一、问题的重述
我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。
为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：
1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。
(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485
(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676
2、同时考虑公汽与地铁线路，解决以上问题。
3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。
二、合理的假设
乘客在线路选择决策中都是单目标的，如乘车时间最短，乘车费用最少，换乘次数最少等；
乘客在对线路选择中不受交通状况等外界因素干扰。
乘客在一次出行中不可能重复选择同一条线路。
三、问题一的分析与求解
1．问题一的分析
城市公交系统承担了主要的城市交通运输工作，具有畅通、便捷的特点。但作为一个复杂的交通运营系统，如何提供一种公交线路选择系统，使得既能快速、准确地提供线路选择信息，又能满足查询者的各种不同需求，备受人们关注。
通过附件1.1和附件2.1、2.2所提供的信息，可以得到北京公交系统520条公汽线路与2条地铁线路各自的行驶以及沿途经过的3957个站点的分布状况。本文通过以上数据信息，尝试构建任意两公汽站点之间的线路选择模型。
在对任意两公交线路站点公交线路选择的问题上，由于无法从附件中直接提取线路选择、换乘等信息。因此首先需要对附件中公交线路及站点数据进行有效提取、存储，以便进一步分析，求解。
然后对提取后的站点与各公交线路数据进行分类分析。在保证算法结构清晰、运算量小的目标下，搜寻出两点间所有可能的公交线路选择情况。然后对满足不同查询者的需求状况进行分析求解。
由于查询者的需求具有各自明显的趋向性，如残疾人希望换乘次数最小，上班族希望耗时最小等。因此，应针对查询者各类需求建立单目标最优选择策略。
2、数据预处理
首先根据附表中所提供的数据，以公汽线路为矩阵的行，站点为矩阵的列，建立由3957个站点与520条公汽线路的数量矩阵。
2.1 初始零矩阵的确定
公汽线路可划分为两种情况：环形与非环形。环形路线中公汽从起点出发，回到起点。非环形路线分上、下行，行驶方式由起点到终点，再从终点到起点。由于某些非环形路线的上、下行停靠站点存在一定差异，为此需要每一个非环形路线的上、下行路线单独考虑。
附件中共有520条公汽路线，其中非环形500条。为此，所建立的初始零矩阵应为，其中。
2.2 公汽线路的站点录入
为了利用初始零矩阵，应将1020条公汽路线（含上、下行）依次录入到矩阵中，录入规则为：若第条公汽线路通过站点，则赋值为1，否则为0。
对赋值后的矩阵可表示为，其中。
2.3 公汽线路的站点排序录入
在矩阵中，并未体现各条公汽线路所经站点的顺序。为以下讨论方便，可按下述方式进行排序。对某一公汽线路，若规定第个站点的序为1，则下一个站点的序为2，……。依次对每一条公汽线路的站点进行排序录入，从而得到站点排序矩阵。
以上站点排序矩阵，可以体现各个公汽线路所经历各站点的先后次序，便于统计各站点间所经历的实际站数。
2.4 公汽线路的识别设计
公汽线路行驶方式共有三种：上行、下行和环行。上、下行是往返式的，即对每一站点存在方向相反的行驶方式；环行是环绕式的，即每一站点只存在方向一致的行驶方式。由于不同的行驶方式将影响公汽线路的站数统计，则需要对各种公车线路进行识别。
对公汽线路站点矩阵中的每一行分别进行标记，以判别其公汽线路及行驶模式。标记方式为：
通过以上处理，可以发现，的整数部分代表公汽线路，而小数部分代表其行驶方式。为了使其能够与站点矩阵与排序矩阵同时运算，所以构建相应的识别矩阵：
在识别矩阵中，第一列为运算列，第二列为识别列。
3．两站点间的线路选择模型
要实现公汽线路上任意两个站点和之间的路线选择问题，则需要对所有经过站点和站点的公汽线路进行统计。
首先在站点录入矩阵中分别筛选出所有经过站点和站点的公汽线路集合，分别用矩阵和矩阵来表示。
其中，构建矩阵和矩阵的规则如下：
保留（站点录入矩阵）中的第列中元素为1的所有行，其余各行所有元素均赋值为0，得到矩阵；
保留（站点录入矩阵）中的第 列中元素为1的所有行，其余各行所有元素均赋值为0，得到矩阵；
然后设定搜索算法对各自站点的公汽线路集合进行搜索分析。由于问题1中是一个涉及在1020种不同的公交线路（包含上、下行）3957个站点的公交系统中的搜索算法设计问题，数据量庞大，很难从中找到合适的搜索的算法，使得算法具有结构清晰、运算量小的必要性。为此，我们通过设定一个简单的且随机公交系统。并对此系统进行算法设计、分析，从而推导出能够在大型公交系统中进行有效搜索的算法。首先给出一个简单的例子。
3．1两站点间的线路选择模型的例子
设一公交系统有4条公汽线路，6个不同的站点，分别记为和，各条公汽线路为：
首先对数据进行预处理，将以上公汽系统进行站点录入及排序录入，得到站点矩阵和排序矩阵：
设站点和分别为起始站点和终到站点，首先通过站点录入矩阵来分别构建所有经过站点和的公汽线路集合，分别用矩阵和矩阵来表示：
通过以上处理，分别得到了所有经过站点和的公汽线路集合。然后就是针对矩阵和矩阵，设定算法搜索从站点到所存在的各种乘车途经。
将矩阵和矩阵进行逐行累加，结果如下：
通过逐行累加运算，通过可以看出，在这个公交系统中，经过站点一共有2条公交线路，且通过以上线路，从可以一次到达站点；同理，经过站点的公交线路仅有一条，且通过此线路可一次到达站点。
然后对矩阵与中的数值进行替换，将矩阵中非0数值换为0.2，矩阵中非0数置换为0.3，则有：
在对公交系统的站点矩阵进行处理：
通过上式，将站点矩阵中经过站点和的各行元素均变换为0值，剩余各行的非0值用0.4来替换。最后可变换为：
然后将与逐行加至，得到搜索矩阵：
以上搜索矩阵包含了所有可能的乘车策略，使得只要从中找到固定的组合，即可完成站点到站点的所有乘车决策。
从站点直接到达站点，即不进行任何转乘；
性质1：搜索矩阵中，当第列或第列存在0.5时，则站点可直接到达站点。
证明：0.5=0.2+0.3，又 且，
由于，所有经过站点的公汽线路集合中至少有一条经过站点。
同理易得故当第列存在0.5时，所有经过站点的公汽线路集合中有一条经过站点。故站点可直接到达站点，无需转乘。
证毕。
从站点经过一次转乘，到达站点；
性质2：搜索矩阵中，当第列与第列均不存在0.5且0.9，而其他列存在0.5或0.9时，则存在一次转乘。
证明：由定理1的逆否命题得，当站点无法直接到达站点，则当第列且第列上均不存在0.5。
不妨设第列存在0.5或0.9，
0.5=0.2+0.3，0.9=0.2+0.3+0.4
又 且，，且。
当第列存在0.5或0.9，
中的元素只能取则所有经过站点的公汽线路集合中至少有一条经过站点，且经过站点的公汽线路集合中有至少一条经过站点
站点可在站点进行一次转乘，然后由站点到站点。
其它列类似证明。
得证
从站点经过二次转乘，到达站点；
性质3：搜索矩阵中，某一行同时存在0.6与0.7，则存在二次转乘。
从站点经过三次转乘，到达站点
性质4：搜索矩阵中，存在两个同列的0.4，分别与0.6和0.7同行，则存在三次换乘。
通过以上性质，可得到简单例子的各换乘次数下的策略集，见表1：
表1 站点的公汽运行策略
3.2两站点间的线路选择的一般模型
在上述具体例子中所给出的建模及求解得方法，可以推广到一般的情形。首先对两点所经过的公汽线路进行赋值标识，同时对初始站点矩阵也进行了相应标识。然后，对各级标识进行聚类处理，从而得到一个标识搜索矩阵。最后在搜索矩阵中，应用组合标识的形式逐步对两点间的乘车策略进行搜索，从而得到了两点间所有的乘车策略。其步骤如下：
构建所有经过起始站点与终到站点公汽线路集合矩阵， ；
将与进行逐行累加并进行标示处理，得到各自的标识矩阵；
将三类标示矩阵进行聚类，得到搜索矩阵；
应用组合标示的搜索方式，逐步搜索所有存在可能的两点之间乘车 策略。
当得到了两点之间所有可能的乘车策略搜索之后，再设定返回算法，使得最终确定各种策略具体路线，上下行、环形行驶方式、时间和费用等各类结果。
假设已经搜索得出的两点之间的一种乘车策略为：进行次换乘，每次换乘依次在列进行。则返回的一般性算法为：
将进行换乘的行列变化反映至站点矩阵中，其余并未涉及的全部附为0，得到新的站点矩阵；
提取相应换乘策略中的所涉及的行列，在排序矩阵中保留这些行列，不涉及的行列均附为0，得到新的排序矩阵
对所经历站数的统计：
其中，为识别矩阵。
通过以上返回算法，最终的到的返回矩阵为，第一列表示每次换乘所乘坐的站数，第二列表示曾换乘过的每条路线。从而很清晰地体现了每次换乘所经历的站点数目及相对应的公汽线路。
3.3 公汽线路选择的单点优化
由于每次换乘选择中，尽管在换乘次数上可能一样，但是不同换乘站点将可能导致不同的结果。
若搜索矩阵中存在0.5或者0.9的元素，则可确定两目标站点与之间可以通过一次换乘到达，现设该换乘站点为，其可能有多种不同的换乘站点。
现在，对不同换乘站点进行分段优化计算。对于从起始站点存在一个局部优化，换乘站点到终到站的也存在另一个局部优化。故从最小换乘数应是在满足每段局部最优的前提下的最小值。
从最小经过站点数角度：
其中，表示第段线路所通过的站点数。
从最小费用角度：
其中，为乘坐公汽的费用，该次出行所乘单一票制公交车的次数。
从时间角度：
其中来表示站点到站点所消耗时间，为第段线路停过的站点数，为换乘次数。
从最小换乘次数角度：
3.4 公汽线路选择多点优化
通过公汽线路单目标优化算法的实现，可以得到任意两站点之间在换乘站点数不同情况下的最优的线路组合，下面将研究相同的两站点在不同数目的换乘站点下的比较算法。假设现有和为两个公汽站点，下面求其在不同数目的换乘站点下优值的集合。
表2. 三类目标下的多点线路优化比较图
从上表可以得出在公汽站点和之间，最小需要换乘几次才可以到达，同时表明在换乘站点逐渐变化的过程当中，其消耗时间，花钱的多少等变化情况，并可以依据其规律，求得在减少时间浪费，减少钱的花费，以及在减少换乘站点不同目的下线路所应作出的选择方案。
3.5 六条线路的优化实现
由于查询者的需求是一个主观的需求，但具有明显的趋向性。如残疾人希望换乘次数最小，上班族希望乘车耗时最小等。为此，本文给出针对查询者的主流需求上局部最优线路选择策略，见表2：
表3. 三类目标下的最优化线路选择
[注]表中的[ ]内前一个元素表示车次，车次前的负(-)号表示该车次的下行线，否则为上行线或环行线，后一个元素表示乘该车次要经过的站数。如S3359—[ L-436,31]—S1784表示从站点S3359乘L436下行线经过31个站点到达站点S1784。表3相同。
四、问题二的建立与求解
1. 问题二的分析
在问题一中，本文已解决了公共汽车作为单一的交通线路的选择问题。该问题要求综合考虑公汽和地铁两类系统共同作用下的线路选择问题。
通过附件信息，北京的地铁系统总共分为两条：和。其中为非环形线，为环形线，且围绕着进行环形运转。两线相交于，两个地铁站点，将以上信息形成于北京地铁线路示意图，见图1。
图1. 北京地铁线路示意图
在单一的公汽系统上额外增加两条地铁系统，无疑方便了许多乘客的需求，使公交系统更为完善。通过分析图1及附件中的信息，可以发现此地铁系统具有以下优点：
互通性强。在地铁系统内任意两站点间，最多只需换乘一次即可到达。
速度快。地铁间换乘耗时较公汽短，且相临两站点之间的行驶时间较公汽短。
缓减交通压力。有效实现了线路之间的多选择性，从而对客运能力得到提高。
为此，本文从分析地铁系统的开通对单一公汽系统的好处出发，利用其优点研究所有曾使用地铁路线到达目的地的情况，找出不同换乘次数上的最优策略。最后与单一公汽系统的情况进行比较，提出两地之间的最优乘车策略。
2．数据预处理
2.1地铁系统录入
通过附件2.1和2.2可知，地铁系统的站点分别位于公汽站点上。为此，首先构建一个的零矩阵，将地铁站点信息依次录入，对所有的地铁站点均赋上纯虚数，。
如D01位于公交站点S0567，S0042，S0025上，则对零矩阵的第567列，第42列，第25列的每一行附值：
这样得到了一个地铁系统的站点矩阵：
2.2地铁站点与公汽站点矩阵的综合
根据以上录入的地铁站点矩阵和公汽站点矩阵，将两矩阵相加即得公汽—地铁站点矩阵，即
在矩阵中，上每个元素的实部表示公汽线路站点信息，虚部表示地铁站点信息。
2.3 地铁线路站点数的推算
根据图1，若分别为任意的地铁站点，则从站点乘地铁到所通过的站点数满足：
当均属于（1,23）时，站点到站点所经过的站点数为 ；
当且时，站点到站点所经过的站点数为；
当且时，站点到站点所经过的站点数为。
3．综合考虑公汽与地铁的线路选择模型
3.1建模原则
本模型主要考察增加地铁系统后对线路选择的改进状况。为此，在搜索算法中应以地铁站点作为主要搜索对象，研究利用地铁降低换乘次数、缩短总时间、减少花费金额等方面的各种线路选择策略。
3.2 模型步骤
对任意给出的两个站点、对搭乘地铁前转乘的次数进行逐次分析：
起始站点和终止站点都与地铁站点相连，则和之间可以通过地铁线路到达。若和在同一条地铁线路上，则可以直达，否则，需要换乘地铁站点一次，然后到达。在这种情况下，换乘的次数为1；
若起始站点和终止站点只有一个与地铁站点相连，若与地铁站点相连，则在通过站点的所有线路中搜寻能到达地铁某站点的线路。从中选择一条最短线路。若没有，则不做考虑。地铁站点若在站点，做相同处理。
若和都不在同一条地铁线路上，若到一地铁站点存在公交车直达，且某地铁站点到存在公交车直达，则可先乘公交车再转乘地铁，然后再转乘公交车到达终点，否则考虑更多的换乘次数。
以上乘车策略和其它所有可能的乘车策略（包括地铁）都包函在得公汽—地铁站点矩阵，只要从中找到固定的组合，即可完成站点到站点的所有乘车决策（包括地铁）。其性质及证明可以参照性质1、性质2、性质3、性质4及证明得出。
3.3 模型的实现
分别建立通过起始站点和终到站点的线路的矩阵和。对矩阵和中分别取实部和虚部，并逐行累加得到：
其中：
（1）若在的第列与 中的第列上的系数均大于0，则使用步骤（1）进行求解；
（2）若在的第列与 中的第列上的系数只有一个等于0，则使用步骤（2）进行求解；
（3）若在的第列与 中的第列上的系数均不等于0，则使用步骤（3）进行求解。
3.4 综合考虑地铁与公汽下的最优路线选择。
基于以上所给的算法，同样利用问题一中的六个例子，分别对消耗时间，花费价钱，换成次数三方面进行最优选择，通过计算见表3：
表4. 三类目标下的综合地铁与公汽的最优化线路选择
五、问题三的分析与求解
1．问题三的分析
在问题1和问题2中均不考虑站点间人的步行策略，即使是两个紧邻着的站点。这种考虑显然不符合现实情况，假设从站点到站点，存在次以上的换乘（最小换乘数为）。则乘客将从站点到站点将经历个站点（含、点）。若乘客在这个站点中的某个站点选择步行，跃迁至第个站点，则有可能使之从第个站点一次性到达站点，从而减少换乘次数，显然有可能提高选择效率。
为此，文中将综合考虑步行策略对线路选择的影响，设计新的算法来搜寻有效的步行策略集。从时间、车费，换乘次数三个角度评判满足查询者的不同需求程度，找出多角度下的最优的策略集。
2. 模型的建立
2.1 进行有效的步行策略的前提
现设为换乘站点时的耗费时间，表示各次的换乘情况，设不做跃迁行为下的换乘次数为，每两换乘站点之间的行驶时间为，每做一次换乘其票价为，若不进行步行跃迁，则以下最优的策略集：
其中：为坐车花费时间，为花费的总价钱，为换乘站总数。
若在第次换乘后进行的依次步行，从第个站点跃迁至个站点，从而使自所换乘次数小于的换乘次数，这时
当满足以下情况时，我们就认为此次步行是有充分价值的
2.2 搜寻步行策略
在问题1中，独创性设计了标识搜寻算法，从无换乘策略搜寻至次换乘策略。而在此问题中，需要我们解决的就是采取合适的步行策略，搜寻换乘次数小于的最优线路选择策略。
为此，在解决本问题中，通过对问题1中的标识搜寻算法进行逆向，利用步行策略可任意越迁的优势，从复杂的次换乘策略逆向搜寻至策略，同时综合考虑地铁系统，得到在各自目标下的步行策略。
以下引用问题1中的标识搜寻矩阵与问题2中的地铁站点矩阵：
公汽标识搜索矩阵 地铁系统矩阵
假设在公汽标识搜索矩阵中存在某种三次换乘情况：
在0.4处进行步行跃迁，故可分两步进行逆推算法搜索。
从公汽出发进行逆推
若在行中有元素0.7，跃迁到下一行中存在有0.6，则可以减少0.4的换乘。其推导过程如下：
在逆推标识搜索矩阵当中，，其可以从第二站点跃迁到下一个站点，避免了在0.4处的站点换乘。
从地铁部分进行逆推
当从跃迁到处时，使得与同属于地铁的同一号线或便与终到站同为一条地铁线路，则可以通过地铁线路直接到达。
现假设该线路为公共线路，用来表示：
当乘客在站点，他要到达站点，则可以跃迁至站点，然后通过地铁线路到达站点。
2.3 步行策略的最优化
基于以上两种逆推策略，可以得到三类目标下的最优化
对于时间至上者：
对于省钱为最主要目标：
对于残疾人的最主要目标：
六、模型的评价与扩展
城市公交系统的不断发展，使得公众的出行更加通畅，便利。但这不可避免地加剧了系统的复杂程度，增加了搜索站点间线路选择的工作量。建立了整体模型有优点也存在一定的不足之处。
优点：
模型处理过程中分别建立录入矩阵、运算矩阵、识别矩阵，实现了处理智能化。
模型所建立的标识搜索方法避免了从两头搜索的盲目性，能有效、直观、方便地提取系统内部关系，逐步靠近系统本质，从而大大简化搜索步骤，减少搜索次数。
有待改进之处：
标识搜索算法需要根据系统反馈的值进行分析，且反馈的值越复杂，分析过程越繁琐。若能对该算法做成一个系统实现自动化分析过程，则可避免分析过程耗时过长。
模型的扩展：
我们提出利用元胞自动机的思想来实现对标识搜索算法的自动化处理，动态地对系统反馈的值进行持续分析，从而可以监控系统部分信息更改下的实时预报。为此，在模型的扩展中，我们提出相应的规则：
模型准备：将站点矩阵转化为二维的元胞自动机网格，如图3：
图2：元胞自动机网格
在上图中，每一行表示一种公交车，红格表示该行表示的公交车过该站点。
初始化：搜寻矩阵中 列（站点 ）不为0 为活元胞（后面简称为元胞）；其它为死元胞。
定义：
级数：初始化时设置的元胞为一级元胞，由一级元胞产的子元胞称为二级元胞，依次类推。
父辈元胞：级数低的元胞称为级数高的元胞的父辈元胞。
子辈元胞：级数高的元胞称为级数低的元胞的子辈元胞。
同辈元胞：级数相同的元胞称为同辈元胞。
规则：
跳转规则：元胞在搜寻矩阵中依照排序矩阵依次同行跳转（模拟行车到站的真实次序）。
生成规则：当发现元胞所在列其它行有数字并且行没有存过父辈或同辈元胞，则在下一时刻此处产生一个新的元胞，并继承原元胞的所有信息（模拟所有转乘车的可能情况）。
记忆规则：元胞产生的位置，被继承元胞，跳转的次数，都会被元胞记录下了（记录中转站和转乘车辆，便于信息的反馈）。
消亡规则：当元胞依照排序矩阵跳转最大次顺所在位置时，该元胞在下一时刻消亡，当元胞到达列时，在下一时刻也消亡（避免重复，限制元胞的数量，降低系统复杂度）。
成功规则：元胞在消亡前到达了列，则该元胞成功的到达了列。此时反回该元胞的所有信息。
七、参考文献
[1] 姜启源，谢金星，叶俊. 数学模型（第三版）[M]. 北京：高等教育出版社，2003
[2] Bastien Chopard，Michel Droz著，祝玉学，赵学龙译. 物理系统的元胞自动机模拟[M]. 北京：清华大学出版社，2003
[3] 陈俊，王令群，郑应平. 基于离散模型的双边搜索博弈问题的研究[J]. 科技导报，2007 Vol. 25 No. 2
八、附录
部分程序：
function []=search(m,n,mn)
% 本程序是未考虑地铁的程序,已对路径作了一定删选, 算法主要依据
% <<标识搜索算法在大型公交查询系统中的应用>>,细节处理略有变化.
%
%
% 须要调用 ls.mat, px.mat, ud.mat.
% ls为站点矩阵 px为排序矩阵 ud为上下行矩阵.
%
% 用法: search(m,n,mn) mn<=2
% 注解: m为起始站点 n为终了站点 mn为换乘的次数.
%
% 例: search(0148,0485,2)
% ============二次转乘可以达到目的==========
% 车次 站数 中转站 车次 站数 中转站 车次 站数
% 24 13 3328 -8 29 2265 -104 16
% 0 0 3328 -8 29 2265 469 12
% ............................................................
%
%
% 注解:车次前的负号表示该车次的下行线, 0表示与上一行相同
% 例: 解中第一行表是从S0148乘L024上行线经过13个站点到达S3328
% 再乘L008下行线经过29个站点到达S2265,再乘L104下行线经过
% 16个站点到达终点S0485. 第二行的前两个为0位置表示与上
% 一行的相应位置一样. (也就是第一次乘的车次与上一行一样).
[line1,NO_s1]=search1(m,n);
%======================== 0次转乘 ===========================
if mn==0;
if line1;
disp('===================能直达================');
disp(' 车次 站数 '); disp([line1,NO_s1]);
else;
disp('==================不能直达===============');
end
%======================== 1次转乘 ===========================
elseif mn==1;
line1=abs(line1);load('ls');lsm2=ls;lsn2=ls;
if line1;lsm2(line1,:)=0;lsn2(line1,:)=0;end
lsm2=sum(lsm2(find(lsm2(:,n)~=0),:));
lsn2=sum(lsn2(find(lsn2(:,m)~=0),:));
lsm2(1,m)=0;lsn2(1,n)=0;zz=find((lsm2&lsn2)~=0);%找中转站
if length(zz)~=0;disp('一次转乘可以达到目的');
for j=1:length(zz);
[line21,NO_s21]=search1(m,zz(j));
[line22,NO_s22]=search1(zz(j),n);
if length(line21)~=0&length(line22)~=0;
x1=length(line21);x2=length(line22);
A(1:x1,1:2)=[line21,NO_s21];
A(1:x2,4:5)=[line22,NO_s22];A(:,3)=zz(j);
disp([' 车次 站点数 ',...
'中转站 车次 站点数']);
disp(A);clear A;
end
end
else
disp('=============一次转乘不能达到目的===========');
end
%======================== 2次转乘 ===========================
elseif mn==2
line1=abs(line1);load('ls');load('px');lsm2=ls;lsn2=ls;LS=ls;
if line1;lsm2(line1,:)=0;lsn2(line1,:)=0;end
lsm2=sum(lsm2(find(lsm2(:,n)~=0),:));lsm2(lsm2>0)=1;
lsn2=sum(lsn2(find(lsn2(:,m)~=0),:));lsn2(lsn2>0)=3;
lsm2(1,m)=0;lsn2(1,n)=0;lsmn2=lsm2+lsn2;
lsmn2(lsmn2==4)=0;LSmn2=repmat(lsmn2,1040,1);
LS(find(LS(:,n)~=0),:)=0;LS(find(LS(:,m)~=0),:)=0;
LSSUM=LS+LSmn2;LSSUM(LSSUM==1)=0;LSSUM(LSSUM==3)=0;
LSSUM(LSSUM==4)=i;LSSS=sum(LSSUM,2);
Y=find((real(LSSS)~=0)&(imag(LSSS)~=0));
if length(Y)~=0;
disp('=============二次转乘可以达到目的==========');
else
disp('=============二次转乘达不到目的============');
end
V=[];J=[];VV=[];JJ=[];NN=[];
for u=1:length(Y);
NO=500;
X1=find(LSSUM(Y(u),:)==2);
X2=find(LSSUM(Y(u),:)==i);
for v=1:length(X1);
for j=1:length(X2);
NO_s44=px(Y(u),X1(v))-px(Y(u),X2(j));
NO_s44(NO_s44<0)=1000;
if NO_s44
end
end
if length(J)==0;J=0;end
JJ=[JJ,J];VV=[VV,V];NN=[NN,NO];
end
Y(JJ==0)=[];NN(JJ==0)=[];JJ(JJ==0)=[];Y(NN==500)=[];
JJ(NN==500)=[];VV(NN==500)=[];NN(NN==500)=[];X1=JJ;X2=VV;
for k=1:length(Y);
[line31,NO_s31]=search1(m,X2(k));
[line32,NO_s32]=search1(X1(k),n);
if length(line31)~=0&length(line32)~=0;
x1=length(line31);x2=length(line32);
A(1:x1,1:2)=[line31,NO_s31];
A(1:x2,7:8)=[line32,NO_s32];
A(:,3)=X2(k);A(:,4)=ceil(Y(k)/2).*...
((-(rem(Y(k),2)==0))+(rem(Y(k),2)~=0));
A(:,5)=NN(k); A(:,6)=X1(k);A(:,9)=A(:,2)+A(:,5)+A(:,8);
disp([' 车次 站数 中转站 ',...
' 车次 站数 中转站 车次 站数']);
disp(A);clear A;
end
end
end
%==============================================================
%==================== 0次转乘调用函数 =======================
function[line,NO_s]=search1(m,n)
load('ls');load('px');load('ud');ud(ud==2)=1;
lsm=ls;lsm(find(lsm(:,n)==0),:)=0;lsn=ls;
lsn(find(lsn(:,m)==0),:)=0;lsm=sum(lsm,2);
lsn=sum(lsn,2);Y=find(lsm&lsn);
if Y;
line=ceil((Y/2));line;UD=ud(Y);NO_s=px(Y,n)-px(Y,m);
line(NO_s<0)=[];UD(NO_s<0)=[];line=line.*UD;NO_s(NO_s<0)=[];
else
line=[]; NO_s=[]; UD=[];
end
标识搜索算法在大型公交查询系统中的应用.doc
