多岔路口交通信號燈控制系統的設計與實現

摘要:多岔路口交通信號燈控制系統的設置問題可轉化為對圖的頂點染色的問題，此種方法簡單可行，問題的探究對以后相關問題的探討有一定的借鑒意義。

關鍵詞:圖論;四色原理;著色

中圖分類號: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] http://www.bjkp.gov.cn/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.