王 飛，袁 濤，王 蒙

(安徽機(jī)電職業(yè)技術(shù)學(xué)院，安徽 蕪湖 241002)

圖(Graph)是一種非線性結(jié)構(gòu)，由頂點(diǎn)和邊組成，頂點(diǎn)表示圖中的數(shù)據(jù)元素，邊表示數(shù)據(jù)元素之間的關(guān)系.圖可定義為G=(V，E),其中V是頂點(diǎn)的非空有窮集合，E是用頂點(diǎn)對(duì)表示邊的有窮集合；按照圖中表示邊的頂點(diǎn)對(duì)是否有序可以把圖分為有向圖和無向圖；具有n個(gè)頂點(diǎn)的無向圖，其邊的數(shù)量如果達(dá)到了n*(n-1)/2,或是具有n個(gè)頂點(diǎn)有向圖，邊的數(shù)量達(dá)到了n*(n-1)，則稱該圖為完全圖；在一個(gè)無向圖中任意兩個(gè)頂點(diǎn)Vi和Vj都有路徑相通，則該圖稱為連通圖，在一個(gè)有向圖中任意兩個(gè)頂點(diǎn)Vi和Vj都有路徑相通，則該圖稱為強(qiáng)連通圖.圖的每條邊或弧上若有一個(gè)具有一定意義的數(shù)值，該數(shù)值稱為權(quán)，邊或弧上帶權(quán)的連通圖稱為網(wǎng).圖的存儲(chǔ)方式有兩種:鄰接矩陣和鄰接表.

在圖中經(jīng)典的算法有求最小生成樹的普里姆算法和克魯斯卡爾算法；在帶權(quán)圖中求最短路徑算法有經(jīng)典的Dijkstra算法和Floyd算法等.

圖論算法在計(jì)算機(jī)科學(xué)中扮演著很重要的角色，它提供了對(duì)很多問題都有效的一種簡單而系統(tǒng)的建模方式.很多問題都可以轉(zhuǎn)化為圖論問題，然后用圖論的基本算法加以解決.在研究各類算法并根據(jù)所針對(duì)的具體問題對(duì)其進(jìn)行改進(jìn)的工作中，有一個(gè)前提工作就是要根據(jù)不同要求來進(jìn)行構(gòu)建各類圖或者網(wǎng)，在算法的一次實(shí)現(xiàn)中，可以通過構(gòu)造靜態(tài)圖或者靜態(tài)網(wǎng)，但是在對(duì)算法的研究中，需要多次構(gòu)造不同的圖并在該圖上驗(yàn)證算法，這個(gè)時(shí)候就需要?jiǎng)討B(tài)隨機(jī)地生成多個(gè)符合要求的圖或網(wǎng)供算法的實(shí)現(xiàn)和驗(yàn)證使用.

1 聯(lián)通網(wǎng)的隨機(jī)生思路與最短路徑算法的簡介

1.1 聯(lián)通網(wǎng)的隨機(jī)生思路

在圖論中的一些重要的方法如圖的遍歷算法、最短路徑算法、最小生成樹算法等都是建立在有圖或者是網(wǎng)的基礎(chǔ)上的.而圖的產(chǎn)生一般是有兩種辦法實(shí)現(xiàn)，一種是提前設(shè)定參數(shù)來生成圖，這種方法的優(yōu)點(diǎn)在于參數(shù)信息可控，可以預(yù)先準(zhǔn)備大量的數(shù)據(jù)來產(chǎn)生豐富的圖；缺點(diǎn)也是明顯的，就是在準(zhǔn)備參數(shù)過程中比較費(fèi)時(shí)費(fèi)力，而且產(chǎn)生的圖的參數(shù)具有一定局限性，不利于對(duì)系統(tǒng)的綜合測試及驗(yàn)證.另一種方法就是隨機(jī)產(chǎn)生法，具體來說就是隨機(jī)產(chǎn)生圖的頂點(diǎn)個(gè)數(shù)、圖的邊的個(gè)數(shù)以及邊的權(quán)值.這種圖的生成法的優(yōu)點(diǎn)和缺點(diǎn)也是顯而易見的：優(yōu)點(diǎn)是產(chǎn)生圖的效率比較高，可以隨機(jī)快速地產(chǎn)生參數(shù)、類型豐富的圖或者網(wǎng)；效率比較高，也有利于對(duì)系統(tǒng)的綜合測試及驗(yàn)證；缺點(diǎn)也較為明顯：由于是隨機(jī)產(chǎn)生圖的參數(shù)來構(gòu)建圖，較容易產(chǎn)生一些不符合實(shí)際需要或邏輯錯(cuò)誤的圖，這對(duì)于在圖上研究相關(guān)問題是有著重大不利影響.

鑒于以上分析，本文提出的方法結(jié)合兩種方法的優(yōu)缺點(diǎn)，將兩種方法的優(yōu)點(diǎn)結(jié)合起來.總體來說,還是通過隨機(jī)生成的方法來生成所需要的圖或者是網(wǎng)，對(duì)于可能產(chǎn)生錯(cuò)誤邏輯的圖或者網(wǎng)，我們采用的方法是在綜合考慮現(xiàn)實(shí)研究問題對(duì)應(yīng)的圖或者是網(wǎng)參數(shù)的合理范圍，對(duì)隨機(jī)生成圖的參數(shù)范圍進(jìn)行合理限定，這樣既能快速高效地產(chǎn)生圖或網(wǎng)，又能避免產(chǎn)生參數(shù)不合理圖或網(wǎng)對(duì)所研究的問題產(chǎn)生負(fù)面影響.

1.2 最短路徑的基本概念及算法分析

作為圖論的經(jīng)典問題，最短路徑一直是一個(gè)在工程規(guī)劃、地理信息系統(tǒng)、軍事等領(lǐng)域應(yīng)用十分廣泛的問題，對(duì)該問題的研究有著重要的理論和應(yīng)用價(jià)值.最短路徑度量標(biāo)準(zhǔn)不僅是空間距離上的，還可以為時(shí)間、花費(fèi)代價(jià)等其他的度量標(biāo)準(zhǔn)[1].根據(jù)度量標(biāo)準(zhǔn)的不同，最短路徑問題可以轉(zhuǎn)換為耗時(shí)最短、花費(fèi)最低等問題.網(wǎng)絡(luò)分析中最基本、關(guān)鍵的問題是最短路徑問題[3]；無論是距離最短、耗時(shí)最短還是花費(fèi)最低，其核心都是最短路徑算法.隨著圖論的相關(guān)算法不斷更新發(fā)展，解決最短路徑問題算法針對(duì)不同的圖網(wǎng)特征、應(yīng)用需求等方面不斷推陳出新，在時(shí)空復(fù)雜度、易于實(shí)現(xiàn)等方面特色各異[2].

簡單來說，從圖中的一個(gè)頂點(diǎn)到另一頂點(diǎn)如果存在相通的路徑，找到一條路徑使得沿此路徑上所有邊的權(quán)值最小的問題就是最短路徑問題.目前理論上最完善、得到廣泛的普及和應(yīng)用的最短路徑算法是采用貪心的啟發(fā)策略的Dijkstra算法[4，5].最短路徑算法有標(biāo)號(hào)算法和代數(shù)算法兩大類，Dijkstra算法屬于標(biāo)號(hào)算法的一種，標(biāo)號(hào)算法的代表除Dijkstra算法外還有Floyd算法[6，7].Dijkstra算法性能穩(wěn)定，較能適應(yīng)網(wǎng)絡(luò)拓?fù)渥兓?，主要針?duì)研究單一起點(diǎn)的最短路徑問題，易實(shí)現(xiàn)且通用性強(qiáng)[3,8]；該算法時(shí)間復(fù)雜度為O(n2)，適用于網(wǎng)絡(luò)節(jié)點(diǎn)較少的情況下[3].Floyd算法主要研究網(wǎng)絡(luò)中兩點(diǎn)間的最短路徑，時(shí)間復(fù)雜度為O(n3).

本文研究的背景問題是為公路網(wǎng)中行駛的電動(dòng)汽車尋找最佳充電點(diǎn)設(shè)計(jì)算法，這個(gè)問題可以從兩個(gè)方面考慮，一方面從獨(dú)立行使的電動(dòng)汽車自身來說可以理解為這是單一起點(diǎn)的最短路徑設(shè)計(jì)算法，當(dāng)前電動(dòng)汽車所在位置就是起點(diǎn)；另一方面，考慮到車聯(lián)網(wǎng)技術(shù)的長足發(fā)展，很多行駛中的電動(dòng)汽車的服務(wù)請求都可以通過網(wǎng)絡(luò)服務(wù)中心得到解決，而網(wǎng)絡(luò)服務(wù)中心面臨的很多問題是要同時(shí)解決很多網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)來的類似請求.公路網(wǎng)中行駛的電動(dòng)汽車尋找最佳充電點(diǎn)的問題，可能在同一時(shí)刻在某個(gè)區(qū)域內(nèi)多輛汽車都需要找到充電節(jié)點(diǎn)進(jìn)行充電，可以考慮在網(wǎng)絡(luò)服務(wù)中心執(zhí)行Floyd算法同時(shí)求出區(qū)域中每個(gè)節(jié)點(diǎn)的最佳充電服務(wù)點(diǎn)；當(dāng)然針對(duì)具體問題還需要對(duì)Floyd算法進(jìn)行改進(jìn)以更加高效地解決問題，這樣做比單一起點(diǎn)的最短路徑算法要更加全面高效.

1.3 Floyd算法的思想

設(shè)一有向網(wǎng)絡(luò)G=(V,E)，求V集合中各點(diǎn)到其余各頂點(diǎn)的最短距離，通過Floyd算法來解決這個(gè)問題需要引入兩個(gè)矩陣S、P，S中的元素s[i][j]表示頂點(diǎn)i到頂點(diǎn)j的距離權(quán)值.矩陣P中的元素p[i][j]，表示頂點(diǎn)i到頂點(diǎn)j經(jīng)過了p[i][j]記錄的值所表示的頂點(diǎn).假設(shè)圖G中頂點(diǎn)個(gè)數(shù)為N，則需要對(duì)矩陣S和矩陣P進(jìn)行N次更新.初始時(shí)，矩陣S中頂點(diǎn)s[i][j]的距離為頂點(diǎn)i到頂點(diǎn)j的權(quán)值；如果i和j不相鄰，則s[i][j]=∞，矩陣P的值為頂點(diǎn)b[i][j]的j的值.

具體算法描述為(算法1：Floyd算法)：

Step1：初始化矩陣S和P；使得S中的元素s[i][j]表示頂點(diǎn)i到頂點(diǎn)j的距離權(quán)值，即s[i][j]=wij.矩陣P中的元素p[i][j]，表示頂點(diǎn)i到頂點(diǎn)j經(jīng)過了p[i][j]記錄的值所表示的頂點(diǎn)，初始時(shí)p[i][j]=j;

Step2：For k:=1 to N

For i:=1 to N

For j:=1 to N

If s[i][j]>s[i][k]+s[k][j]

Then {s[i][j]:=s[i][k]+s[k][j];p[i][j]=p[i][k];}

Step3：算法結(jié)束，矩陣S存儲(chǔ)所有點(diǎn)對(duì)之間的最短路徑長度，矩陣P存儲(chǔ)所有點(diǎn)對(duì)的最短路徑信息.

2 改進(jìn)Floyd算法在隨機(jī)生成網(wǎng)上的實(shí)現(xiàn)

2.1 問題背景分析

在當(dāng)前各大城市中充電汽車日益普及的情況下，行駛中電動(dòng)汽車在電量不足時(shí)尋找合適充電樁進(jìn)行充電的問題是本文所研究問題的大背景.該問題其實(shí)就是最短路徑問題，利用Floyd算法找到路網(wǎng)中各點(diǎn)之間的最短路徑，考慮到路網(wǎng)中并不是每一個(gè)點(diǎn)都是充電節(jié)點(diǎn)，而充電點(diǎn)中每個(gè)充點(diǎn)電可能存在其他電動(dòng)汽車正在占用、排隊(duì)等待的情況，解決這樣的問題需要對(duì)Floyd算法進(jìn)行改進(jìn)形成符合解決問題所需要的算法，改進(jìn)的思想就是把充電點(diǎn)中等待充電的汽車數(shù)量與當(dāng)前行駛速度、每輛汽車充電所需時(shí)間等相關(guān)參數(shù)利用公式1折算成其余各點(diǎn)到達(dá)該點(diǎn)距離的一部分，具體如下：

設(shè)V為當(dāng)前車速，T為每輛車充電所需時(shí)間，當(dāng)前有向網(wǎng)中每個(gè)點(diǎn)Vx，如果Vx為充電節(jié)點(diǎn)，該節(jié)點(diǎn)的numcars分量為等待充電電動(dòng)汽車數(shù)量，distance分量為該節(jié)點(diǎn)由于有排隊(duì)等待充電的電動(dòng)汽車所造成的時(shí)間開銷所折算的距離；如果Vx為非充電節(jié)點(diǎn)，則該節(jié)點(diǎn)的numcars分量設(shè)為-1，distance分量設(shè)為0；

具體算法描述為(算法2：充電節(jié)點(diǎn)等待時(shí)間-距離折算)：

If(Vx是充電節(jié)點(diǎn))

Vx.distance=V*T*numcars；

else

{ Vx.distance=0；numcars=-1；}

通過算法2將當(dāng)前有向網(wǎng)中每個(gè)充電點(diǎn)Vx由于等待充電排隊(duì)汽車所造成的開銷distance計(jì)算出來，將速度、等待充電車輛數(shù)量等非距離因素轉(zhuǎn)換成距離來統(tǒng)一考慮.Floyd算法在解決有向網(wǎng)中各點(diǎn)之間最短距離問題上是最具優(yōu)勢的，剩下的問題可由改進(jìn)的Floyd算法來解決.

具體算法描述為：(算法3：改進(jìn)的Floyd算法)

Step1：初始化矩陣S和P；使得S中的元素s[i][j]表示頂點(diǎn)i到頂點(diǎn)j的距離權(quán)值，即s[i][j]=wij.矩陣P中的元素p[i][j]，表示頂點(diǎn)i到頂點(diǎn)j經(jīng)過了p[i][j]記錄的值所表示的頂點(diǎn)，初始時(shí)p[i][j]=j;

Step2：對(duì)于有向網(wǎng)中每個(gè)節(jié)點(diǎn)Vx：

If(Vx是充電節(jié)點(diǎn))

Vx.distance=V*T*numcars；

else

{ Vx.distance=0；numcars=-1；}

Step3：For k:=1 to N

For i:=1 to N

For j:=1 to N

If s[i][j]>s[i][k]+s[k][j]

Then {s[i][j]:=s[i][k]+s[k][j];p[i][j]=p[i][k];}

Step4：s[i][j]=s[i][j]+Vj.distance

Step5：算法結(jié)束，矩陣S存儲(chǔ)所有點(diǎn)對(duì)之間的最短路徑長度與等待代價(jià)之和，矩陣P存儲(chǔ)所有點(diǎn)對(duì)的最短路徑信息.

2.2 隨機(jī)構(gòu)建有向聯(lián)通網(wǎng)

改進(jìn)Floyd算法在電動(dòng)汽車充電中得以實(shí)現(xiàn)的基礎(chǔ)是符合要求的有向網(wǎng)，而有向網(wǎng)的構(gòu)造有固定生成法和隨機(jī)產(chǎn)生法兩種，固定生成法主要通過程序讀入文件或輸入固定參數(shù)的方法來生成圖，生成的圖用鄰接矩陣來存儲(chǔ)，這種方法產(chǎn)生的圖具有一定的局限性，不利于對(duì)系統(tǒng)的綜合測試及驗(yàn)證；隨機(jī)生成網(wǎng)的方法就是隨機(jī)產(chǎn)生圖的頂點(diǎn)個(gè)數(shù)、圖的邊的個(gè)數(shù)以及邊的權(quán)值.這種圖的生成法可以隨機(jī)快速地產(chǎn)生類型豐富的圖或者網(wǎng)，效率比高，有利于對(duì)系統(tǒng)的綜合測試及驗(yàn)證.

將兩種方法的優(yōu)點(diǎn)結(jié)合起來.主要通過隨機(jī)生成的方法來生成所需要的圖或網(wǎng)，同時(shí)綜合考慮現(xiàn)實(shí)研究問題對(duì)應(yīng)的圖或者是網(wǎng)參數(shù)的合理范圍，對(duì)隨機(jī)生成圖的參數(shù)范圍進(jìn)行合理限定，高效地產(chǎn)生出所需的有向網(wǎng).在市區(qū)行駛中的電動(dòng)汽車尋找合適充電點(diǎn)進(jìn)行充電，可以考慮以當(dāng)前點(diǎn)為源點(diǎn)，產(chǎn)生10～20個(gè)公路節(jié)點(diǎn)，在這10～20個(gè)公路節(jié)點(diǎn)里有3～8個(gè)充電點(diǎn)，在預(yù)先設(shè)定隨機(jī)數(shù)范圍來實(shí)現(xiàn)產(chǎn)生公路節(jié)點(diǎn)和充電節(jié)點(diǎn)，然后再設(shè)定各節(jié)點(diǎn)之間的距離.根據(jù)市區(qū)內(nèi)的特點(diǎn)，可以將節(jié)點(diǎn)或充點(diǎn)電之間的距離設(shè)為5～15千米范圍，也可以預(yù)先設(shè)定隨機(jī)數(shù)范圍的方式來確定，按照以上提出的思路來構(gòu)建有向網(wǎng)絡(luò).在現(xiàn)實(shí)生活中,公路網(wǎng)一般是聯(lián)通的，為了解決隨機(jī)產(chǎn)生公路網(wǎng)可能存在不連通的狀況，本文采用了一個(gè)限定辦法：在隨機(jī)產(chǎn)生了公路節(jié)點(diǎn)的數(shù)量m后，限定隨機(jī)產(chǎn)生的路徑數(shù)量不得小于m，且在構(gòu)建前m條路徑時(shí)先把m個(gè)節(jié)點(diǎn)串成一個(gè)閉環(huán)，在第m及以后條邊的起點(diǎn)和終點(diǎn)采用隨機(jī)選取的方式來確定，這樣可以保證產(chǎn)生聯(lián)通有向網(wǎng).至于是否需要構(gòu)建強(qiáng)聯(lián)通網(wǎng)，考慮到城市道路中存在單行道的特點(diǎn)，我們在構(gòu)建公路網(wǎng)絡(luò)時(shí)不按照強(qiáng)聯(lián)通網(wǎng)的特點(diǎn)來構(gòu)建.隨機(jī)有向網(wǎng)構(gòu)建流程如圖1所示.

圖1 隨機(jī)有向網(wǎng)構(gòu)建流程

2.3 改進(jìn)Floyd算法在隨機(jī)有向網(wǎng)上的實(shí)現(xiàn)

根據(jù)上文分析，把需要充電的電動(dòng)汽車所處位置環(huán)境抽象為有向連通網(wǎng)G=(V,E)，先隨機(jī)生成連通網(wǎng)后，按照預(yù)設(shè)條件范圍隨機(jī)生成平均充電時(shí)間T和當(dāng)前車速CV，設(shè)頂點(diǎn)集V中一共有M個(gè)節(jié)點(diǎn)，隨機(jī)生成N個(gè)充電節(jié)點(diǎn)，N的范圍是M/4<=N<=M/3，并對(duì)每個(gè)充電節(jié)點(diǎn)隨機(jī)設(shè)置0～3輛等待充電汽車的數(shù)量.接下來，調(diào)用前文提出的算法2對(duì)于有向連通網(wǎng)中的每個(gè)節(jié)點(diǎn)Vx的distance分量進(jìn)行計(jì)算，作為有向網(wǎng)中其余點(diǎn)到達(dá)該點(diǎn)距離的一部分.引入兩個(gè)矩陣S、P，S中的元素s[i][j]表示頂點(diǎn)i到頂點(diǎn)j的距離權(quán)值.矩陣P中的元素p[i][j]，表示頂點(diǎn)i到頂點(diǎn)j經(jīng)過了p[i][j]記錄的值所表示的頂點(diǎn).再按照前文提出的算法3求出該有向連通網(wǎng)各點(diǎn)之間的最小距離(含有distance因素的綜合距離)，算法具體步驟如下：

Step1：初始化矩陣S和P；使得S中的元素s[i][j]表示頂點(diǎn)i到頂點(diǎn)j的距離權(quán)值，即s[i][j]=wij.矩陣P中的元素p[i][j]，表示頂點(diǎn)i到頂點(diǎn)j經(jīng)過了p[i][j]記錄的值所表示的頂點(diǎn)，初始時(shí)p[i][j]=j;隨機(jī)生成N個(gè)充電節(jié)點(diǎn)，N的范圍是M/4<=N<=M/3，并對(duì)每個(gè)充電節(jié)點(diǎn)隨機(jī)設(shè)置0～3輛等待充電汽車的數(shù)量.

Step2：對(duì)于有向網(wǎng)中每個(gè)節(jié)點(diǎn)Vj，調(diào)用算法2計(jì)算設(shè)置Vj.distance

Step3：For k:=1 to N

For i:=1 to N

For j:=1 to N

If s[i][j]>s[i][k]+s[k][j]

Then {s[i][j]:=s[i][k]+s[k][j];p[i][j]=p[i][k];}

Step4：s[i][j]=s[i][j]+Vj.distance

Step5：對(duì)于任一非充電節(jié)點(diǎn)x，找到一個(gè)充電節(jié)點(diǎn)y使得s[x][y]=Min{s[i][j]|x==i&&j為充電節(jié)點(diǎn)}

2.4 系統(tǒng)測試與分析

本研究算法(包括隨機(jī)生成有向網(wǎng))采用C語言模擬實(shí)現(xiàn)，按照圖1所示流程先生成一個(gè)有向聯(lián)通網(wǎng)，在指定范圍內(nèi)隨機(jī)預(yù)設(shè)當(dāng)前車速及各充電樁等待充電汽車的數(shù)量，最后按照前文所提的改進(jìn)Floyd算法找到合適的充點(diǎn)電并將路徑返回.整個(gè)系統(tǒng)流程圖如圖2所示.

圖2 系統(tǒng)流程圖

本算法中的隨機(jī)生成有向網(wǎng)部分，生成節(jié)點(diǎn)的部分算法復(fù)雜度為O(n)，生成有向邊部分，考慮一個(gè)有向網(wǎng)為強(qiáng)聯(lián)通網(wǎng)的情況下邊的數(shù)量為n*(n-1)，而實(shí)際上公路存在單行道的情況，公路網(wǎng)不可能達(dá)到n*(n-1)條邊的規(guī)模，所以隨機(jī)生成網(wǎng)操作的時(shí)間復(fù)雜度為O(n2)；接下來調(diào)用前文提出的改進(jìn)Floyd算法(算法3)結(jié)合每個(gè)充電點(diǎn)等待充電汽車數(shù)量等綜合因素計(jì)算出每個(gè)點(diǎn)對(duì)之間的最短距離，最后，根據(jù)提出的非充電節(jié)點(diǎn)位置，計(jì)算出最佳充電點(diǎn)的位置并給出相應(yīng)路徑.Floyd算法的改進(jìn)的核心思想是先計(jì)算出有向網(wǎng)中所有點(diǎn)對(duì)的最短距離，然后再結(jié)合每個(gè)充電點(diǎn)等待充電汽車數(shù)量,根據(jù)算法2更新每個(gè)點(diǎn)的distance分量，該分量將作為其余頂點(diǎn)達(dá)該點(diǎn)的最短距離的一部分，這樣得出與充點(diǎn)電相關(guān)的各點(diǎn)對(duì)的最短距離就結(jié)合了排隊(duì)等待的其他因素，使得選擇方案更加科學(xué)、有效.

傳統(tǒng)的Floyd算法的時(shí)間復(fù)雜度為O(n3)，對(duì)改進(jìn)部分主要是計(jì)算每個(gè)點(diǎn)的distance分量和計(jì)算出每個(gè)點(diǎn)對(duì)之間的最短距離后結(jié)合目標(biāo)點(diǎn)的distance分量確定指定起點(diǎn)的最佳充電位置及相應(yīng)路徑，這兩改進(jìn)部分的時(shí)間復(fù)雜度都是O(n).綜合以上，改進(jìn)的Floyd算法的時(shí)間復(fù)雜度還是O(n3)，相對(duì)來說時(shí)間復(fù)雜度較高.為電動(dòng)汽車尋找最佳充電點(diǎn)和路徑而設(shè)計(jì)的算法，考慮到電動(dòng)汽車?yán)m(xù)航能力，設(shè)計(jì)的路網(wǎng)節(jié)點(diǎn)一般在20個(gè)以內(nèi)，充電節(jié)點(diǎn)一般在路網(wǎng)節(jié)點(diǎn)的1/4～1/3之間，這樣的路網(wǎng)規(guī)模運(yùn)行本設(shè)計(jì)的Floyd算法是完全可行的.

系統(tǒng)分組進(jìn)行測試，每組在其對(duì)應(yīng)參數(shù)取值范圍內(nèi)測10次，如表1所示.

表1 系統(tǒng)運(yùn)行表

通過表1，我們可以發(fā)現(xiàn)以下幾點(diǎn)特征：

1.本文提出的算法將路網(wǎng)中的充電點(diǎn)存在的排隊(duì)等待因素綜合考慮到最短路徑算法中，將Floyd算法改進(jìn)并實(shí)現(xiàn)，經(jīng)過系統(tǒng)測試，每組實(shí)驗(yàn)均能準(zhǔn)確找到充電目標(biāo)并輸出正確的行駛路徑，說明本文提供的算法正確并且可以解決以電動(dòng)汽車尋找充電點(diǎn)為背景的問題.

2.一共6組實(shí)驗(yàn)，隨著圖的復(fù)雜度增加，改進(jìn)Floyd算法運(yùn)行時(shí)間也大幅提升，這與算法時(shí)間復(fù)雜度本身特性相一致.

3.Floyd算法時(shí)間復(fù)雜度比較高，但是經(jīng)過分析是可以適用于本研究的背景課題，由理論分析與實(shí)驗(yàn)對(duì)比，對(duì)Floyd算法的改進(jìn)沒有提高算法的時(shí)間復(fù)雜度，且增加的時(shí)間開銷(查找充電點(diǎn)運(yùn)行時(shí)間)相對(duì)于整個(gè)算法運(yùn)行時(shí)間可忽略不計(jì).

綜上分析，該算法運(yùn)行達(dá)到了預(yù)期的結(jié)果.

3 結(jié)束語

本文通過研究相關(guān)經(jīng)典的Floyd、Dijkstra等最短路徑及其改進(jìn)算法，提出一種實(shí)現(xiàn)隨機(jī)生成有向聯(lián)通網(wǎng)的方法.改進(jìn)的Floyd算法經(jīng)過測試，獲得了預(yù)期的結(jié)果；該方法的應(yīng)用提高了對(duì)圖、網(wǎng)絡(luò)中最短路徑等相關(guān)算法研究的效率，具有一定的實(shí)用價(jià)值.

本文提出的隨機(jī)生成連通網(wǎng)的方法雖然根據(jù)現(xiàn)實(shí)情況對(duì)相關(guān)參數(shù)進(jìn)行了范圍限定，力求生成與現(xiàn)實(shí)情況貼近的有向聯(lián)通網(wǎng)，但考慮到隨機(jī)生成時(shí)，有部分參數(shù)可能與實(shí)際情況有一定差異，在一定程度上會(huì)造成實(shí)驗(yàn)數(shù)據(jù)的偏差.在未來的研究中應(yīng)考慮按照實(shí)際路網(wǎng)情況進(jìn)行構(gòu)圖，并將參數(shù)信息存儲(chǔ)到文件或是數(shù)據(jù)庫中，不斷充實(shí)、完善文件及數(shù)據(jù)庫信息，使實(shí)驗(yàn)數(shù)據(jù)完全符合實(shí)際情況，當(dāng)文件或數(shù)據(jù)庫信息非常豐富時(shí)，可以通過隨機(jī)抽取的方式來構(gòu)建路網(wǎng)圖，為相關(guān)算法提供更為準(zhǔn)確的測試數(shù)據(jù)，進(jìn)而獲取更為準(zhǔn)確的結(jié)論.