基于Floyd算法的医院选址实现

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