摘要本文針對一類交通網(wǎng)絡(luò)，利用最短路算法，建立了交通網(wǎng)絡(luò)中等待次數(shù)最少的通路算法。

關(guān)鍵詞交通網(wǎng)絡(luò)臨時標(biāo)號永久標(biāo)號

中圖分類號:O13文獻(xiàn)標(biāo)識碼:A

1 引言

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

本文對一類交通網(wǎng)絡(luò)，按照交通規(guī)則，提出了一個計(jì)算等待綠燈次數(shù)最少的通路算法，從一個方面解決了這個問題。

2 模型及算法

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

現(xiàn)圖示如下:

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

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

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

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

這里，我們規(guī)定，，經(jīng)到方向的等待次數(shù)標(biāo)在的右邊，如圖2，2表示從始點(diǎn)到共等待2次。

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

我們以表示的臨時標(biāo)號，以表示的永久標(biāo)號。

① 以出發(fā)點(diǎn)為終點(diǎn)虛擬一條邊，并賦予該出發(fā)點(diǎn)標(biāo)號(初始標(biāo)號，;

② 設(shè)是剛剛獲得標(biāo)號的點(diǎn)，考慮所有與相鄰且標(biāo)號為標(biāo)號的點(diǎn)，將的標(biāo)號修改為新的標(biāo)號(仍記為)min{}

③ 令{min{}，且與相鄰}€H⒔旰鷗奈旰?，若不唯逸x蛉扛奈旰牛?

④ 一旦終點(diǎn)得到標(biāo)號，則步驟停止(此時已求得出發(fā)點(diǎn)到終點(diǎn)等待次數(shù)最少的通路)，否則轉(zhuǎn)②。

由E.W.Dijkstra算法知此算法是一多項(xiàng)式算法。

3 算例

如圖3為一交通網(wǎng)絡(luò)，為出發(fā)點(diǎn)，為終點(diǎn)，怎樣尋求從到等待次數(shù)最少的通路。

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

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

→→→→→→

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

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

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

→→→→→

或→→→→→

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

或→→→→→→→

或→→→→→→

或→→→→→→→

4 結(jié)束語

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