深度优先算法（共6篇）
深度优先算法 篇1
前言
随着物流业的发展, 快递行业应运而生, 同时网购的普及更是为快递公司带来丰厚的利润。快递公司在不断谋取利润的同时, 也为我们的生活带来许多方便。就目前我国快递公司的营运状况来说, 一般地, 当所有快件到达某地后, 会集中存放在总部, 然后由业务员分别进行派送。对于快递公司, 为了保证快件能够在指定的时间内送达目的地, 必须要雇佣足够的业务员进行送货, 同时还要选择合适路径以节省送货时间。因此, 确定业务员数量和优化送货路径是快递公司不得不面临的抉择, 显然, 这属于典型的TSP问题。
TSP问题是一个具有广泛应用背景和重要理论价值的组合优化难题, 但问题本身在概念上却很简单:有N个城市, 一个旅行商从某个城市出发, 遍历所有城市后回到出发点, 求一条经过所有城市仅一次的最短遍历路径。其形式化描述为:给定一个连通图G= (V, E, W) , 其中V为顶点集合, E为边的集合, W为边的非负权值集合, 经过连通图所有顶点恰好一次的回路称为Hamilton回路, 记为T, WT为Hamilton回路所有边权值的和, 求WT最小的Hamilton回路。对N个顶点的连通图G, 其不同的Hamilton回路数为 (N-1) !/2。城市管道铺设优化、物流等行业中的车辆调度优化、制造业中的切割路径优化等现实生活中的优化问题都可以归结为TSP来求解。在计算机算法理论中, TSP已经被证明是一个NP-Hard问题, 即找不到一种算法能在多项式时间内求得问题的最优解。这意味着随着问题规模的增大, 很难在较短的时间内求得问题的精确值, 只能找到“亚优解” (Sub Optimal Solution) 。
一、送货策略算法选择
在公司确定快递派送策略时, 通常认为快件是无差别的, 但每次业务员的承受重量是有限的, 即送货过程中存在载重限制。另外鉴于快递行业的特殊性质, 业务员每天的工作时间也是有限制的。合理的快递派送策略需在满足每次送货的载重限制和工作时间限制的基础上, 使得业务员运行的总路程最短, 以此作为目标函数确定需要的业务员的数目以及送货路线。
由于顾客多是散点状分布, 这里涉及分组离散的网络图论问题。在确定派送策略时, 我们可以通过合理的假设, 将其转化为MTSP问题, 因MTSP问题求解难度较大, 可把MTSP问题转化为TSP问题解决, 即可求出总的最短送货路程。以此最短路程为限制条件, 利用基于最小生成树的深度优先搜索算法寻找合适的运行路线, 并结合实际情况中的载重限制, 对找出的运行路线进行调整修正, 即可得出符合要求的运行路线。
下面利用TSP的相关理论对问题进行分析。
(一) MTSP问题原理
给定n个城市 (V1, V2…Vn) , m名旅行商皆以城市V0为基地。 令Wi, j表示Vi城到Vj城的距离。 , 指一条巡回路线 。为巡回的总路程。目标是选择m条巡回路线使总路程最小, 目标函数如下:
当Wij=Wji时, 称为对称型MTSP。
目标函数:以总的运行公里数最短为目标
约束条件:最短路径的约束
注解: (1) , 为0-1变量; (2) 不存在子巡回路;
(3) 因MTSP问题求解难度较大, 所以把MTSP问题转化为TSP解决, 以求解最短路程。
(二) MTSP问题转化为TSP问题来求解
n个顶点, m个旅行商的MTSP问题可以转化为n'=n+m-1个顶点的TSP问题求解。扩大的 (m-1) 个顶点称为“人造顶点”, 其距离矩阵W=[Wi, j]n×n转化为矩阵W'=[W'i, j]n'×n', 设原问题矩阵为:
扩大顶点以后的距离矩阵为:
所以转化后的TSP模型如下:
目标函数:
约束条件:
注解:约束条件 (1) 保证每个派送点只能去送货一次, 停留一次;
约束条件 (2) 保证每个派送点只能离开一次;
约束条件 (3) 有解, 则得到的任何圈一定包含原点, 并且圈
是可行的;
约束条件 (4) 为0-1变量约束;
约束条件 (5) 为非负约束。
(三) 基于最小生成树的深度优先搜索法寻找运行路线
1、根据TSP模型所得的结果, 将它分为d1, d2, …, di满足d1
2、选择最小生成树中任一点为起点, 将该点与原点的最短路程赋值给S1进行深度优先搜索, S1=S1+ (树上连续搜索两点之间的最短距离) , 若S1+ (正在搜索点到原点的最短距离) >d1, 则停止搜索;
3、在以上所找点中找到一条与原点相连且距离在d1限制范围内的一条至少过顶点一次的回路;
4、找到这条回路中所包括点 (除原点外) 中最后搜索的点, 将此点作为寻找回路2的起点;
5、将d1改为d2, …, di重复 (2) ~ (4) ;
6、找出i条回路后, 如此时d1+d2+…+di已比所求的最短路程大或d1, d2, …, di不满足限制条件退出, 否则以步长5改变d1, d2, …, di重复以上步骤。
根据上面的方法求得合理的运行路线即可。
二、实例分析
某快递公司, 假定所有快件在早上7点钟到达, 早上9点钟开始派送, 要求与当天17点之前必须派送完毕, 每个业务员每天平均工作时间不超过6小时, 在每个送货点停留的时间为10分钟, 途中速度为25km/h, 每次出发最多能带25千克的重量。为了计算方便, 将快件一律用重量来衡量, 平均每天收到总重量为184.5千克, 公司总部位于坐标原点, 每个送货点的位置和快件重量如表1所示, 并且假设街道平行于坐标轴方向。为该公司提供一个合理的派送策略 (需要多少业务员, 每个业务员的运行线路, 以及总的运行公里数) 。
点的分布如下:
首先对问题作如下假设:
1、公司总部每次发货的对象是无差别的;
2、尽量满足每条路线负重总量均衡;
3、业务员行走拐弯的时间, 路上的意外事故的耽搁时间忽略;
4、街道平行于坐标轴方向。
显然这是一个多旅行商问题, 可将其转化为单旅行商问题, 而对于TSP (单旅行商) 问题可以利用LINGO软件来求解, 解得最短总路程为492公里。
根据上文提到的深度优先搜索法得到合理的运行路线, 并计算每条路线的公里数和运行时间, 结果如表2所示:
根据每个快递员允许所带重量限定修正上面的结果, 题目中要求的运行时间及重量限制分别为:
原则1:每个业务员工作时间不超过6小时, 送货点停留的时间为10分钟;
原则2:每次出发最多能带25千克的重量;
原则3:考虑每条路线载重量和每个业务员工作时间的均衡。
利用上面的三个原则, 对表2进行修正, 同时组合每个业务员的送货时间, 所得结果如表3所示:
由表3知, 根据工作时间均衡的原则, 分别将路线2和路线8合并, 路线6和路线7合并, 合并后每条路线由一个业务员送货, 因此只需要6个业务员。最终调整后的每个业务员的运行路线如表3和图2所示, 业务员的总运行路程为546公里。
本算法在对题目全面理解和把握的基础上, 根据要求, 对快递派送方案的优化模型采用逼近搜索的方法, 得到近似解。由于派送过程中有负重的约束条件, 使得每个业务员的工作时间较短, 多在4个小时左右, 相较于题目中每个业务员最长工作时间6小时, 表面上看利用率不足。考虑到现实中快递公司多会聘用兼职人员以及混合型员工 (部分时间送货, 部分时间做其他工作) , 因此本文得出的结论很有现实意义。
三、结束语
本文针对快递派送策略的选择问题, 由于目前解决多旅行商问题的直接方法仍不够完善, 故先将多旅行商问题巧妙地转化为单旅行商问题, 利用其成熟的理论进行求解。根据时间限制条件, 结合最小生成树的深度优先搜索算法确定业务员的运行路线, 得到近似最优解, 求解的精度和时间效率都比较高。基于目前快递行业的发展态势, 该算法的得出很有现实意义。另外也可将其应用到其他方面的问题研究之中, 如灾情巡查路线、垃圾处理问题等。
参考文献
[1]薛毅, 耿美英.运筹学与实验[M].北京:电子工业出版社, 2008.
[2]阮怀忠, 张建中.基于改进遗传算法的TSP问题求解[J].安徽建筑工业学院学报 (自然科学版) , 2003, 11 (4) :53-56.
[3]姜昌华, 胡幼华.一种求解旅行商问题的高效混合遗传算法[J].计算机工程与应用, 2004, (22) :67-70.
[4]萧树铁, 姜启源, 高立等.大学数学第二版数学实验[M].北京:高等教育出版社, 2005.
[5]刘育兴, 钟剑.垃圾运输问题的模型及其求解[J].赣南师范学院学报, 2006, 7 (3) :52-55.
[6]耿素云, 屈婉玲.离散数学[M].修订版.北京:高等教育出版社, 2004.
[7]谢金星, 薛毅.优化模型与LINDO/LINGO软件[M].北京:清华大学出版社, 2005.
[8]贺一, 刘光远.紧急搜索算法求解旅行商问题研究[J].西南师范大学学报 (自然科学版) , 2002, 27 (7) :341-345.
[9]毕守东, 胡焱等.最佳巡视路线模型研究[J].安徽农业大学学报, 2000, 27 (2) :178-181.
深度优先算法 篇2
1.1 有向无环图与拓扑序列
集合及在上的偏序关系[1]可以用有向无环图(DAG:Directed Acyclic Graph)表示[2]。其中,V是G的顶点集合,E是有向边的集合,代表了上的偏序关系。连接V中的顶点i,的边{i,j}表示偏序关系R中的一个偏序r。拓扑序列是由某个具有偏序关系的集合得到的该集合上的一个全序序列。对于一个有向无环图,其拓扑序列是顶点的线性排列P,连接顶点的边{i,j}意味着在序列P中顶点i的出现要先于顶点j。而构造这样的线性序列的过程称为拓扑排序[1,2,3,4]。有向图当且仅当无环时才可以拓扑排序,且通常有多个解。
1.2 拓扑排序的基本算法
拓扑排序理论的研究最早是在项目管理日程安排中的计划评审技术(PERT:Program Evaluation and Review Technique的相关背景下出现的(Jarnagin 1960)[5]。拓扑排序算法最早则是由Kahn(1962)提出来的[6]。在计算机科学中,这种类型的应用也出现在计算机指令调度,电子表格中在重新计算公式值时的公式单元评价结果的排序,逻辑综合,执行编译文件中的编译任务的顺序的测定和串行化以及在连接器中的符号依赖关系的解析等。
拓扑排序的基本算法有:源点消去算法、广度优先搜索算法和深度优先搜索算法3种。
(1)源点消去算法又称无前驱顶点优先算法,是最经典、最简单的,也是教科书中最常介绍的关于有向无环图的拓扑排序算法。该算法的伪代码如下所示[7]:
上述伪代码所述的算法的输入必须是有向无环图,其输出序列是图的某一个拓扑序列。若将其中的第一条伪代码修改为如下形式:
则算法输入就允许是一个有向图(无论是否有环)。只需通过判定输出序列中的元素数量是否与图的顶点的数量相同,即可判定图是否有环。即输出序列中的元素数量小于图中顶点的数量,则可判定图中有环;若相等,则图中无环,输出的就是图的一个拓扑序列。
(2)广度优先搜索算法[8,9]常常用于图的最小生成树或顶点之间的最短路径的搜索,当然也能够用于拓扑排序[10]。从本质上来讲,该方法与源点消去算法的基本原理是一样的,是一种更有效的改进方法。广度优先搜索算法首先要在有向无环图中找出所有无入边(入度为0)的顶点(源点),插入到结构S中(结构S可以是集合、队列或是堆栈,但最常用的还是队列)。该算法的伪代码如下所示[11]:
该算法允许输入一个有向图(无论是否有环)。算法的最后的部分给出了是否有环的判定方法。
(3)深度优先算法[8,10,11,12]最早是由Tarjan(1972)发表的。该算法采用递归调用,代码简洁高效,也是针对大规模网络中各种动态拓展研究中最常采用的算法。其伪代码如下所示[11]:
其中visit()是递归函数。采用深度优先搜索算法,首先添加到L中的是首次沿搜索路径查找到的深度优先搜索树末端(该路径最深处的)顶点。L中的结果是拓扑序列的逆序。求逆后就是所求有向无环图的一个拓扑序列。
1.3 问题的提出
拓扑序列是有向无环图的顶点的一个线性序列,在这个序列中,顶点的排列顺序满足边所代表的偏序关系。只有有向无环图才具有拓扑序列。因此,拓扑排序算法的输入通常都是有向无环图。实际上,源点消去法和广度优先搜索法的输入可以是任意的有向图。在这两种算法中,若输入的是带环的有向图,环上的顶点都不是入度为0的顶点,因此不会添加到输出列表中。这样,就可以通过输出列表中顶点的数量判定有向图中是否存在环。若列表中的顶点数量等于有向图中的顶点数量,则有向图无环,列表中的序列就是该图的一个拓扑序列。反之,若列表中的顶点数量少于有向图中的顶点数量,就可以判定有向图中有环,不能进行拓扑排序。但是,对于深度优先搜索拓扑排序算法而言,其输入必须严格限定为有向无环图。这是因为除了有向图中存在的与其他部分不相连的独立的环外,1.2节描述的深度优先搜索算法都能遍历到图中由入度为0的顶点可达的所有顶点,并将遍历到的顶点添加到输出序列中,即这部分图中有环。因此无法像源点消除算法和广度优先搜索算法那样,利用输出序列中顶点的数量准确判定有向图中是否有环,从而无法判定由一个有向图产生的输出序列是否是一个拓扑序列。鉴于上述原因,往往需要先确认给定的有向图是无环的,然后才能使用深度优先搜索拓扑排序算法进行拓扑排序。这就为采用深度优先搜索拓扑排序算法带来了不便和负担。
确认一个有向图是否有环,通常采用的是判定有向图中强连通分量(SCC:Strongly Connected Component)的算法。有向图的强连通分量是图的最大强连通子图,如果一个有向图的每一个强连通分量都是由单个顶点构成的,则这个图就是一个有向无环图[13]。换句话说,当一个有向图的强连通分量的数量等于图的顶点的数量时,这个图就是一个有向图无环图。常见的求解有向图强连通分量的算法有3种:Kosaraju算法、Tarjan算法和Gabow算法,算法的处理过程都比较复杂。首先看看Tarjan算法,其伪代码如下所示[14]:
需要注意其中顶点v的两个变量:v.index和v.lowlink。该算法的处理过程是这样的:遍历V中的顶点v,若v尚未被搜索到,则对v调用递归函数strongconnect()。调用时,计数变量index的值将赋予v的两个变量v.index和v.lowlink,且index值随递归深度递增,同时将顶点v存入堆栈S中。然后,若v的每个邻接顶点w未曾搜索到则调用递归函数strongconnect(),且都是在递归函数返回时,又重新令v.lowlink取v.lowlink和w.lowlink中较小的值;若顶点w已被搜索(已在S中),同样令v.lowlink取v.lowlink和w.lowlink中较小的值。这样,随着递归调用的深入,若顶点v自身就是一个强连通分量(不是环上的顶点),v.index和v.lowlink的值必相等且随递归深度递增,若强连通分量是由若干顶点构成的环,则环上的顶点的v.index的值是随递归深度递增的,而环上所有顶点的lowlink的值均等于该环上值最小的深度优先搜索树根的lowlink。这样,环上的顶点只有“根”(环上第一个被搜索到的顶点)的index值和lowlink值相等,环上其余顶点的index和lowlink是不相等的。于是,每个非环上的顶点的index和lowlink值相等,是一个强连通分量,环上的顶点中只有称为“根”的顶点的index和lowlink值相等,代表一个强连通分量。从而获得了有向图的强连通分量的集合及其强连通分量的数量。显然,当一个有向图中的强连通分量的数量小于其顶点的数量时,说明图中有环。因此,可以利用该算法来判定一个有向图是否有环。
Gabow算法[15]与Tarjan算法的核心思想实质上是相通的。Gabow算法采用两个堆栈P和S来取代v.index和v.lowlink的操作[16],算法略为简洁一点。这两种算法在求解有向图的强连通分量时更受欢迎,因为只需要进行一次深度优先搜索。
如果要使用1.2节描述出的深度优先搜索算法对有向图进行拓扑排序,就需要先利用Tarjan算法或Gabow算法判定有向图中是否有环,然后在无环的情况下,再采用深度优先搜索算法进行拓扑排序。
值得一提的是Kosaraju算法。该算法的伪代码[17]如下所示:
该算法的设计思想非常巧妙。首先,采用深度优先搜索对有向图进行一次搜索,堆栈S中得到一个顶点的序列;其次,将有向图中有向边的方向倒置,获得一个转置的有向图;然后,依次从堆栈S中弹出一个顶点,若该顶点在转置的图中尚未被访问,则以这个顶点为根,对转置的有向图进行深度优先搜索,得到一棵深度优先搜索树,直到S中不存在顶点,就能获得深度优先搜索森林。森林中每棵树中的顶点集合就对应一个强连通分量,树的数量就是有向图的强连通分量的数量。同样,当强连通分量的数量等于图中顶点的数量时,这个图就是有向无环图。有趣的是:当图是一个有向图无环图时,则S中顶点的输出序列就是一个拓扑序列。遗憾的是:该算法还是需要进行两次深度优先搜索。
到目前为止,采用深度优先搜索的拓扑排序算法的都是针对有向无环图的,当输入的是带环的有向图时,则会给出错误的结果。因此,必须事先运行Tarjan算法、Gabow算法或其他可以检测有向图中是否有环的算法确认有向图无环后,才能再进行深度优先搜索拓扑排序。即使采用Kosaraju算法,也要进行两次深度优先搜索才能得到拓扑序列。Yufei Tao(2011)在其关于拓扑排序和深度优先搜索的课件中关于拓扑排序所使用的深度优先算法也只是针对有向无环图的,可喜的是关于拓扑排序算法正确性的证明中有“If v is grey(本文注:指顶点u的邻接顶点v是搜索路径上的顶点),then there is a cycle,i.e.,from v via another path to u,plus edge(u,v).This contradicts the fact that the graph is a dag.”[18]这样的描述,给出了在深度优先搜索过程中判定环的一个思路。下面将给出一个带有环检测功能的只需进行一次深度优先搜索的拓扑排序算法。
2 带环检测的深度优先搜索拓扑排序算法
2.1 伪代码表示
带环检测的深度优先搜索拓扑排序算法(以下简称CD_DfsTS)可以像源点消去拓扑排序算法和广度优先搜索拓扑排序算法一样,允许输入任意的有向图,在一次深度优先搜索的过程中同时完成环的检测和排序操作。一旦检测到图中有环时,立即终止搜索,返回环检出信息。在搜索最终结束后,根据输出序列中元素的数量就能判断图中是否有环。若图中无环,输出序列就是有向图的一个拓扑序列。参照1.2节的广度优先算搜索算法和深度优先搜索算法,给出CD_DfsTS算法的伪代码如下:
CD_DfsTS算法与1.2节描述的深度优先搜索拓扑排序算法基本相同,但由于输入的是无向图(可能有环),因此有一些不同之处:(1)每个顶点的访问情况不再是未被访问和已被访问两种,而是用3种标识,即:未被访问、已被访问和正在访问路径之上来表示。(2)递归函数要返回搜索是否正常完成的状态。(3)根据输出列表中元素的数量判定有向图是否有环。
有了第3种标识,算法中环的检测就变得非常简单了。首先,若顶点n尚未被访问,则先对n设置为在访问路径上,然后对n的所有邻接顶点m进行深度优先搜索的递归调用。若对m的递归调用是非正常返回时,不会将n添加到列表L中,直接返回false;若对n的所有邻接顶点的访问均正常返回,则将n添加到列表L中,这时才将n设置为已被访问过,然后返回true。其次,若顶点n的是正在访问路径之上的点,则判定有环,立即终止递归的调用,返回false。另外,算法隐含的是:若顶点n是已被访问过的,则不做任何处理,直接返回true。算法最终根据添加到L中的顶点的数量来判定图中是否有环。
2.2 算法分析
2.2.1 完备性与正确性分析
若算法的输入是一个有向无环图,从某一个不存在入边(入度为0)的顶点开始进行深度优先搜索的过程中,在搜索路径上遇到的顶点只能是未被访问的和已被访问的顶点两种情况,遇到的是未访问(unvisited)的顶点,才设置为在搜索路径上(on searching path),在递归返回时,再设置为被访问过(visited)。其过程与传统的深度优先搜索相比,除增加了设置在搜索路径上的标识及返回和判断搜索是否正常完成的状态以外,其余是完全相同的。对于输入的是有向无环图而言,算法的完备性与正确性毋庸置疑。因此,只需分析当输入的是带环的有向图的情况。
若输入是带环的有向图时,可分为两种情况:第一种情况:若有向图存在一个或一个以上的由独立的环构成的连通分量,由于这些环不存在入度为0的顶点,因此CD_DfsTS算法不会搜索到这些顶点,因此也不存在将其中的顶点添加到输出列表中的可能性,这样,输出列表中元素的数量必然小于有向图中顶点的数量。第二种情况:环是处在CD_DfsTS算法可搜索到的连通分量之中。算法搜索到环时会立即终止搜索,且在返回时不会再将顶点添加到输出列表中,输出列表中元素的数量也必然会小于有向图中顶点的数量。CD_DfsTS算法的搜索分为3种情况:(1)当搜索过程中遇到的是已被访问过的顶点时,则直接返回。(2)当搜索过程中遇到是未曾访问过的顶点时,则设为在搜索路径上,继续沿有向边搜索。当搜索到头时,依次返回,返回时将顶点存入列表L中,并将顶点设置为被访问过的。返回过程中遇到新的分支时,继续沿新的分支进行搜索。(3)搜索时遇到搜索路径上的顶点时,则判定检测到环,从而终止搜索。1和2与传统的深度优先搜索算法是相同的,因此只要证明搜索时遇到的搜索路径上的顶点是环上的顶点即可。
定理使用CD_DfsTS算法对有向图进行深度优先搜索时,若搜索过程中遇到当前搜索路径上的顶点,则该顶点是环上的顶点。
2.2.2 运行时间分析
分如下两种情况:
(1)输入的是有向无环图
在这种情况下,CD_DfsTS算法与传统的深度优先搜索算法相比,只是在返回前多了一次对顶点访问标识的设置,另外多了一次对递归调用返回状态的判定,通常认为这些操作所占用的时间都是可以忽略不计的。除此之外,对边的搜索和对顶点的访问处理和传统的深度优先搜索算法是完全相同的。因此,其运行所需时间也是[11]。
(2)输入的是有向有环图
2.3 算法的具体实现
这里给出一个用C++语言描述的已在实际应用中的CD_DfsTS算法的具体实现。
2.3.1 算法使用的数据结构
在深度优先搜索算法中关于边的邻接关系的最常使用的数据结构有邻接矩阵和邻接表。本文给出的关于边邻接关系的数据结构采用的是边集数组。在这里,边集数组中的元素采用的是由边的起始顶点的编号和终止顶点编号构成的结构体,初始化时,其中的元素按终止顶点编号为主序起始顶点编号为辅序的方式进行排序,以便在对该数组进行查询时,可以使某个顶点的邻接顶点按编号由小到大的顺序进行操作。
边集数组元素和数组的定义如下:
struct Edge//边信息结构体
顶点的标注(Label)可以是从0或从1开始的数字,也可以是字母甚至是单词或短语。因此,表示顶点的数据结构采用的是关于顶点标注的字符串数组,初始化时,元素的顺序是按顶点编号由小到大排列的。定义如下:
CStringArray m_saNodes;//顶点标注字符串数组
此外,还定义了对应每个顶点的访问标识和入度的整数数组指针,当程序初始化时,根据实际操作中顶点的多少动态地用new命令创建这两个整数数组,并将数组的地址赋给相应的指针,数组中的元素的顺序是按顶点编号由小到大排列的,m_Visited指向的数组中的元素都初始化为0(unvisited),m_Indegree指向的数组中元素初始化为对应顶点的入度。定义如下:
2.3.2 实现代码
3 结语
给出的CD_DfsTS算法不需要进行专门的有向图是否有环的检测和判定,为深度优先搜索拓扑排序提供了直接有效的方法。特别是对具有海量数据的有向图进行拓扑排序时,更加彰显其高效、简洁和便利,在实际应用中具有良好的效果。该算法对深度优先搜索算法做出了一个很有实际应用价值的拓展。
摘要：提出了一种带环检测功能的深度优先搜索拓扑排序算法,详细介绍了几种基本拓扑排序算法,分析了带环检测功能的深度优先搜索拓扑排序算法的意义和作用,并证明了该算法的完备性和正确性,给出了该算法的用C++编写的实现代码。
深度优先算法 篇3
对于用顺序法表示的二叉树,各结点在数组中的编号很有规律,其周游较容易进行,但对于用链式存储结构表示的二叉树,进行周游就复杂一些,仅讨论二叉链表存储的二叉树的周游算法。首先讨论深度优先周游二叉树的递归算法,然后研究深度优先周游二叉树的非递归算法。
1 深度优先周游二叉树的递归算法
前序法(DLR)的递归定义是:若二叉树为空,则空操作;否则:访问根结点;前序周游左子树;前序周游右子树。
中序法(LDR)的递归定义是:若二叉树为空,则空操作;否则:中序周游左子树;访问根结点;中序周游右子树。
后序法(LRD)的递归定义是:若二叉树为空,则空操作;否则:后序周游左子树;后序周游右子树;访问根结点。
深度优先周游二叉树的次序是递归定义的,因此其递归算法是很容易实现的。若二叉树的二叉链表存储结构定义为:
则3种深度优先周游二叉树的递归算法分别为:
从上述深度优先周游二叉树的定义可知,3种周游算法的不同处仅在于访问根结点和周游左、右子树的先后关系。深度优先周游二叉树的递归算法的实现,在系统运行时是借助栈来完成的。以图1所示的二叉树为例,分析栈的变化过程。前序周游二叉树与中序周游二叉树时,栈的变化相同,而后序周游二叉树则稍微复杂一些。如表1、表2和表3所示。
2 二叉树的非递归周游算法
根据上述二叉树周游时的栈的变化情况,可以看出:二叉树的前序周游和中序周游时栈的变化情况完全相同,不同的是前序周游时,进栈时访问元素;而中序周游时,出栈时访问元素。由此设计二叉树的DLR和LDR的非递归周游算法如下:
使用栈进行前序周游时,遇到一个结点,就访问该结点,并把该结点推入栈中,然后下降去周游它的左子树。周游完它的左子树后,从栈顶托出这个结点,然后按照它的右孩子指针指示的地址再去周游该结点的右子树。
使用栈进行中序周游时,遇到一个结点,就把它推入栈中,并去周游它的左子树。周游完它的左子树后,从栈顶托出这个结点并访问之,然后按照它的右孩子指针指示的地址再去周游该结点的右子树。
使用栈进行后序周游二叉树时,遇到一个结点,把它推入栈中,去周游它的左子树。周游遍它的左子树后,还不能马上访问处于栈顶的结点,而是要再按照它的右孩子指针指示的地址去周游该结点的右子树。周游遍右子树后才能从栈顶托出该结点并访问之。为此,需要设一个标志,以标识右子树已被周游。算法中设置了一个指针标志pre,表示刚刚访问的结点。如果当前结点的右孩子为pre,就说明右子树已被访问,接下来是访问当前结点了。
3 深度优先周游二叉树的算法性能分析
上述深度优先周游二叉树的递归算法与非递归算法的时间复杂度均为O(n),空间复杂度在理想情况下为O(log 2n),如二叉树退化为单支树时,则空间复杂度为O(n)。
由于递归算法结构清晰,程序易读,而且它的正确性容易得到证明,因此,利用允许递归调用的语言进行程序设计时,给用户编制程序和调试程序带来很大的方便。因为对这样的一类递归问题编程时,不需要程序员而由系统来管理递归工作栈。而非递归算法更方便读者理解工作栈的变化情况,但需要程序员决定栈所占据的存储空间大小,为保证二叉树周游不至于因为栈溢出而进行不下去,就需要给栈分配足够的存储空间。
摘要：给出了深度优先周游二叉树的前序、中序、后序的3种递归算法,在分析了周游二叉树的递归算法中的工作栈的执行过程的基础上,设计了先序、中序、后序周游二叉树的非递归算法,对深度优先周游二叉树算法的性能进行了分析。
关键词：二叉树,周游,递归,非递归,栈
参考文献
[1]严蔚敏,吴伟民.数据结构(C语言版).清华大学出版社,2010.
深度优先算法 篇4
迄今为止, 对于该问题的研究均是基于绘制于同一图层的电网模型, 如面向图形对象的电力网络建模拓扑分析法、深度优先搜索法、Petri网络法、广度优先搜索法等。但上述方法并不适用于厂站分布管理采用多图层操作的电力网络。
本文针对厂站分布管理系统的特点进行了研究, 提出了深广度搜索相结合的电网拓扑分析方法。该方法在拓扑分析过程中, 以厂站作为基本节点进行站间广度优先搜索, 每遍历到一个厂站节点后, 对站内设备网络进行深度优先搜索。在完成一次拓扑遍历后, 实现元件带电状态确定、带电着色、非阻抗元件的节点融合、元件节点编号和确定系统子网的功能。相较于现有其它拓扑分析方法, 本文方法适用于电网按厂站进行分布式管理的方式。
1 电力网络分布式图形建模
1.1 厂站内电力元件图形建模
文献[1, 2]提出了电网拓扑图形建模的图元类──电力元件类 (PElement) 。在此大类中, 所有实际设备被归为几种不同类型的元件, 以不同图元区别表示;图元定义有端口属性, 用端口则可建立元件之间的连接关系。电力元件类所包括的子类为:功率类, 节点类, 开关类, 阻抗类等;每个子类所包括的设备如图1所示。因此, 所有设备均包括在电力元件类中。
为了实现按厂站进行的分布管理, 现定义一个新的元件子类-厂站图元 (STA) 。该图元表示一个厂站, 通过它实现厂站之间的连接, 它与其它子类的关系示于图1中。
图1中每一元件的属性包括:元件类型号 (PType No) 、带电状态 (PState) 、元件颜色 (PColor) 、电压等级 (PVoltage) 、站内子网序号 (Sta No) 和系统子网序号 (Net No) 。
其中, Net No属性值可把整个电力网络划分为若干联通子网络;Sta No用于站内深度优先搜索过程中辨识厂站的接线关系, 标记出站内联通子网络。Net No在此基础上利用全网广度优搜索可以快速地确定厂站间各个子网的联通关系, 把整个电力网络划分为若干联通子网络。
1.2 厂站间网络图形建模
地区级的电力网络可能包括数十个甚至数百个不同电压等级的变电站, 只有基于不同电压等级的电网分布式管理才能适应实际管理需要。因此, 电网也应该建立多层模型。以厂站作为基本单位, 通过厂站间联络线建立网络架构模型。
2 深度广度相结合的电网拓扑算法
2.1 站间广度遍历和站内深度遍历
如前所述, 网络架构模型把厂站看成单位节点, 厂站间的联络线是连接节点间的支路。广度优先搜索法适用于厂站间遍历。发电站是遍历起始节点, 根据联络线的连接关系逐层搜索外层厂站。当遍历前进到底层厂站, 该次广度优先搜索完毕, 形成一个系统联通子网。
利用深度优先搜索算法[1]遍历站内接线, 能在完成一次遍历后, 同时确定元件带电状态、完成无阻抗元件融合、实现元件带电着色、赋予有效节点编号及处理站内孤岛系统。
深度优先遍历分为前进和回溯两个过程:前进即优先向更深层节点遍历;回溯就是逆向遍历。回溯的起始于前进至网络的某个终端 (如遇到断开的开关类元件) , 结束至回溯到上一个未经搜索的网络分支。每结束一次回溯就完成了一个分支网络的遍历。当某次回溯完成后没有节点可继续前进过程是, 厂站内子网就完成了一次深度优先遍历。
通过联络线联通的所有厂站及其站内元件均划分为同一子网, 赋系统子网号 (Net No) 。站内遍历到的元件赋站内子网序号 (Sta No) ;节点编号分配以上一搜索厂站编号为基础, 同时考虑遍历元件阻抗属性;元件带电状态 (PState) 需要判断元件是否与搜索的起始元件存在电气通路;元件着色 (PColor) 与否由其带电状态决定, 遍历到的元件均会进行着色。
2.2 广度优先搜索结合深度优先搜索
厂站间的连接关系是通过联络线建立的。广度优先搜索每向前遍历一层厂站, 就是将与上层厂站相连但未经遍历的厂站作为新一层厂站。该新层厂站是从连接至上层厂站的联络线进入, 同理若要继续遍历下一层厂站, 则必须确定本层厂站的联络线出线。因此, 广度优先搜索到每一个厂站节点后就要对该站内子网进行遍历, 及转入站内深度优先搜索。该层所有厂站完成站内深度优先搜索后, 根据遍历结果再回到站间广度优先搜索并继续前进至下一层厂站。
假设站间广度遍历前进至第n层, 设该层共有m个厂站, 分别为STn, 1, STn, 2至STn, m。每个厂站与第n-1层节点的联络线分别为wn, 1, wn, 2, …, wn, m。此时暂停网络广度遍历, 以各条联络线为起点前进到下层连接厂站, 转入站内深度优先搜索。以STn, 1为例, wn, 1为站内深度优先搜索的拓扑起始元件, 依据前所述方法遍历出该厂站内的联通网络, 同时标记出搜索到的新联络线元件, 设有wn+1, 1, wn+1, 2~wn+1, l共l条;然后从wn, 2开始同理对STn, 2进行站内深度遍历, 搜索到新联络线wn+1, l+1~wn+1, l+k共k条。若有厂站完成站内深度遍历后不存在起始联络线之外的新增联络线, 则该厂站不与外层厂站相连, 即为此遍历分支的底层厂站。若本层最后一个厂站STn, m完成站内深度优先遍历后, 除去起始联络线之外的新增联络线共找到wn+1, s条, 即本层厂站共有s条联络线连接到下一层厂站。这s条联络线就确定了前进到下一层厂站STn+1, i (其中i为第n+1层厂站的标号) 的连接关系, 全网广度优先遍历就由第n层前进至第n+1层。对n+1层厂站继续重复上述站内深度遍历, 完成后再转入站间广度遍历前进至n+2层, 最后直到所有分支节点都前进到底层厂站为止。
3 算例
给出一个包含两个发电站和两个厂站的简单示例系统。为简洁与方便, 此处略去了所有IS, 仅保留必要的开关类元件BK。系统厂站联络图示于图2, 站内接线分别为图3~图6。
为示例完整性, 现断开发电站1中的连接三卷变TШ-1和母线B3的BK。显而易见, 该站的右半部分将单独形成一个子网。
拓扑分析以发电站1作为起始节点。首先对发电站1进行站内深度优先搜索, 以G1为起始节点。与G1联通的站内深度优先搜索完成后, 转入广度优先搜索前进至第二层节点。发电站G1有联络线L1-B连接厂站1, 则厂站1确定为第二层节点的一个厂站, 继续转入对厂站1的站内深度优先搜索。然后找到联络线L2-B, L2-B连接到厂站2。厂站2完成站内深度优先搜索后, 再由L3-B同样找到该厂站, 则判断第二层两个厂站搜索结束。同理, 根据该层联络线出线继续前进找到第三层仅有发电站2, 且判断为底层节点。故完成第三层搜索后对该联通网络的拓扑分析过程完毕。
第二个子网的遍历从发电站1的G2开始。由于该子网仅限于发电站1内部, 故只需进行一次站内深度优先搜索。完成对第G2联通子网的遍历后, 搜索发电机元件不存在未经遍历的, 全网拓扑分析过程结束。示例系统通过拓扑分析形成的等效图如图7。
4 结语
本文研究了电力网络按厂站分布管理模式下的网络拓扑分析问题。在电力网络按厂站图形建模此基础上, 提出了深度广度相结合的电力网络拓扑分析方法。该方法在完成一次网络拓扑分析后, 可确定元件带电状态、进行无阻抗元件的节点融合、元件带电着色、有效节点编号及划分系统子网的功能。最后, 给出了简单示例系统说明该拓扑分析方法的实现过程。这为在此基础上进行电力系统的研究分析以及软件扩展功能模块的扩展提供了必要的支持。
参考文献
[1]林济铿, 覃岭, 罗萍萍.基于图形建模的电力系统拓扑分析新方法[J].电力系统自动化 (Automation of Electric PowerSystems) , 2005, 29 (22) :54-59.
[2]林济铿, 覃岭, 罗萍萍.基于Visual Graph的电力图形系统开发[J].电力系统自动化 (Automation of Electric PowerSystems) , 2005, 29 (15) :73-76.
[3]邓佑满, 张伯明.网络拓扑着色算法在电力系统中的应用[J].电力系统自动化 (Au t oma t i on of E l ec t r i c P o w erSystems) , 1998, 22 (10) :7-9.
[4]赖晓平, 周鸿兴.电力系统网络拓扑分析的有色Petri网络模型[J].电网技术 (Power System Technology) , 2000, 24 (1 2) :5-1 0.
[5]王元驰, 肖先勇, 邓武军.一种基于邻接关系和广度优先搜索的网络拓扑分析方法[J].四川电力技术 (Sichuan ElictricPower Technology) , 2007, 30 (2) :29-32.
用广度优先搜索算法实现路径搜索 篇5
关键词：广度优先搜索,VC语言
路径搜索是许多游戏特别是即时战略游戏的核心组成部分, 玩过即时战略游戏 (如红色警报) 的朋友们对此一定都不陌生。在这类游戏中, 玩家不需要控制游戏主角的每一步移动, 只需用鼠标点击一下目的地, 游戏主角就可以自己移动到那里。那么游戏是如何实现路径搜索的呢?实现路径搜索的算法又是什么呢?下文就以一个简单的路径搜索为例, 说明上述问题, 并给出VC++的程序实现。
1 路径搜索的实现方法
路径搜索是一个寻径问题, 所谓寻径问题, 就是在地图上的起始点A和目的点B之间寻找一条可通行的路径。显然, A和B之间可以有很多条路径, 目的就是用最短的时间找到一条最佳路径。寻找最佳路径, 其本质就是搜索, 是一个从初始节点出发, 沿着与之相连的边试探前进, 寻找目标节点的过程。
路径搜索的基本算法主要有盲目搜索和启发式搜索两种, 进行盲目搜索时, 扩展节点不估计路径代价, 是比较常用的方法, 下文采用一种盲目搜索算法——广度优先搜索算法来实现即时战略游戏中的路径搜索。
1.1 广度优先搜索算法简介
广度优先搜索算法把起点作为初始节点, 从初始节点开始, 应用算法生成第一层节点, 检查目标节点是否在这些后继节点中。若没有, 再用算法将所有第一层的节点逐一扩展, 得到第二层节点, 并逐一检查第二层节点中是否包含目标节点。如此依次扩展、检查下去, 直至发现目标节点为止。这里采用的原则是先生成的节点先扩展, 为满足这一要求, 采用“队列”这一数据结构来存储节点, 队列设置两个指针:open指针和closed指针, open指针指向扩展得到的节点, closed指向已检查过的节点。当open=closed时, 表示队列空, 当open大于队列长度时, 表示队列溢出, 如图1所示。
1.2 路径搜索的实现过程
为了具体说明广度优先搜索算法在即时战略游戏中的应用, 以一个简单的路径搜索为例, 构造一个二维地图, 如图2所示, 把地图均匀划分为若干个小方格, 在图2中共3*3个方格, 游戏主角位于一个方格中, 我们选中其他任一个方格作为目的地, 点击鼠标, 游戏主角自动选路移动到目的方格。为了更加逼近现实情况, 可以设置某些方格为障碍物, 即游戏主角必须绕过障碍才能前进。例如, 方格编号如图2所示分别为1、2、……、9, 游戏主角位于方格1中, 方格5为障碍物, 玩家要使主角移动到方格9中, 那么广度优先搜索算法把1加入队列, 此时队列包含{1}, 检查1是否目标节点, 不是目标节点则继续搜索, 从1开始搜索相邻节点, 这是第一层搜索, 得到方格2和4, 检查2和4, 不是目标节点, 则2、4进入队列, 队列包含{1, 2, 4};进行第二层搜索, 由2搜索相邻节点得到3, 也搜索到了5, 但是方格5是障碍物, 不能加入队列, 由4搜索到7, 检查3和7, 不是目标节点, 于是3、7进入队列, 队列包含{1, 2, 4, 3, 7};继续第三层搜索, 由3得到6, 由7得到8, 检查6和8, 不是目标节点, 于是6、8进入队列, 队列包含{1, 2, 4, 3, 7, 6, 8};继续第四层搜索, 由6得到9, 检查9是目标节点, 于是结束搜索。为了记住搜索的路径, 在搜索过程中, 设计数据结构记录每一个节点的前趋节点, 如2的前趋节点是1, 这样, 在找到9之后, 可以根据前趋节点回溯到节点1, 回溯过程是9、6、3、2、1。可以用“栈”这一数据结构保存回溯过程, 压栈顺序为9、6、3、2、1, 这时, 游戏主角可以按路径移动, 移动按出栈顺序进行, “栈”是后入先出的数据结构, 于是, 主角就按1-2-3-6-9的顺序完成移动。
2 程序实现
下面给出广度优先搜索的程序实现。选用VC++6.0作为程序开发平台, 建立基于对话框的工程。程序设计的关键是: (1) 编写广度优先搜索类, 用于随机生成二维地图, 并且实现路径搜索。 (2) 实现游戏主角在地图中移动。
2.1 实现广度优先搜索的类CBfs Map
下面依次介绍CBfs Map类的成员函数。
函数void Init Map () 用于初始化地图, 并随机设置障碍物。
函数void Search Path () 用于路径搜索:
2.2 实现主角在地图中移动
创建一个基于对话框的类CBfs Dlg, 在类中添加按下鼠标左键的消息响应函数On LButton Down () , 该函数根据鼠标左键点击的位置, 进行路径搜索, 代码如下:
程序运行情况如图3所示, 界面中红色栅格表示障碍, 白色部分表示通路, 当玩家点击任意空白处, 游戏主角能够自行移动到该位置。
3 结语
介绍了一种采用广度优先搜索算法实现路径搜索的方法, 并给出了原理及关键数据结构。虽然代码不多, 却实现了一个较为完整的路径搜索实例, 希望能对游戏编程爱好者们起到积极的参考作用。
参考文献
深度优先算法 篇6
城市交叉口是交通的瓶颈, 车流的延误主要发生在交叉口信号阻滞。利用交通信号控制方法减少公交车在交叉口产生的延误, 保证公交运行的快捷、准点, 为居民出行提供更大的便利。因此公交信号优先手段是实现“公交优先”战略的重要技术手段之一。公交信号优先控制是一种对公交车辆的利益优先考虑的信号配时技术, 依据检测到的公交车辆和社会车辆的信息, 通过信号配时技术优先公交车辆在交叉口通行权, 达到的公交优先的目的[1]。
介于以上背景, 本文主要研究常规公交信号优先控制算法, 主要包括单相常规公交优先信号控制算法和多相常规优先信号控制算法, 研究成果为城市交通信号控制系统设计提供理论依据。
1常规公交系统公交信号优先控制系统
公交优先信号控制系统由公交信息采集模块、公交信息传输模块、公交信息储存及处理模块、公交信号优先服务模块、交叉口运行效率评价模块五个部分组成[2], 如图1。
1.1 公交信息采集模块
公交信息采集利用安装在信号交叉口和公交车上的检测器对公交车流数据进行采集, 从而获得公交车的速度、位置等信息;主要根据公交信息检测需求, 在不同位置布设公交检测器, 本模块是公交信号优化控制系统的基础模块, 直接关系到公交信息的获取方式及相关的公交信号优先算法。
1.2 公交信息传输模块
公交信息传输通过通信链路将其采集到的公交车数据传输至信号机或者控制中心;是联系公交信息检测器及控制机或控制中心的中间链路。本模块根据公交检测器的类型选择不同公交信息传输方式并根据公交信号优先控制方式选择公交信息传输路径, 最后将检测器采集到的数据信息传输到信号机或者控制中心。
1.3 公交信息存储及处理模块
本模块对上传的公交信息进行筛选、存储, 并根据上传数据提取出所需的信息, 如车速、位置等, 为公交信号优先系统的控制算法提供支持, 从而将控制算法得到的优化结果传输至信号机中。
1.4 公交信号优先服务模块
本模块主要是指信号机获得控制中心或信号机自身的处理器所处理的信息后, 通过信号机显示公交信号优先结果以给公交车提供优先服务。
1.5 交叉口运行效率评价模块
由于公交信号的优先, 打乱了该交叉口的信号配时, 因此该模块分析公交信号优先服务对整个交叉口的运行效率及服务水平造成的影响, 从而使得公交车的优先不会造成交叉口服务水平下降。
2 单相常规公交优先信号控制算法
单相常规公交优先信号控制即只有一个相位有公交车的公交信号优先控制方式。这种情况下, 公交车流量较小, 优先级别较高, 但是不可忽视公交车信号优先对社会车辆造成的影响, 要实现在不造成其它相位车辆发生拥堵情况下, 尽量减小公交车的延误并使其通过交叉口[3]。
2.1 公交车红灯期间到达优先算法
公交车在红灯期间内到达检测器说明目前显示绿灯相位不是公交相位, 那么在非公交相位的检测时刻就要对公交车的优先方式进行选择[4]。具体控制算法如下:
1) 安装在公交专用道上的检测器每检测到一辆公交车, 就根据时间预测模型预测这辆公交车到达交叉口停车线的时刻, 并把这些预测数据存放在公交车到达数据库中。
2) 在非公交相位, 通过检测器获取公交车的到达时间数据, 判断在上一周期公交相位绿灯结束时刻与本周期当前相位压缩绿灯时间结束时刻之间是否已经有公交车停车等待要通过交叉口。如果已经有公交车停车等待, 则在当前相位压缩绿灯终止时刻提前启亮下一相位绿灯;否则, 继续下一过程。
3) 判断在当前相位的压缩绿灯时间和基础绿灯时间内是否有公交到达交叉口停车线。若有公交车到达停车线, 则要压缩当前相位绿灯相位时间, 并以当前相位的压缩绿灯时间为最小值, 选取最早到达停车线的公交车的到达时刻作为当前相位的绿灯终止时刻;否则, 等到当前相位基础绿灯时间结束后再启亮公交相位。
其具体控制流程如图2所示。
2.2 公交车绿灯期间到达优先算法
公交车在相位绿灯时间内到达检测器说明当前显示绿灯相位是公交相位, 那么在公交相位的检测时刻就对公交车的优先方式进行选择[5]。具体控制算法如下:
1) 安装在公交专用道上的检测器每检测到一辆公交车, 就根据时间预测模型预测这辆公交车到达交叉口停车线的时刻, 并把这些时间数据存放在该方向的检测数据库中。
2) 在公交相位的检测时刻, 根据检测器检测到的公交车的到达情况, 并依据上一周期公交相位的优先状态和各相位的显示绿灯时间等数据, 计算本周期公交相位的最大绿灯时长。
3) 根据检测器在公交相位检测到的数据, 判断当前相位到达的所有公交车中是否有一些公交车在在临界绿灯时间和最大绿灯时间之间到达交叉口停车线。若有公交车到达停车线, 那么就继续当前相位, 且选择满足条件的时刻中最大值作为该相位的终止时刻。如果没有公交车到达停车线, 则根据上一周期公交相位优先状态确定本周期各相位绿灯时间的执行, 并对非公交相位进行补偿。
其具体控制流程如图3所示。
3 多相常规公交优先信号控制算法
多相常规公交优先信号控制是指多个相位均有公交车到达, 需要权衡多相位公交优先权的控制方式。与单相常规公交优先信号控制相比, 这种情况下公交车流量较大, 优先级别较低。须考虑各个相位公交车的到达情况, 同时还要保证非公交相位不发生交通拥堵。当多个相位都有公交车到达的情况下, 采用就近原则的控制方式, 即当前相位到达的公交车优先级别最高, 非当前相位的公交车的优先级别按本周期后续各相位显示顺序逐次递减, 离当前相位越近, 越优级别越高。多相常规公交优先信号控制中公交车辆的延长和压缩范围相对较小, 各个公交相位相互限制[6]。
假设在t0时刻控制中心接到检测器发来的i相位的公交优先申请, 首先判断在t0时刻i相位显示绿灯还是红灯。
若此时i相位正显示绿灯, 那么就对i相位进行绿灯延长处理, 使该公交车在最大绿灯时间内通过交叉口, 绿灯延长的极限为最大绿灯时间。同时, 查看其它相位是否有公交优先申请, 若其它相位也有公交优先申请, 使得i相位绿灯时间正在被压缩, 则根椐就近原则, 跳出压缩模块, 先对i相位进行绿灯延长处理, 并保留其他相位的公交优先申请。
若此时i相位正显示红灯, 则判断该公交车到达交叉口停车线的时刻t1在i相位的灯色。若该公交车到达交叉口停车线的时刻t1交叉口显示绿灯, 则该公交车可以直接通过交叉口;若t1时刻i相位显示红灯, 则首先查看其他相位是否正在进行绿灯延长处理, 若有某一相位正在绿灯延长, 那么需要等待其相位绿灯延长处理完之后, 再考虑i相位的公交优先申请。接着再判断下一显示绿灯相位是否为i相位, 如果是i相位, 就对当前相位进行绿灯压缩处理;如果不是i相位, 则对当前相位进行绿灯压缩处理后, 仍然保留优先申请, 继续判断。
其具体控制流程如图4所示。
多相常规公交优先信号控制实际上包括两层, 第一层为常规公交优先信号控制总体流程, 如图4所示。在每次循环后, 根据流程图中的每个判别状态, 进入相应的处理模块 (包括绿灯延长模块和绿灯压缩模块) 。第二层是第一层的子流程, 包括绿灯延长模块控制流程和绿灯压缩模块控制流程。
绿灯压缩模块控制流程, 运用在当前相位没有公交车到达, 而其它相位有公交车到达的情况下。是指对当前显示绿灯相位进行绿灯时间压缩的处理过程, 控制方法是缩短当前相位的绿灯时间, 提前启亮下一相位绿灯。
绿灯延长模块控制, 是对当前相位的显示绿灯时间进行优化的过程, 它是运用在当前显示绿灯相位有公交车到达的情况下。在绿灯延长模块中, 首先判断公交车到达停车线的时刻在本相位是否仍然显示绿灯, 若仍是绿灯, 则该公交车直接通过交叉口;若显示红灯, 则需要以最大绿灯时间为限制, 接受公交优先申请, 延长该相位的绿灯时间, 使该公交车可在本周期内通过交叉口。最大绿灯时间必须小于本相位的内置最大绿灯时间, 若大于, 则设本相位的内置最大绿灯时间为该周期本相位的最大绿灯时间。
4 结论
随着城市化进程的不断深入, 我国汽车保有量逐年增加, 城市交通问题越来越严重。而城市公共交通在城市交通受益人数最多, 同大多数城市居民生产、生活等活动密切相关, 在城市交通中占有重要的地位与作用。因此, 大力发展城市公共交通, 是解决城市交通问题、提高城市生活质量、促进城市可持续发展的最有效途径之一, 本文针对于常规公交系统的信号优先问题, 在前人研究的基础上进一步深化了单相常规公交信号优先和多相常规公交信号优先的研究, 使信号优先的控制模型的准确性更高, 研究成果将为城市公交优先控制提供新思路。
参考文献
[1]杨晓光, 林瑜, 杭明升.信号控制交叉口公共汽车优先信号确定方法研究.中国公路学报, 2001;14增刊:101—105
[2]高昆, 张海.城市交通中的公交优先策略.交通运输系统工程与信息, 2006;6 (2) :23—26
[3]阴炳成, 杨晓光.交叉口单点公共汽车交通优先控制方法研究.公路交通科技, 2005;22 (12) :124—126
[4]马万经, 杨晓光.单点公交优先感应控制策略效益分析与仿真验证.系统仿真学报, 2008;20 (12) :3309—3313
[5]张宇.基于延误的单个交叉口公交优先信号控制方法研究.长春:吉林大学交通学院, 2008