1、題 目: 基于Floyd算法的醫院選址實現初始條件：理論：學習了數據結構課程，掌握了基本的數據結構和常用的算法；實踐：計算機技術系實驗室提供計算機及軟件開發環境。要求完成的主要任務: （包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求）1、系統應具備的功能：（1）以鄰接表為存儲結構,建立n個結點的無向圖；（2）用Floyd算法實現醫院選址；（3）運行程序。2、數據結構設計；3、主要算法設計；4、編程及上機實現；5、撰寫課程設計報告，包括：（1）設計題目；（2）摘要和關鍵字；（3）正文，包括引言、需求分析、數據結構設計、算法設計、程序實現及測試、不足之處、設計體會等；（4）結束語；（5）

2、參考文獻。時間安排： 2007年7月2日7日 （第18周）7月2日 查閱資料7月3日 系統設計，數據結構設計，算法設計7月4日-5日 編程并上機調試7月6日 撰寫報告7月7日 驗收程序，提交設計報告書。指導教師簽名： 2007年7月2日系主任（或責任教師）簽名： 2007年7月2日基于Flyod算法的醫院選址實現摘要：以最短距離為最優目標選址的定量技術頗多，其中，最優化規劃法及圖論方法是研究熱點。本設計中闡述了無向網絡中選址問題的Flyod基本模型及其全部頂點間最短路徑算法選址的原理，并通過實例探討了醫院選址算法的步驟及C+語言實現的全過程。關鍵詞：最優化規劃，Flyod算法，醫院選址，圖論

3、0引言“數據結構”在計算機科學中是一門綜合性的專業基礎課。“數據結構”的研究不僅涉及到計算機硬件（特別是編碼理論、存儲裝置和存取方法等）的研究范圍，而且和計算機軟件的研究有著更密切的關系，無論是編譯程序還是操作系統，都涉及到數據元素在存儲器中的分配問題。選址問題，是指為一個和幾個服務設施在一定區域內選定它的位置，使某一指標達到最優解。這類問題，在規劃建設中經常可以碰到，這里所謂的服務設施，可以是某些公共服務設施，如醫院，消防站，物流中心等。也可以是生產服務設施，如倉庫，轉運站等等。可以認為，選址問題，就是把服務設施與服務對象，反映與統一的網絡中，便于對問題進行研究。盡管對選址的目標、要求有不同

4、的評判標準，但是要求服務對象與服務設施之間易于溝通、易于達到，這是一個最基本的要求。本課程設計為基于Flyod算法的醫院選址的實現，因此在把實際的問題簡化為網絡模型后，建立約束函數和最終目標函數，運用Flyod算法求出最優解。例如本次設計中醫院選址關心的是如何找到一個社區建立醫院使所有的社區到醫院的路徑之和最短，沒有約束函數,目標函數則為。1需求分析1.1影響醫院選址的因素1.1.1空間距離由于建醫院的主要目的是收治病人，方便病人就醫，使病人能在最短的時間內到達醫院接受醫治，因此院方必需調查所在地區各大社區到醫院的空間距離，即病人到醫院的直接距離。此距離受地理條件，城市建筑等社會因素的限制。1

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

6、據結構設計為了使問題更加具體，更加形象，便于求解，設計了一張網絡圖如下：75655258457280452250302830186870508078404870324028303832301048562826325846505636385060406270851510252625048425235504050456040380356898622825202116171819131415121011976842543122524232922282730263132333435363738394041圖中的每個節點表示一個社區，一共有42個社區，社區與社區之間的數字為社區之間的距離。要求是要在這4

7、2個社區里面選擇一個社區建立醫院，使其余社區到醫院的距離之和最短。2.1自定義結構體struct Graphint vexnum;long arcxM_vexnumM_arcnum;其中vexnum為圖中的頂點數，在本圖中它的值為43（0號單元為用），arcxM_vexnumM_arcnum用來表示任意兩個節點之間的距離，初始化的時候把不同頂點間的距離都設為無窮大，相同頂點間的距離設為0。2.2結點距離矩陣的初始化與賦值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; 在程序運行的時候再對它們賦值，對于上圖對其上三角矩陣賦值為：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;因為是無向圖，所以VijVji ，得到圖完整的鄰接矩陣，語句如下：for(i=1;i<G.vexnum;i+)for(j=1;j<i;j+)G.arcxij=G.arcxji;3.算法設計圖論中的最短路徑算法包括指定的頂點之間的最短路徑算法和全部頂點間的最短路徑算法。前者可用于運輸的合理化決策分析，一般用迪杰斯特拉（Dijkstra）算法實現,而后者很適合于選址合理的中心等,使總的路程最短,一般用弗洛伊德(

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

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

14、度，即是從到中間可插入任何頂點的路徑中最短路的長度，因此D即是距離矩陣。4 .程序實現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任意兩個頂點之間最短距離的計算計算任意兩個頂點之間的最短距離的方法有很多，最基本的有迪杰斯特拉（Dijkstra）算法和弗洛伊德（Flyod）算法。相比之下，Flyod算法比Dijkstra算法更容易理解，算法在一次運算中可以求出任意兩個頂點之間的距離,并且它們的時間復雜度都是o(n3)。以下代碼是整個程

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確定醫院地址的算法得到圖的距離矩陣后，要想從中得到醫院的地址。我們分析，醫院選址的要求是使所有的頂點到醫院的距離之和最短，既然已經求出了圖的距離矩陣，那么把矩陣的沒一行或者每一列進行相加，就得到所有頂點到該頂點的距離之和，重復此操作42次就會得到所以的頂點到每個頂點距離之和，然后從中選取最小值，該數對應的點則為醫院的地址。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運行結果這是一個42*42的矩陣,即是圖的距離矩陣,矩陣中的每一個元素對應的橫縱結點之間的最短距離。為了檢查結果的正確與否，另外用優化軟件lingo對其進行建模，取其中結點1的數據，即所以結點到結點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把結果與C代碼運行的結果做比較，可以發現結果是一致的。 sumi表示其他頂點到i點距離之和，如圖所示，從中選取最小值則為醫院建立的地址，從結果中可以看到社區27適合建立醫院。5 設計體會 這次課程設計給了我一個很好的機會去鍛煉運用所學知識去解決實際問題的能力。在學習了數據結構之后，對書上的算法的了解也僅僅停留在理論階段，但是一但需要用它解決實際問題的時候，問題常常接踵而至。首先感到棘手的就是將偽代碼轉化為可以執行的C代碼，特別是涉及到指針與函數之間參數傳遞的算法，必須將C