多岔路通信号灯控制系统的设计与实现

摘要:多岔路通信号灯控制系统的设置问题可转化为对图的顶点染色的问题,此种方法简单可行,问题的探究对以后相关问题的探讨有一定的借鉴意义。

关键词:图论;四色原理;着色

中图分类号:TB533文献标识码:A 文章编号:1009-3044(2010)01-208-02

Design and Implementation of the Traffic Signal Control System in the Multi-Fork Road

LIU Pan, XU Zhi-pan, ZHANG Xiao-ming

(Collage of Computer and Information Technology, Henan Normal University, Xinxiang 453007, China)

Abstract: Based on the topological transformation to graph coloring, the design and implementation of the traffic signal control system in the multi-fork road is changed into the quadratic equation, the Four-color Theorem is applied to the equation. This methord is simple and feasible. The research about the problem can also be used forfor the further reacher.

Key words: graph theory; four-color theorem; vertex coloring

图是一种常见的数据结构[1]。图论问题中的四色原理猜想最早是在1852年由毕业于伦敦大学的Francis Guthrie发现提出的[2],运用四色原理着色是常见的将问题化繁为简的方法。

通常,十字路口只需设置红黄绿三种颜色的交通信号灯便可保持正常的交通秩序,而在车流量较大的多岔路口则需设多种颜色的交通灯才能既使车辆相互之间不碰撞,又能达到车辆的最大流通。

汪学典将十字路通信号灯控制系统看作典型的米莱型时序逻辑电路,用时序PLA实现了该系统[4];雷新军与王耀青采用了以8051为内核的单片机芯片作为核心控制器,以嵌入式操作系统RTX51为软件开发平台,通过控制城市路口十字路口的交通信号灯来指挥交通的方法[5];耿文波和黄伟基于EWB实现交通信号灯控制系统的设计与仿真[6];但是他们并没有提出具体的交通信号灯设置问题的解决方案。本文将讨论把四色原理运用到三岔路通信号灯的设置问题上,运用Welch Powell法对图进行着色,即可算出信号灯的所有颜色。提出自己的算法,并将此算法推广至四岔路口五岔路口至多岔路通信号灯的设置问题上,最后讨论了此种算法的优点与不足。

1 图论的基础理论

定义1.1 图G的正常着色(简称着色)是指对它的每一个结点指定一种颜色,使得没有两个邻接的结点有同一种颜色。如果图G在着色时用了n种颜色,称为G为n-色的。

定义1.2 对于图G着色时需要的最少颜色数称为G的着色数,记作x(G)。

韦尔奇・鲍威尔法(Welch Powell)着色法:

1) 将图中的顶点按照度数的递减次序进行排列。(这些排列可能不是唯一的,因为有些点又相同的度数。这时进行实地考察,按车流量排序。)

2) 用第一种颜色对第一个点着色,并且按排列次序,对与前面着色点不邻接的每一个点着相同的颜色。

3) 用第二种颜色对尚未着色的点重复b),用第三种颜色继续这种做法,直到所有的点全部着上颜色为止。

定义1.3 对于n个结点的完全图Kn,有x(Kn)=n。

定义1.4 四色原理:任一平面G最多是4-色的[2]。G=(V,E),

定义1.5 图G的着色2当且仅当G是一个非空二分图。

2 由上导出的交通信号灯的设置

2.1 三岔路口

1) 图1是一个三岔路口,在路的中间有L1,L2,...,L6六个交通信号灯,图中箭头方向表示每条路上的车流方向,交叉和箭头并行表明两条道路不能同时通车,否则会发生交通事故。当且仅当某个方向上的交通灯变为绿色时,此方向上的车辆才能通行。问怎样变换交通灯的颜色才能使此路口的车都能安全通过又能达到路口的最大流通。

2) 解决方法:在“图”中,用一个顶点表示一条通路,两条通路之间相互矛盾的关系用两个顶点之间的连线表示,即若两条通路之间不能同时通车,则两个顶点之间连一条线。因此设置交通灯的问题就转化为对图中顶点的着色问题,要求对图上的每个顶点染一种颜色,并且要求有线相连的两个顶点不能具有相同染色,而总的颜色种类应尽可能地少。由定义1.4中四色原理可知,所使用的最大颜色数为4。

按韦尔奇・鲍威尔法(Welch Powell)法对图中顶点着色。由于对顶点的着色顺序不唯一,所得的着色结果也不唯一,图2所示仅为其中的一种着色结果,当结点的度数相同时,按结点顺序由小到大进行着色。

1号灯亮时,只有L1、L2、L6三个方向上的车能通过;

2号灯亮时,只有L4、L5两个方向上的车能通过;

3号灯亮时,只有L3方向上的车能通过。

2.2 四岔路口

1) 图3是一个四岔路口,在路的中间有L1,L2,...,L9九个交通信号灯,图中箭头方向表示每条路上的车流方向,交叉和箭头并行表明两条道路不能同时通车,否则会发生交通事故。当且仅当某个方向上的交通灯变为绿色时,此方向上的车辆才能通行。问怎样变换交通灯的颜色才能使此路口的车都能安全通过又能达到路口的最大流通。

2) 解决方法:

分析方法与三岔路口的情况相同,所得的着色结果如图4所示。

1号灯亮时,只有L1、L2、L3三个方向上的车能同时通过;

2号灯亮时,只有L4、L5、L9三个方向的车能同时通过;

3号灯亮时,只有L6、L7两个方向上的灯能同时通过;

4号灯亮时,只有L8方向上的车能通过。

2.3 五岔路口

1) 图5是一个三岔路口,在路的中间有L1,L2,...,L10十个交通信号灯,图中箭头方向表示每条路上的车流方向,交叉和箭头并行表明两条道路不能同时通车,否则会发生交通事故。当且仅当某个方向上的交通灯变为绿色时,此方向上的车辆才能通行。问怎样变换交通灯的颜色才能使此路口的车都能安全通过又能达到路口的最大流通。

2) 解决方法:

分析方法与三岔路口的情况相同,所得的着色结果如图6所示。

1号灯亮时,只有L5、L9、L10三个方向上的车能同时通过;

2号灯亮时,只有L3、L4两个方向的车能同时通过;

3号灯亮时,只有L1、L2两个方向上的灯能同时通过;

4号灯亮时,只有L6、L7、L8三个方向上的车能同时通过。

3 推广到多岔路通信号灯的设置

当碰到多岔路口情况时,按如下算法解决问题:

1) 画出此多岔路口的车流量抽象图;

2) 计算出每条路与其它路交叉的数与驶向同一个方向的路的总数;

3) 将每个方向设置成一个结点,把不能同时通车的两个结点间连线;

4) 按韦尔奇.鲍威尔法(Welch Powell)对图中的结点着色;

5) 着相同颜色的结点即能同时通车的道路。

用韦尔奇・鲍威尔法(Welch Powell)法对图着色,所用的最大着色数也为4,这与四色原理恰好吻合。

4 对此算法的评价

算法优点:1)此种算法创新性强; 2)算法简单,方法可行。

算法不足:1)人们对于颜色的敏感度不同,其中红、黄、绿三种最能引起人的注意力,很难再找到第四种颜色作为交通信号灯的颜色;2)大城市中路口多时,需要在每个路口都设置一个交通灯,这样会增加人们的等待时间。

5 结束语

将图论的着色问题用于交通信号灯的设置上,不仅为交通信号灯的设置提出了一种新的解决方案,同时也大大简化了设置的方法。该文以三岔路口为切入点,提出了新的交通信号灯设置算法,用同样的方法解决了四岔路口与五岔路口的信号灯设置问题,并推广到多岔路口问题上。此算法简单,理论性强,然而也有弊端。实际生活中,在城市规划问题上,一般避免出现多岔路口的情况,而通过增加立交桥、地铁的方法来缓解城市因车流量大而引起的交通拥堵情况。

参考文献:

[1] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2008.

[2] Gray Chartrand,Ping Zhang.Introduction to Graph Theory[M].美国:McGraw-Hill Companies,Inc.2005.

[3] /bjkpzc/kxcl/wk/qnkxjkpwk/gc/9324.shtml.

[4] 汪学典.十字路通信号灯控制系统[J].武汉化工学院学报,1996,18(3):47-50.

[5] 雷新军,王耀青.基于MCU和嵌入式操作系统的交通信号灯控制系统[J].河南科学,2009,27(6):714-717.

[6] 耿文波,黄伟.基于EWB的交通信号灯控制系统的设计与仿真[J].电脑知识与技术:学术交流,2007(8):821-823.