袁威威

摘要：對(duì)消防車的路徑進(jìn)行研究，確定最佳路線以提高滅火速度，縮短消防車抵達(dá)起火處時(shí)間，采用鄰接矩陣算法作為求解該問題的核心算法，尋找到時(shí)間最少和路徑最短的最優(yōu)路徑。

關(guān)鍵詞：鄰接矩陣；路徑優(yōu)化；有向圖

目前我國(guó)絕大多線路優(yōu)化，是憑借經(jīng)驗(yàn)，也有少部分開始借助于信息技術(shù)實(shí)現(xiàn)線路的優(yōu)化工作。本文求解最佳路徑的過程即尋找最短時(shí)間和最短路徑，我們將路徑抽象為有向圖，利用有向圖的鄰接矩陣。尋找到時(shí)間最少和路徑最短的最優(yōu)路徑。

一、應(yīng)用舉例

下面以某小區(qū)為例

假設(shè)將小區(qū)的十字路口設(shè)為v₁，v₂，v₃，v₄，v₅為有向圖的五個(gè)定點(diǎn)，小區(qū)的主干線為有向圖的邊，通過每條路的時(shí)間為有向圖邊的權(quán)。下面我們可以得到鄰接矩陣如下：

在小區(qū)中任意選取兩點(diǎn)v₃到v₂從加權(quán)值為根據(jù)圖二和距離矩陣D可知，當(dāng)v₅發(fā)生災(zāi)情時(shí)，消防站點(diǎn)v₃可到達(dá)v₅的路徑有：v₃-v₄-v₅，v₃-v₂-v₅，v₃-v₂-v₁-v₅，v₃-₂-v₄-v₅，-v₅，v₃-v₄-v₂-v₁-v₅等若干條路線，所以從v₂可到達(dá)v₄兩處之間的加權(quán)值最小的路線為v₃-v₄-v₅加權(quán)值為15，其他的兩兩任意兩頂點(diǎn)之間也可根據(jù)這樣的算法得出兩頂點(diǎn)之間的最短距離。

二、結(jié)論

采用鄰接矩陣算法能夠方便求出火災(zāi)救援所需的最短路徑，如突發(fā)交通事故或是車輛擁擠引起的交通堵塞。這需受密切注意掌握最新交通動(dòng)態(tài)信息，及時(shí)準(zhǔn)確地獲取動(dòng)態(tài)的路段耗時(shí)特征，并及時(shí)計(jì)算最佳行車路徑，做出準(zhǔn)確合理的應(yīng)急決策。如果路徑復(fù)雜本算法可以通過程序重復(fù)使用，只需輸入相應(yīng)的仞始數(shù)據(jù)即可，極大的減少了人力資源的浪費(fèi)。endprint