交通網絡中的一些問題及算法

摘要本文針對一類交通網絡，利用最短路算法，建立了交通網絡中等待次數最少的通路算法。

關鍵詞交通網絡臨時標號永久標號

中圖分類號:O13文獻標識碼:A

1 引言

在各大中城市，隨著機動車輛的不斷增加，交通擁擠現象已成為廣大職工上下班深為關注的一個熱點。而“堵”又是最感頭痛的問題之一。

本文對一類交通網絡，按照交通規則，提出了一個計算等待綠燈次數最少的通路算法，從一個方面解決了這個問題。

2 模型及算法

設為一個無向圖，這里為的頂點集，為的邊集，對每一頂點，我們賦一個權(只取0，1兩個值)，其值依交通規則確定如下:

現圖示如下:

其中(c)可視為(b)的特例。

根據交通規則，上面三圖中除車輛遇紅燈往右拐不需等待外，其余各方向皆要等待一次。

另外，對一個交叉路口處，即一個頂點，若有五叉或五叉以上路口，可在該交叉路口處設立交橋，所以不必考慮。

我們的問題是，在賦權的無向圖上，尋找一條從(出發點)到(終點)的等待次數最少的通路，我們不妨從始點出發，逐步往前行，從始點尋找到下一個點等待次數最少的通路，逐步往下延伸，最終到達終點。當然，對于一個點，若有任意條以為終點的通路時，應取到等待次數最少的一條通路。如圖1，此時，應取等待次數為1的兩條通路中的任一條。

這里，我們規定，，經到方向的等待次數標在的右邊，如圖2，2表示從始點到共等待2次。

具體算法(不考慮時間):

我們以表示的臨時標號，以表示的永久標號。

① 以出發點為終點虛擬一條邊，并賦予該出發點標號(初始標號，;

② 設是剛剛獲得標號的點，考慮所有與相鄰且標號為標號的點，將的標號修改為新的標號(仍記為)min{}

③ 令{min{}，且與相鄰}€H⒔旰鷗奈旰牛舨晃ㄒ輝蛉扛奈旰牛?

④ 一旦終點得到標號，則步驟停止(此時已求得出發點到終點等待次數最少的通路)，否則轉②。

由E.W.Dijkstra算法知此算法是一多項式算法。

3 算例

如圖3為一交通網絡，為出發點，為終點，怎樣尋求從到等待次數最少的通路。

這里說明一下，具體操作時，給頂點標號標在邊上是為了便于觀察等待次數最少的通路是由哪個方向來的。若標號過程中，有兩條通路則任取其中一條。

由圖4作法可知，從到等待次數最少的通路為

→→→→→→

或→→→→→(如圖5所示)

若要求該通路必通過則怎樣尋找?

此時先以為起點，為終點，尋找一條等待次數最少的通路，由圖6可知，該通路為

→→→→→

或→→→→→

再以為起點，為終點來尋找一條等待次數最少的通路，此時，的標號為(2)，從而得到一條從到，中間必過點等待次數最少的通路(如圖7所示)即→→→→→→

或→→→→→→→

或→→→→→→

或→→→→→→→

4 結束語

本文對交通網絡的一類問題尋求到一種算法，這算法可推廣到必經某點或某個地方的交通網絡，有利于解決交通中車輛更好地通行，節約時間。當然，本文是在不考慮邊長的情況下而得到的一種算法，若同時還需考慮路途最短則屬于多目標問題，有待于進一步探討。