基于Floyd算法的醫(yī)院選址實(shí)現(xiàn)

1、題 目: 基于Floyd算法的醫(yī)院選址實(shí)現(xiàn)初始條件：理論：學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)課程，掌握了基本的數(shù)據(jù)結(jié)構(gòu)和常用的算法；實(shí)踐：計(jì)算機(jī)技術(shù)系實(shí)驗(yàn)室提供計(jì)算機(jī)及軟件開(kāi)發(fā)環(huán)境。要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫等具體要求）1、系統(tǒng)應(yīng)具備的功能：（1）以鄰接表為存儲(chǔ)結(jié)構(gòu),建立n個(gè)結(jié)點(diǎn)的無(wú)向圖；（2）用Floyd算法實(shí)現(xiàn)醫(yī)院選址；（3）運(yùn)行程序。2、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)；3、主要算法設(shè)計(jì)；4、編程及上機(jī)實(shí)現(xiàn)；5、撰寫課程設(shè)計(jì)報(bào)告，包括：（1）設(shè)計(jì)題目；（2）摘要和關(guān)鍵字；（3）正文，包括引言、需求分析、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)、程序?qū)崿F(xiàn)及測(cè)試、不足之處、設(shè)計(jì)體會(huì)等；（4）結(jié)束語(yǔ)；（5）

2、參考文獻(xiàn)。時(shí)間安排： 2007年7月2日7日 （第18周）7月2日 查閱資料7月3日 系統(tǒng)設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，算法設(shè)計(jì)7月4日-5日 編程并上機(jī)調(diào)試7月6日 撰寫報(bào)告7月7日 驗(yàn)收程序，提交設(shè)計(jì)報(bào)告書(shū)。指導(dǎo)教師簽名： 2007年7月2日系主任（或責(zé)任教師）簽名： 2007年7月2日基于Flyod算法的醫(yī)院選址實(shí)現(xiàn)摘要：以最短距離為最優(yōu)目標(biāo)選址的定量技術(shù)頗多，其中，最優(yōu)化規(guī)劃法及圖論方法是研究熱點(diǎn)。本設(shè)計(jì)中闡述了無(wú)向網(wǎng)絡(luò)中選址問(wèn)題的Flyod基本模型及其全部頂點(diǎn)間最短路徑算法選址的原理，并通過(guò)實(shí)例探討了醫(yī)院選址算法的步驟及C+語(yǔ)言實(shí)現(xiàn)的全過(guò)程。關(guān)鍵詞：最優(yōu)化規(guī)劃，F(xiàn)lyod算法，醫(yī)院選址，圖論

3、0引言“數(shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課?！皵?shù)據(jù)結(jié)構(gòu)”的研究不僅涉及到計(jì)算機(jī)硬件（特別是編碼理論、存儲(chǔ)裝置和存取方法等）的研究范圍，而且和計(jì)算機(jī)軟件的研究有著更密切的關(guān)系，無(wú)論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲(chǔ)器中的分配問(wèn)題。選址問(wèn)題，是指為一個(gè)和幾個(gè)服務(wù)設(shè)施在一定區(qū)域內(nèi)選定它的位置，使某一指標(biāo)達(dá)到最優(yōu)解。這類問(wèn)題，在規(guī)劃建設(shè)中經(jīng)?？梢耘龅?，這里所謂的服務(wù)設(shè)施，可以是某些公共服務(wù)設(shè)施，如醫(yī)院，消防站，物流中心等。也可以是生產(chǎn)服務(wù)設(shè)施，如倉(cāng)庫(kù)，轉(zhuǎn)運(yùn)站等等?？梢哉J(rèn)為，選址問(wèn)題，就是把服務(wù)設(shè)施與服務(wù)對(duì)象，反映與統(tǒng)一的網(wǎng)絡(luò)中，便于對(duì)問(wèn)題進(jìn)行研究。盡管對(duì)選址的目標(biāo)、要求有不同

4、的評(píng)判標(biāo)準(zhǔn)，但是要求服務(wù)對(duì)象與服務(wù)設(shè)施之間易于溝通、易于達(dá)到，這是一個(gè)最基本的要求。本課程設(shè)計(jì)為基于Flyod算法的醫(yī)院選址的實(shí)現(xiàn)，因此在把實(shí)際的問(wèn)題簡(jiǎn)化為網(wǎng)絡(luò)模型后，建立約束函數(shù)和最終目標(biāo)函數(shù)，運(yùn)用Flyod算法求出最優(yōu)解。例如本次設(shè)計(jì)中醫(yī)院選址關(guān)心的是如何找到一個(gè)社區(qū)建立醫(yī)院使所有的社區(qū)到醫(yī)院的路徑之和最短，沒(méi)有約束函數(shù),目標(biāo)函數(shù)則為。1需求分析1.1影響醫(yī)院選址的因素1.1.1空間距離由于建醫(yī)院的主要目的是收治病人，方便病人就醫(yī)，使病人能在最短的時(shí)間內(nèi)到達(dá)醫(yī)院接受醫(yī)治，因此院方必需調(diào)查所在地區(qū)各大社區(qū)到醫(yī)院的空間距離，即病人到醫(yī)院的直接距離。此距離受地理?xiàng)l件，城市建筑等社會(huì)因素的限制。1

5、.1.2時(shí)間距離必需考慮時(shí)間距離。這是病人從發(fā)病點(diǎn)到醫(yī)院所需的時(shí)間（最好有80%的病人能在一個(gè)小時(shí)內(nèi)到達(dá)醫(yī)院），它受城市交通狀況影響較大。在我國(guó)城市當(dāng)前交通不發(fā)達(dá)的情況下，應(yīng)十分重視時(shí)間距離。近年來(lái)，某大城市新建幾所大醫(yī)院的地址，雖然環(huán)境安靜，地形理想，離社區(qū)的空間距離不太長(zhǎng)，道路也較好，但唯獨(dú)交通不便，時(shí)間距離長(zhǎng)，開(kāi)診后病人少，并未減輕其他醫(yī)院的壓力，可謂目前城市新建醫(yī)院選址的教訓(xùn)。1.1.3其他因素建院選址，除考慮上述要求外，還應(yīng)做到：納入城市規(guī)劃，合理布局；環(huán)境安靜，利于修養(yǎng)；地形理想，便于綠化；公用設(shè)施，盡量利用；地質(zhì)合適，易防污染；運(yùn)輸方便，運(yùn)費(fèi)低廉等到，這些條件也應(yīng)綜合考慮。2.數(shù)

6、據(jù)結(jié)構(gòu)設(shè)計(jì)為了使問(wèn)題更加具體，更加形象，便于求解，設(shè)計(jì)了一張網(wǎng)絡(luò)圖如下：75655258457280452250302830186870508078404870324028303832301048562826325846505636385060406270851510252625048425235504050456040380356898622825202116171819131415121011976842543122524232922282730263132333435363738394041圖中的每個(gè)節(jié)點(diǎn)表示一個(gè)社區(qū)，一共有42個(gè)社區(qū)，社區(qū)與社區(qū)之間的數(shù)字為社區(qū)之間的距離。要求是要在這4

7、2個(gè)社區(qū)里面選擇一個(gè)社區(qū)建立醫(yī)院，使其余社區(qū)到醫(yī)院的距離之和最短。2.1自定義結(jié)構(gòu)體struct Graphint vexnum;long arcxM_vexnumM_arcnum;其中vexnum為圖中的頂點(diǎn)數(shù)，在本圖中它的值為43（0號(hào)單元為用），arcxM_vexnumM_arcnum用來(lái)表示任意兩個(gè)節(jié)點(diǎn)之間的距離，初始化的時(shí)候把不同頂點(diǎn)間的距離都設(shè)為無(wú)窮大，相同頂點(diǎn)間的距離設(shè)為0。2.2結(jié)點(diǎn)距離矩陣的初始化與賦值for(i=1;i<G.vexnum;i+)for(j=1;j<G.vexnum;j+) if(i=j)G.arcxij=0;else G.arcxij=INFIN

8、ITY; 在程序運(yùn)行的時(shí)候再對(duì)它們賦值，對(duì)于上圖對(duì)其上三角矩陣賦值為：G.arcx12=40; G.arcx133=60;G.arcx134=45;G.arcx23=35;G.arcx27=50;G.arcx29=62;G.arcx310=42;G.arcx336=50;G.arcx45=10;G.arcx46=30;G.arcx429=40;G.arcx430=70;G.arcx56=28;G.arcx539=85;G.arcx540=38;G.arcx611=32;G.arcx640=30;G.arcx641=48;G.arcx710=48;G.arcx727=70;G.arcx814=3

9、6;G.arcx815=38;G.arcx828=50;G.arcx927=40;G.arcx931=52;G.arcx940=28;G.arcx1012=52;G.arcx1115=56;G.arcx1125=40;G.arcx1127=48;G.arcx1213=80;G.arcx1320=68; G.arcx1327=50;G.arcx1417=56;G.arcx14 23=50; G.arcx1518=58;G.arcx15 25=46;G.arcx1542=28; G.arcx1618=75;G.arcx16 21=58;G.arcx1623=65;G.arcx1723=52;G.a

10、rcx1819=22;G.arcx18 23=45;G.arcx1825=30; G.arcx1922=72;G.arcx19 26=28;G.arcx2022=80;G.arcx20 24=50;G.arcx2122=45;G.arcx2426=30;G.arcx2526=18; G.arcx2627=70;G.arcx2740=32;G.arcx2829=60;G.arcx28 42=32; G.arcx2930=62;G.arcx3039=15;G.arcx3132=50;G.arcx3231=50; G.arcx3234=25; G.arcx3235= 98; G.arcx3238=6

11、8; G.arcx3239=62;G.arcx3336=40;G.arcx3337=38; G.arcx3539=102;G.arcx3738=35;G.arcx4142=26;因?yàn)槭菬o(wú)向圖，所以VijVji ，得到圖完整的鄰接矩陣，語(yǔ)句如下：for(i=1;i<G.vexnum;i+)for(j=1;j<i;j+)G.arcxij=G.arcxji;3.算法設(shè)計(jì)圖論中的最短路徑算法包括指定的頂點(diǎn)之間的最短路徑算法和全部頂點(diǎn)間的最短路徑算法。前者可用于運(yùn)輸?shù)暮侠砘瘺Q策分析，一般用迪杰斯特拉（Dijkstra）算法實(shí)現(xiàn),而后者很適合于選址合理的中心等,使總的路程最短,一般用弗洛伊德(

12、Flyod)算法求解。3.1 算法的基本思想 全部頂點(diǎn)間最短路徑算法具有代表性的是1962年有福勞德（Flyod）提出的算法。它的主要思想是從代表任意2個(gè)頂點(diǎn)到的距離帶權(quán)鄰接矩陣開(kāi)始，每次插入一個(gè)頂點(diǎn)，然后將到間的已知最短路徑于插入頂點(diǎn)作為中間頂點(diǎn)（一條路徑中始點(diǎn)外和終點(diǎn)外的其他頂點(diǎn)）時(shí)可能產(chǎn)生的到路徑距離比較，取較小值以得到新的距離矩陣。如此循環(huán)迭代下去，依次構(gòu)造出n個(gè)矩陣D（1）,D（2）, D（3）,D（n），當(dāng)所有的頂點(diǎn)均作為任意2個(gè)頂點(diǎn)到中間頂點(diǎn)時(shí)得到的最后帶權(quán)鄰接矩陣D就反映了所以頂點(diǎn)對(duì)之間的最短距離信息，成為圖G的距離矩陣。最后對(duì)G中各行元素求和值并比較大小，決定單個(gè)或多個(gè)最佳的

13、中心。3.2 Flyod算法構(gòu)造距離矩陣的原理 對(duì)一個(gè)有n個(gè)頂點(diǎn)的圖G，將頂點(diǎn)用n個(gè)整數(shù)（從1到n）進(jìn)行編號(hào)。把G的帶權(quán)鄰接矩陣W作為距離矩陣的初值，即D（0）（d（0）ij）n*nW。 第一步構(gòu)造D（1）（d（1）ij）n*n，其中dijmind（1）i1d（1）1j是從到的允許到作為中間點(diǎn)的路徑中最短距離長(zhǎng)度。 第二步構(gòu)造D（2）（d（1）ij）n*n，其中dijmind（2）ij，d（2）i2d（2）2j是從到的只 許以，作為中間點(diǎn)的路徑最短長(zhǎng)度。 第n步構(gòu)造D（n）（d（n）ij），其中dijmind（n）ij，d（n）ind（n）nj是從到的只允許以，作為中間點(diǎn)的所有路徑中最短路的長(zhǎng)

14、度，即是從到中間可插入任何頂點(diǎn)的路徑中最短路的長(zhǎng)度，因此D即是距離矩陣。4 .程序?qū)崿F(xiàn)4.1圖的初始化for(i=1;i<G.vexnum;i+)for(j=1;j<G.vexnum;j+) if(i=j)G.arcxij=0;else G.arcxij=INFINITY; 4.2任意兩個(gè)頂點(diǎn)之間最短距離的計(jì)算計(jì)算任意兩個(gè)頂點(diǎn)之間的最短距離的方法有很多，最基本的有迪杰斯特拉（Dijkstra）算法和弗洛伊德（Flyod）算法。相比之下，F(xiàn)lyod算法比Dijkstra算法更容易理解，算法在一次運(yùn)算中可以求出任意兩個(gè)頂點(diǎn)之間的距離,并且它們的時(shí)間復(fù)雜度都是o(n3)。以下代碼是整個(gè)程

15、序中最重要的部分，它將求解出圖的距離矩陣。for(v=1;v<G.vexnum;v+)for(w=1;w<G.vexnum;w+)Dvw=G.arcxvw;for(u=1;u<G.vexnum;u+)Pvwu=FALSE;if(Dvw<INFINITY)Pvwu=TRUE;Pvww=TRUE;for(u=1;u<G.vexnum;u+)for(v=1;v<G.vexnum;v+)for(w=1;w<G.vexnum;w+)if(Dvu+Duw<Dvw)Dvw=Dvu+Duw;for(i=1;i<G.vexnum;i+)Pvwi=Pvui;4

16、.3確定醫(yī)院地址的算法得到圖的距離矩陣后，要想從中得到醫(yī)院的地址。我們分析，醫(yī)院選址的要求是使所有的頂點(diǎn)到醫(yī)院的距離之和最短，既然已經(jīng)求出了圖的距離矩陣，那么把矩陣的沒(méi)一行或者每一列進(jìn)行相加，就得到所有頂點(diǎn)到該頂點(diǎn)的距離之和，重復(fù)此操作42次就會(huì)得到所以的頂點(diǎn)到每個(gè)頂點(diǎn)距離之和，然后從中選取最小值，該數(shù)對(duì)應(yīng)的點(diǎn)則為醫(yī)院的地址。for(v=1;v<G.vexnum;v+)sumv=0;for(w=1;w<G.vexnum;w+)sumv+=Dvw;temp=sum1;for(v=1;v<G.vexnum;v+)if(sumv<temp)temp=sumv;node=v;4

17、.4運(yùn)行結(jié)果這是一個(gè)42*42的矩陣,即是圖的距離矩陣,矩陣中的每一個(gè)元素對(duì)應(yīng)的橫縱結(jié)點(diǎn)之間的最短距離。為了檢查結(jié)果的正確與否，另外用優(yōu)化軟件lingo對(duì)其進(jìn)行建模，取其中結(jié)點(diǎn)1的數(shù)據(jù)，即所以結(jié)點(diǎn)到結(jié)點(diǎn)1的最短距離：D1( N1, N1) 0.000000D1( N1, N2) 40.00000D1( N1, N3) 75.00000D1( N1, N4) 178.0000D1( N1, N5) 168.0000D1( N1, N6) 160.0000D1( N1, N7) 90.00000D1( N1, N8) 284.0000D1( N1, N9) 102.0000D1( N1, N10)

18、 117.0000D1( N1, N11) 190.0000D1( N1, N12) 169.0000D1( N1, N13) 192.0000D1( N1, N14) 320.0000D1( N1, N15) 246.0000D1( N1, N16) 335.0000D1( N1, N17) 357.0000D1( N1, N18) 260.0000D1( N1, N19) 240.0000D1( N1, N20) 260.0000D1( N1, N21) 357.0000D1( N1, N22) 312.0000D1( N1, N23) 305.0000D1( N1, N24) 242.0

19、000D1( N1, N25) 230.0000D1( N1, N26) 212.0000D1( N1, N27) 142.0000D1( N1, N28) 266.0000D1( N1, N29) 209.0000D1( N1, N30) 147.0000D1( N1, N31) 120.0000D1( N1, N32) 70.00000D1( N1, N33) 60.00000D1( N1, N34) 45.00000D1( N1, N35) 168.0000D1( N1, N36) 100.0000D1( N1, N37) 98.00000D1( N1, N38) 133.0000D1(

20、 N1, N39) 132.0000D1( N1, N40) 130.0000D1( N1, N41) 208.0000D1( N1, N42) 234.0000把結(jié)果與C代碼運(yùn)行的結(jié)果做比較，可以發(fā)現(xiàn)結(jié)果是一致的。 sumi表示其他頂點(diǎn)到i點(diǎn)距離之和，如圖所示，從中選取最小值則為醫(yī)院建立的地址，從結(jié)果中可以看到社區(qū)27適合建立醫(yī)院。5 設(shè)計(jì)體會(huì) 這次課程設(shè)計(jì)給了我一個(gè)很好的機(jī)會(huì)去鍛煉運(yùn)用所學(xué)知識(shí)去解決實(shí)際問(wèn)題的能力。在學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)之后，對(duì)書(shū)上的算法的了解也僅僅停留在理論階段，但是一但需要用它解決實(shí)際問(wèn)題的時(shí)候，問(wèn)題常常接踵而至。首先感到棘手的就是將偽代碼轉(zhuǎn)化為可以執(zhí)行的C代碼，特別是涉及到指針與函數(shù)之間參數(shù)傳遞的算法，必須將C