Floyd算法在中心小學選址上的應用

摘要：中心小學選址是一個非常重要的問題。是將地理信息作為選址的主要依據，將幾個相鄰的村子的地理信息抽象成數學當中的圖，然后用圖論中求中心點和中位點的方法來確定中心小學的位置。在求中心點、中位點時要用到圖論中最短路徑算法，對經典的最短路徑算法Floyd算法作了介紹。最后，用實例來分析中心點與中位點選址模型，并對中位點模型作了進一步分析。

關鍵詞：中心小學選址； Floyd算法； 最短路徑

中圖分類號：TP399 文獻標識碼：A文章編號：2095-2163（2013）02-0080-03

0引言

自1979年中國推行計劃生育政策以來，農村人口出生率呈明顯下降態勢，而如何保證農村人口接受優質教育的問題日益迫切地擺在每個規范農村教育發展，關注農村教育進步的有識之士面前。農村教學點布局不盡合理，生源明顯不足，學校規模局促、辦學效益走低等。

2006年，教育部發出《關于實事求是地做好農村中小學布局調整工作的通知》，通知要求“大力發展鄉鎮中心學校，啟動寄宿制學校的標準化建設，提高農村教育質量?！币恍┑胤介_始有目標、有規劃、分階段、分步驟地調整小學布局，對未達到一定規模的小學教學點陸續進行了撤并，設立鄉鎮中心小學。

但是，由目前農村中心小學選址的現狀，其最終的選址結果卻仍存在一定的缺陷和弊端。諸如：頻繁出現的交通事故，學校布局過于密集或分散造成的不合理利用率等。通常，農村中心小學選址的影響因素則有許多，其中如交通條件、自然地理條件、道路狀況和學生人數等，就是最為關鍵的影響因素。如何將這些因素有效納入選址決策，并科學規劃農村中心小學布局，在發揮其最大效益的同時，能夠更為符合農村人口結構特征，并進一步保證學生上學、放學的安全則顯得越發重要。本文探討了一種基于Floyd算法的完整實用技術，可在廣大農村轄區內為中心小學實現合理選址，選址效果滿足了多項性能指標需求，因而具有一定的理論意義和實用價值。

1Floyd算法的基本思想

最短路徑問題是圖論中的一個基本內容.在賦權圖中，每一條邊都定義了一個權值（距離、成本、時間等），搜索得到兩點之間權值總和最小的路徑就是最小路徑問題.最短路徑問題，通常可分為三類[1]：單源最短路徑問題；確定起點、終點的最短路徑問題；全局最短路徑問題。

Floyd算法[2]可借助于權矩陣，直接求得任意兩點間的最短路徑。假設需要求取由節點i到j的最短路徑，實現步驟是：

（1）如果i、j間有邊，則由i到j存在一條長度為cost[i，j]的路徑，該路徑不一定是最短的路徑，還需要進行n次試探.

（2）從i經過若干個節點k到j。所以，假設Dis（i，j）為節點i到節點j的最短路徑距離，對于每一個節點k，檢查Dis （i，k） + Dis （k，j） < Dis （i，j）是否成立，如果成立，證明從i→k→j的路徑比i→j的路徑短，便可設置Dis（i，j） = Dis（i，k） + Dis（k，j），當遍歷完成所有節點k以后，Dis（i，j）就記錄了i→j的最短路徑距離。

2中心小學選址模型的算法與分析

21選址模型介紹

根據選址設定的目標函數不同，可以分為中心點問題和中位點問題。中心點問題的目標函數是使得“最大距離達到最小”；中位點問題的目標函數是使得“距離總和達到最小”，本文選用的是中位點方法[3]。

中位點問題是研究如何選擇一個服務站（本文是中心小學），使得需求點和服務站間的距離與需求量的乘積之和能夠限定為最小。中位點問題可以用如下模型進行表示：

其中：Wi表示需求點和設施點間的最大距離；Vi代表可選的頂點；Vj代表任意頂點.第2期吳煥瑞，等：Floyd算法在中心小學選址上的應用智能計算機與應用第3卷

22建立拓撲圖

農村的交通網絡，可以將村莊和道路抽象為其組成節點和連接邊均為有限的有向圖G。在建立圖G前，先進行如下處理：如果兩個村子之間存在兩條路，則以一條邊實際計算，并確定其權值為兩條路中最短長度。如此處理，是為了使圖G成為一個簡單圖。

例如：選取河北省三河市泃陽鎮的幾個相鄰的村落來討論中心小學的選址模型，圖1是從搜狗地圖中下載的地圖圖片，對圖1抽象處理，得到的拓撲如圖2所示。其中，頂點代表村落，邊代表兩頂點所對應的村落之間有連接道路，邊上的權值代表兩個村落間的距離，單位為500米。

23中心小學選址實例實現

建立圖G所對應的鄰接矩陣，如圖3所示。采用C語言實現中位點求解。通過計算，在中位點選址模型中選取趙河溝（節點③）為中心小學的選址地點，可滿足中位點的選址要求。程序調試結果如圖4所示。

3.1模型分析

上述求取中位點的過程中，只是考慮了村落地理位置這一基本因素，卻未考慮到每個村落的人口因素，而人口因素也是中心小學的選址的重要因素，因此可做如下處理以重新建立中位點選址模型。

每個村落都有相對固定的人口數和家庭數?？蓪D2中建立的圖G的每個頂點再加上一個權值，這個權值用來體現人口因素，現在需要決策將每個村落頂點的權值設為該村子的人口數，還是設為其中的學齡兒童數.顯然，選取每個村落的學齡兒童數作為頂點的權值，較為合理。

在帶權值的頂點圖上選取中位點，在鄰接矩陣中求出了Edge[M][M]矩陣，其中，第i行第j列表示i與j間的最短路徑長度。將頂點的權值按照順序構造一個向量q，用向量q與矩陣Edge[M][M]相乘，得到一個新的向量，存到search[M]中，再從search[M]找到其中最小的，得到中位點位置[4]。當M=10時，其數學表達式為：

在si（i=0，…，9）中尋到最小值，該值所對應的頂點就是中位點。用此方法擇選的中心小學位置，既考慮了村落之間的地理因素，也考慮了每個村落的人口因素，更具有全面的合理性，對中心小學的實際選址更為顯明的借鑒和參考作用。

32實例求解

如前所述，利用每個村落的學齡兒童的數作為圖頂點的權值，各個村落的具體數值是：趙屠莊村284人、李河溝村63人、馬河溝村135人、大田莊村177人、趙河溝村355人、小田莊村和北陳莊村324人、方元屯村248人、鄭辛莊戶村188人、大丁河溝和小丁河溝357人、溝北莊戶村438人。頂點權值構成的向量為：（24863135177355324248188357438）

這個模型求解結果是選取大丁河溝和小丁河溝作為中心小學的選址地點。在Visual C++6.0中計算結果如圖5所示。圖5 中位點加權法調試結果

Fig.5 The debugging results of Weighted method

4結束語

針對近年來中心小學的建設現狀，介紹了圖論知識在選址上的應用。本文將幾個村落的地理信息作為中心小學選址需要考慮的因素，其做法就是將幾個村落的地理信息抽象為數學中的拓撲圖，再利用Floyd算法進行實例驗證。在文章最后，還對中位點模型展開了更進一步的分析，將每個村落的人口因素看作是圖G頂點的權值，由此，在中位點選址方案中，就考慮了地理和人口因素，選址的結果將更加科學合理，具有良好的推廣應用價值。

參考文獻：

[1]姬東. 圖論最短路徑問題在消防選址中的應用[J]. 武警學院學報，2009，25（12）：10-12.

[2]嚴蔚敏，吳偉民. 數據結構（C語言版）[M]. 北京：清華大學出版社，2007：186-192.

[3]楊豐梅， 華國偉， 鄧猛，等. 選址問題研究的若干進展[J]. 運籌與管理，2005，14（6）：1-6.

[4]黎青松，楊偉，曾傳華. 中心問題與中位問題的研究現狀[J].系統工程，2005，23（5）：11-16.