數(shù)據(jù)結(jié)構(gòu)算法應(yīng)用
——基于Floyd算法的醫(yī)院選址問(wèn)題求解

陳志珍，陳 燕，李桃迎

（大連海事大學(xué)，遼寧 大連 116026）

數(shù)據(jù)結(jié)構(gòu)算法應(yīng)用
——基于Floyd算法的醫(yī)院選址問(wèn)題求解

陳志珍，陳 燕，李桃迎

（大連海事大學(xué)，遼寧 大連 116026）

本文闡述了數(shù)據(jù)結(jié)構(gòu)中Floyd最短路徑算法的原理，實(shí)例討論了使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短的醫(yī)院選址問(wèn)題，將地理信息抽象為數(shù)據(jù)結(jié)構(gòu)中的圖，采用Floyd算法，描述了醫(yī)院選址問(wèn)題的算法及其具體實(shí)現(xiàn)步驟，最后通過(guò)C語(yǔ)言實(shí)現(xiàn)鄰接矩陣的存儲(chǔ)結(jié)構(gòu)和主要算法。

數(shù)據(jù)結(jié)構(gòu)；Floyd最短路徑算法；醫(yī)院選址；C語(yǔ)言

一、引言

《數(shù)據(jù)結(jié)構(gòu)》課程是計(jì)算機(jī)類、信息管理類、電子商務(wù)、經(jīng)濟(jì)類及相關(guān)專業(yè)的一門重要的專業(yè)基礎(chǔ)課程。早在1968年，美國(guó)一些學(xué)校的計(jì)算機(jī)系就開(kāi)設(shè)《數(shù)據(jù)結(jié)構(gòu)》課程。20世紀(jì)70年代中后期，我國(guó)也開(kāi)設(shè)《數(shù)據(jù)結(jié)構(gòu)》課程作為計(jì)算機(jī)專業(yè)的核心課程。開(kāi)設(shè)該課程的目的在于讓學(xué)者了解數(shù)據(jù)的計(jì)算機(jī)外部邏輯結(jié)構(gòu)和計(jì)算機(jī)內(nèi)部的存儲(chǔ)結(jié)構(gòu)以及相關(guān)操作，它為后續(xù)的專業(yè)課程，如編譯原理、數(shù)據(jù)庫(kù)原理、操作系統(tǒng)、系統(tǒng)分析與設(shè)計(jì)等課程提供必要的知識(shí)和技能準(zhǔn)備。本人認(rèn)為數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)中的難點(diǎn)包括遞歸程序的閱讀、非線性結(jié)構(gòu)中圖和樹(shù)的相關(guān)算法，尤其是圖的最短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑的基本應(yīng)用，學(xué)習(xí)難點(diǎn)在于：圖的存儲(chǔ)結(jié)構(gòu)、圖中頂點(diǎn)的定位、圖中各個(gè)頂點(diǎn)的訪問(wèn)方法等。本文試圖就圖的最短路徑算法的學(xué)習(xí)過(guò)程進(jìn)行探討。在學(xué)習(xí)中，我們發(fā)現(xiàn)：在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)元素之間都有可能相鄰，如果對(duì)圖進(jìn)行操作或者遍歷的話，必須先確定圖中第一個(gè)訪問(wèn)的頂點(diǎn)，才能對(duì)其他頂點(diǎn)進(jìn)行訪問(wèn)（操作），因此，圖是一種比線性表和樹(shù)更為復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。圖之所以仍然作為《數(shù)據(jù)結(jié)構(gòu)》課程的重要內(nèi)容出現(xiàn)，是因?yàn)閳D的存儲(chǔ)結(jié)構(gòu)容易定義和掌握，但是需要通過(guò)圖的形式化定義及其相關(guān)操作來(lái)實(shí)現(xiàn)具體問(wèn)題的求解，這就是我們所說(shuō)的在《數(shù)據(jù)結(jié)構(gòu)》的圖中需要掌握的重要知識(shí)點(diǎn)。圖的運(yùn)算已經(jīng)成為人們解決實(shí)際問(wèn)題的重要工具，比如通過(guò)Prim算法或Kruskal算法求最小生成樹(shù)以構(gòu)造最低價(jià)的通信網(wǎng)；通過(guò)關(guān)鍵路徑求解確定一個(gè)工程中的“關(guān)鍵工程”；通過(guò)Dijkstra算法求某個(gè)源點(diǎn)到其余各個(gè)頂點(diǎn)的最短路徑，解決物流配送的最短路徑選擇；通過(guò)Floyd算法計(jì)算每一對(duì)頂點(diǎn)之間的最短路徑，用于確定設(shè)施的選址。本文重點(diǎn)討論Floyd算法在醫(yī)院選址問(wèn)題中的應(yīng)用。

醫(yī)院是社會(huì)的重要基礎(chǔ)設(shè)施，醫(yī)院建設(shè)的選址必須本著以人為本、服務(wù)社會(huì)、經(jīng)濟(jì)效益的原則，如何使群眾就醫(yī)路徑較短，是醫(yī)院選址需要充分考慮的問(wèn)題，本文以患者就醫(yī)路徑最短為切入點(diǎn)，選址問(wèn)題轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)圖論中的求解最短路徑的問(wèn)題，并采用Floyd算法對(duì)最短路徑問(wèn)題進(jìn)行求解，為醫(yī)院的選址問(wèn)題提供定量分析。

二、Floyd算法基礎(chǔ)概念

1.圖：頂點(diǎn)和連線的集合，G=（V，VR），其中V是圖中頂點(diǎn)的有窮非空集合，VR是兩個(gè)頂點(diǎn)的關(guān)系的集合，即圖中連線的集合。若VR中頂點(diǎn)對(duì)＜v，w＞是有序的，則為有向圖，否則為無(wú)向圖。

2.連通圖：在無(wú)向圖或者有向圖G=（V，VR）中，若任意兩個(gè)頂點(diǎn)v，w都能找到一條路徑連接v和w，G即為連通圖。

3.網(wǎng)：帶權(quán)值的圖稱為網(wǎng)。

4.鄰接矩陣：表示頂點(diǎn)之間連接關(guān)系的矩陣。網(wǎng)的鄰接矩陣定義如下：

三、Floyd算法基本思想

最短路徑問(wèn)題是數(shù)據(jù)結(jié)構(gòu)圖論中的一個(gè)典型問(wèn)題，這里的最短路徑，不僅僅指的是距離的長(zhǎng)短，還可以引申為經(jīng)濟(jì)費(fèi)用、時(shí)間等廣義上的最短。在數(shù)據(jù)結(jié)構(gòu)中求解網(wǎng)絡(luò)中任意兩個(gè)頂點(diǎn)之間的最短路徑的典型算法是Floyd算法。

Floyd算法的基本思想是：從帶權(quán)鄰接矩陣出發(fā)，若（vi，vj） 存在，則存在路徑長(zhǎng)度D[i][j]，但該路徑不一定是最短路徑，需要進(jìn)行n次試探。如果存在一個(gè)k，且D[i][k]+D[k][j]＜D[i][j]，則將vk插入到vi到vj的路徑中，得到新的矩陣D1，經(jīng)過(guò)n次循環(huán)迭代，比較過(guò)所有頂點(diǎn)作為任意兩個(gè)頂點(diǎn)之間的中間點(diǎn)的路徑，得到最后的最短距離矩陣Dn。

四、實(shí)例應(yīng)用

（一）醫(yī)院選址問(wèn)題建模

現(xiàn)假設(shè)給定n個(gè)村莊之間的交通圖，現(xiàn)在要從這n個(gè)村莊中選擇一個(gè)村莊建一所醫(yī)院，要求離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短。

上述問(wèn)題中，可將地理信息中的交通網(wǎng)絡(luò)抽象為數(shù)學(xué)模型，以頂點(diǎn)表示村莊，以連線表示村莊之間的道路，因此交通圖轉(zhuǎn)化為由有限頂點(diǎn)和有限條邊組成的無(wú)向圖，圖中頂點(diǎn)之間的關(guān)系由權(quán)值表示，定義權(quán)矩陣為前述網(wǎng)的帶權(quán)鄰接矩陣，wij的值為村莊之間的道路距離。這樣醫(yī)院選址問(wèn)題就轉(zhuǎn)化為在全部頂點(diǎn)之間最短距離的最大值中尋找最小值的問(wèn)題，按照Floyd算法進(jìn)行運(yùn)算。

（二）醫(yī)院選址算法示例

1.假設(shè)有6個(gè)村莊，村莊v0、v1之間道路距離為12，v0、v2為3，v0、v4為9，v0、v5為10，v1、v3為2，v1、v4為6，v2、v3為2，v2、v5為6，v3、v4為4，v3、v5為7，v4、v5為4。將6個(gè)村莊作為頂點(diǎn)，有直接道路的村莊之間連線，頂點(diǎn)之間的邊所對(duì)應(yīng)的權(quán)值為村莊之間的道路距離。

2.按照上文的算法，建立帶權(quán)鄰接矩陣D0。

3.第一次迭代，插入v0后計(jì)算最短路徑，即兩點(diǎn)之間可以有一個(gè)中間點(diǎn)的最短路徑，D1[i][j]=min{D0[i][j]，D0[i] +D0[j]}。

4.第二次迭代，插入v1，D2[i][j]=min{D1[i][j]，D1[i]+D1[j]}，在D1的基礎(chǔ)上構(gòu)建D2。

5.第三次迭代，插入v2，D3[i][j]=min{D2[i][j]，D2[i]+D2[j]}，在D2的基礎(chǔ)上構(gòu)建D3。

6.第四次迭代，插入v3，D4[i][j]=min{D3[i][j]，D3[i]+D3[j]}，在D3的基礎(chǔ)上構(gòu)建D4。

7.第五次迭代，插入v4，D5[i][j]=min{D4[i][j]，D4[i]+D4[j]}，在D4的基礎(chǔ)上構(gòu)建D5。

8.第六次迭代，插入v5，D6[i][j]=min{D5[i][j]，D5[i]+D5[j]}，在D5的基礎(chǔ)上構(gòu)建D6，D6就是最后求得的最短距離矩陣。

9.以各個(gè)頂點(diǎn)為源點(diǎn)的最短距離的最大值maxdis= {9，9，6，7，9，9}，min{maxdis[i]}=6，對(duì)應(yīng)頂點(diǎn)為v2，因此本例的最終醫(yī)院選址為v2村莊。

（三）選址算法的C語(yǔ)言實(shí)現(xiàn)

1.圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)表示。

五、結(jié)論

實(shí)際應(yīng)用中，醫(yī)院選址問(wèn)題需要考慮眾多因素，可以設(shè)置權(quán)值為各項(xiàng)耗費(fèi)總值。本文運(yùn)用Floyd算法將醫(yī)院選址問(wèn)題進(jìn)行了量化，并采用C語(yǔ)言實(shí)現(xiàn)，在實(shí)際的設(shè)施合理選擇中，具有一定的理論意義和實(shí)用價(jià)值。除了選址問(wèn)題，物流配送的路線選擇、旅游中最短路線的設(shè)計(jì)等問(wèn)題都可以通過(guò)建立數(shù)學(xué)模型進(jìn)行算法設(shè)計(jì)。在數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)過(guò)程中，我們更需要學(xué)會(huì)的是如何將實(shí)際問(wèn)題抽象為合理的數(shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解決該模型的算法，最后進(jìn)行編程、測(cè)試得到最終解答。

[1]陳燕,曹妍,賈紅雨.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：科學(xué)出版社，2014．

[2]王軍，王偉,公長(zhǎng)春.基于多因素評(píng)價(jià)法下的社區(qū)醫(yī)院投資研究[J].中國(guó)全科醫(yī)學(xué),2010，13（10A）：3143-3144.

[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：清華大學(xué)出版社，2009.

[4]王曉東.算法設(shè)計(jì)與分析[M].北京：清華大學(xué)出版社,2011.

[5]趙麗娜，李慧.基于Floyd最短路徑算法的教材中心選址問(wèn)題[J].中國(guó)教育技術(shù)裝備，2014，（4）：40-42.

G642.41

A

1674-9324（2014）36-0280-02

國(guó)家自然科學(xué)基金（71271034）；中央高校基本科研業(yè)務(wù)費(fèi)（3132014307，3132014080）；遼寧省社科基金項(xiàng)目（L13DGL060）；遼寧省教育廳一般項(xiàng)目（L2012173）。

陳志珍（1992-），女，浙江衢州人，大連海事大學(xué)信息管理與信息系統(tǒng)專業(yè)本科生，研究方向：管理科學(xué)與決策支持系統(tǒng)；陳燕（1952-），女，遼寧大連人，博士，大連海事大學(xué)管理科學(xué)與工程教授，博士生導(dǎo)師，研究方向：交通運(yùn)輸現(xiàn)代化管理、決策支持系統(tǒng)、知識(shí)管理、數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘；李桃迎（1981-），女，安徽蕭縣人，博士，大連海事大學(xué)管理科學(xué)與工程副教授，研究方向：決策支持、數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘。