交通網(wǎng)絡(luò)中的一些問題及算法

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

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

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

1 引言

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

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

2 模型及算法

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

現(xiàn)圖示如下:

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

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

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

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

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

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

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

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

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

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

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

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

3 算例

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

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

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

→→→→→→

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

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

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

→→→→→

或→→→→→

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

或→→→→→→→

或→→→→→→

或→→→→→→→

4 結(jié)束語

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