基于Floyd算法的大型停車場導航系統的設計

高振，陳順龍，王玨輝

（長江大學工程技術學院，湖北荊州，434000）

0 引言

“停車難”加重交通擁堵。在北京中關村、南京新街口、廣州天河等繁華商圈，車位的捉襟見肘造成了交通的嚴重擁堵。“停車難”引發公共糾紛。把Floyd算法應用在大型停車導航系統的設計，在一定程度上，能夠解決“停車難”的問題。

1 Floyd算法的原理分析

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

圖1 圖轉化矩陣

圖2 初始矩陣轉化最短路徑矩陣

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

2 探求Floyd算法的動態規劃本質

從表面上粗看，Floyd算法是一個非常簡單的三重循環，而且純粹的Floyd算法的循環體內的語句也十分簡潔。正是由于“Floyd算法是一種動態規劃（Dynamic Programming）算法”的本質，才導致了Floyd算法如此精妙。因此，這里將從Floyd算法的狀態定義、動態轉移方程以及滾動數組等重要方面，來簡單剖析一下圖論中這一重要的基于動態規劃的算法——Floyd算法。

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

圖中共有n個點，標號從1開始到n。因此，在這里，k可以認為是動態規劃算法在進行時的一種層次，或者稱為“松弛操作”。d[1][i][j]表示只使用1號點作為中間媒介時，點i到點j之間的最短路徑長度；d[2][i][j]表示使用1號點到2號點中的所有點作為中間媒介時，點i到點j之間的最短路徑長度；d[n-1][i][j]表示使用1號點到(n-1)號點中的所有點作為中間媒介時，點i到點j之間的最短路徑長度d[n][i][j]表示使用1號到n號點時，點i到點j之間的最短路徑長度。有了狀態的定義之后，就可以根據動態規劃思想來構建動態轉移方程。

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

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 大型停車導航系統應用分析

在大型停車導航系統中，會將所有的停車位錄入到數據庫中，系統會將數據庫的停車位構造成初始矩陣，利用Floyd算法將計算出最短路徑。根據車主提供的所在地址和目的地址，返回號航路線，能夠提供一種高效地尋找停車位的方式。

參考文獻

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

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

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

[4]魏霖靜,岳建斌. Floyd算法在一類實際問題中的應用[J].電腦知識與技術. 2010(22).