基于Floyd算法的大型停車(chē)場(chǎng)導(dǎo)航系統(tǒng)的設(shè)計(jì)

高振，陳順龍，王玨輝

（長(zhǎng)江大學(xué)工程技術(shù)學(xué)院，湖北荊州，434000）

0 引言

“停車(chē)難”加重交通擁堵。在北京中關(guān)村、南京新街口、廣州天河等繁華商圈，車(chē)位的捉襟見(jiàn)肘造成了交通的嚴(yán)重?fù)矶隆！巴＼?chē)難”引發(fā)公共糾紛。把Floyd算法應(yīng)用在大型停車(chē)導(dǎo)航系統(tǒng)的設(shè)計(jì)，在一定程度上，能夠解決“停車(chē)難”的問(wèn)題。

1 Floyd算法的原理分析

通過(guò)Floyd計(jì)算圖D=(V,E)中各個(gè)頂點(diǎn)的最短路徑時(shí)，需要引入一個(gè)矩陣S，矩陣S中的元素a[i][j]表示頂點(diǎn)i(第i個(gè)頂點(diǎn))到頂點(diǎn)j(第j個(gè)頂點(diǎn))的距離。

圖1 圖轉(zhuǎn)化矩陣

圖2 初始矩陣轉(zhuǎn)化最短路徑矩陣

假設(shè)圖D中頂點(diǎn)個(gè)數(shù)為N，則需要對(duì)矩陣S進(jìn)行N次更新。初始時(shí)，矩陣S中頂點(diǎn)a[i][j]的距離為頂點(diǎn)i到頂點(diǎn)j的權(quán)值；如果i和j不相鄰，則a[i][j]=∞。接下來(lái)開(kāi)始，對(duì)矩陣S進(jìn)行N次更新。第1次更新時(shí)，如果”a[i][j]的距離” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i與j之間經(jīng)過(guò)第1個(gè)頂點(diǎn)的距離”)，則更新a[i][j]為”a[i][0]+a[0][j]”。同理，第k次更新時(shí)，如果”a[i][j]的距離” > “a[i][k]+a[k][j]”，則更新 a[i][j]為”a[i][k]+a[k][j]”。更新N次之后，操作完成！

2 探求Floyd算法的動(dòng)態(tài)規(guī)劃本質(zhì)

從表面上粗看，F(xiàn)loyd算法是一個(gè)非常簡(jiǎn)單的三重循環(huán)，而且純粹的Floyd算法的循環(huán)體內(nèi)的語(yǔ)句也十分簡(jiǎn)潔。正是由于“Floyd算法是一種動(dòng)態(tài)規(guī)劃（Dynamic Programming）算法”的本質(zhì)，才導(dǎo)致了Floyd算法如此精妙。因此，這里將從Floyd算法的狀態(tài)定義、動(dòng)態(tài)轉(zhuǎn)移方程以及滾動(dòng)數(shù)組等重要方面，來(lái)簡(jiǎn)單剖析一下圖論中這一重要的基于動(dòng)態(tài)規(guī)劃的算法——Floyd算法。

在動(dòng)態(tài)規(guī)劃算法中，處于首要位置、且也是核心理念之一的就是狀態(tài)的定義。在這里，把d[k][i][j]定義成：“只能使用第1號(hào)到第k號(hào)點(diǎn)作為中間媒介時(shí)，點(diǎn)i到點(diǎn)j之間的最短路徑長(zhǎng)度。”

圖中共有n個(gè)點(diǎn)，標(biāo)號(hào)從1開(kāi)始到n。因此，在這里，k可以認(rèn)為是動(dòng)態(tài)規(guī)劃算法在進(jìn)行時(shí)的一種層次，或者稱(chēng)為“松弛操作”。d[1][i][j]表示只使用1號(hào)點(diǎn)作為中間媒介時(shí)，點(diǎn)i到點(diǎn)j之間的最短路徑長(zhǎng)度；d[2][i][j]表示使用1號(hào)點(diǎn)到2號(hào)點(diǎn)中的所有點(diǎn)作為中間媒介時(shí)，點(diǎn)i到點(diǎn)j之間的最短路徑長(zhǎng)度；d[n-1][i][j]表示使用1號(hào)點(diǎn)到(n-1)號(hào)點(diǎn)中的所有點(diǎn)作為中間媒介時(shí)，點(diǎn)i到點(diǎn)j之間的最短路徑長(zhǎng)度d[n][i][j]表示使用1號(hào)到n號(hào)點(diǎn)時(shí)，點(diǎn)i到點(diǎn)j之間的最短路徑長(zhǎng)度。有了狀態(tài)的定義之后，就可以根據(jù)動(dòng)態(tài)規(guī)劃思想來(lái)構(gòu)建動(dòng)態(tài)轉(zhuǎn)移方程。

動(dòng)態(tài)轉(zhuǎn)移的基本思想可以認(rèn)為是建立起某一狀態(tài)和之前狀態(tài)的一種轉(zhuǎn)移表示。按照前面的定義，d[k][i][j]是一種使用1號(hào)到k號(hào)點(diǎn)的狀態(tài)，可以想辦法把這個(gè)狀態(tài)通過(guò)動(dòng)態(tài)轉(zhuǎn)移，規(guī)約到使用1號(hào)到(k-1)號(hào)的狀態(tài)，即d[k-1][i][j]。對(duì)于d[k][i][j]（即使用1號(hào)到k號(hào)點(diǎn)中的所有點(diǎn)作為中間媒介時(shí)，i和j之間的最短路徑），可以分為兩種情況：（1）i到j(luò)的最短路不經(jīng)過(guò)k；（2）i到j(luò)的最短路經(jīng)過(guò)了k。不經(jīng)過(guò)點(diǎn)k的最短路情況下，d[k][i][j]=d[k-1][i][j]。經(jīng)過(guò)點(diǎn)k的最短路情況下，d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]。因此，綜合上述兩種情況，便可以得到Floyd算法的動(dòng)態(tài)轉(zhuǎn)移方程：

d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])（k,i,j ∈ [1,n]）

3 大型停車(chē)導(dǎo)航系統(tǒng)應(yīng)用分析

在大型停車(chē)導(dǎo)航系統(tǒng)中，會(huì)將所有的停車(chē)位錄入到數(shù)據(jù)庫(kù)中，系統(tǒng)會(huì)將數(shù)據(jù)庫(kù)的停車(chē)位構(gòu)造成初始矩陣，利用Floyd算法將計(jì)算出最短路徑。根據(jù)車(chē)主提供的所在地址和目的地址，返回號(hào)航路線，能夠提供一種高效地尋找停車(chē)位的方式。

參考文獻(xiàn)

[1]許克平,曾明月,鄢好,袁麗娟,彭圓紅.基于不確定因素下的Floyd算法改進(jìn)[J]. 中國(guó)科技信息. 2016(18).

[2]葉奇明,石世光Floyd算法的演示模型研究[J].海南大學(xué)學(xué)報(bào)(自然科學(xué)版). 2008(01).

[3]曹睿.基于Floyd算法的最短路徑問(wèn)題應(yīng)用研究[J].內(nèi)江科技. 2012(08).

[4]魏霖靜,岳建斌. Floyd算法在一類(lèi)實(shí)際問(wèn)題中的應(yīng)用[J].電腦知識(shí)與技術(shù). 2010(22).