基于floyd算法的医院选址实现.docx
《基于floyd算法的医院选址实现.docx》由会员分享，可在线阅读，更多相关《基于floyd算法的医院选址实现.docx（18页珍藏版）》请在冰点文库上搜索。
基于floyd算法的医院选址实现
题目:
基于Floyd算法的医院选址实现
初始条件：
理论：
学习了《数据结构》课程，掌握了基本的数据结构和常用的算法；
实践：
计算机技术系实验室提供计算机及软件开发环境。
要求完成的主要任务:
（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1、系统应具备的功能：
（1）以邻接表为存储结构,建立n个结点的无向图；
（2）用Floyd算法实现医院选址；
（3）运行程序。
2、数据结构设计；
3、主要算法设计；
4、编程及上机实现；
5、撰写课程设计报告，包括：
（1）设计题目；
（2）摘要和关键字；
（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等；
（4）结束语；
（5）参考文献。
时间安排：
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算法，医院选址，图论
0．引言
“数据结构”在计算机科学中是一门综合性的专业基础课。
“数据结构”的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。
选址问题，是指为一个和几个服务设施在一定区域内选定它的位置，使某一指标达到最优解。
这类问题，在规划建设中经常可以碰到，这里所谓的服务设施，可以是某些公共服务设施，如医院，消防站，物流中心等。
也可以是生产服务设施，如仓库，转运站等等。
可以认为，选址问题，就是把服务设施与服务对象，反映与统一的网络中，便于对问题进行研究。
尽管对选址的目标、要求有不同的评判标准，但是要求服务对象与服务设施之间易于沟通、易于达到，这是一个最基本的要求。
本课程设计为基于Flyod算法的医院选址的实现，因此在把实际的问题简化为网络模型后，建立约束函数和最终目标函数，运用Flyod算法求出最优解。
例如本次设计中医院选址关心的是如何找到一个社区建立医院使所有的社区到医院的路径之和最短，没有约束函数,目标函数则为
。
1．需求分析
1.1影响医院选址的因素
1.1.1空间距离
由于建医院的主要目的是收治病人，方便病人就医，使病人能在最短的时间内到达医院接受医治，因此院方必需调查所在地区各大社区到医院的空间距离，即病人到医院的直接距离。
此距离受地理条件，城市建筑等社会因素的限制。
1.1.2时间距离
必需考虑时间距离。
这是病人从发病点到医院所需的时间（最好有80%的病人能在一个小时内到达医院），它受城市交通状况影响较大。
在我国城市当前交通不发达的情况下，应十分重视时间距离。
近年来，某大城市新建几所大医院的地址，虽然环境安静，地形理想，离社区的空间距离不太长，道路也较好，但唯独交通不便，时间距离长，开诊后病人少，并未减轻其他医院的压力，可谓目前城市新建医院选址的教训。
1.1.3其他因素
建院选址，除考虑上述要求外，还应做到：
纳入城市规划，合理布局；环境安静，利于修养；地形理想，便于绿化；公用设施，尽量利用；地质合适，易防污染；运输方便，运费低廉等到，这些条件也应综合考虑。
2.数据结构设计
为了使问题更加具体，更加形象，便于求解，设计了一张网络图如下：
75
65
52
58
45
72
80
45
22
50
30
28
30
18
68
70
50
80
78
40
48
70
32
40
28
30
38
32
30
10
48
56
28
26
32
58
46
50
56
36
38
50
60
40
62
70
85
15
102
52
62
50
48
42
52
35
50
40
50
45
60
40
380
35
68
98
62
28
25
20
21
16
17
18
19
13
14
15
12
10
11
9
7
6
8
42
5
4
3
1
2
25
24
23
29
22
28
27
30
26
31
32
33
34
35
36
37
38
39
40
41
图中的每个节点表示一个社区，一共有42个社区，社区与社区之间的数字为社区之间的距离。
要求是要在这42个社区里面选择一个社区建立医院，使其余社区到医院的距离之和最短。
2.1自定义结构体
structGraph
{
intvexnum;
longarcx[M_vexnum][M_arcnum];
};
其中vexnum为图中的顶点数，在本图中它的值为43（0号单元为用），arcx[M_vexnum][M_arcnum]用来表示任意两个节点之间的距离，初始化的时候把不同顶点间的距离都设为无穷大，相同顶点间的距离设为0。
2.2结点距离矩阵的初始化与赋值
for（i=1;ifor（j=1;j{
if（i==j）
G.arcx[i][j]=0;
else
G.arcx[i][j]=INFINITY;
}
在程序运行的时候再对它们赋值，对于上图对其上三角矩阵赋值为：
G.arcx[1][2]=40;G.arcx[1][33]=60;G.arcx[1][34]=45;
G.arcx[2][3]=35;G.arcx[2][7]=50;G.arcx[2][9]=62;
G.arcx[3][10]=42;G.arcx[3][36]=50;
G.arcx[4][5]=10;G.arcx[4][6]=30;G.arcx[4][29]=40;G.arcx[4][30]=70;
G.arcx[5][6]=28;G.arcx[5][39]=85;G.arcx[5][40]=38;
G.arcx[6][11]=32;G.arcx[6][40]=30;G.arcx[6][41]=48;
G.arcx[7][10]=48;G.arcx[7][27]=70;
G.arcx[8][14]=36;G.arcx[8][15]=38;G.arcx[8][28]=50;
G.arcx[9][27]=40;G.arcx[9][31]=52;G.arcx[9][40]=28;
G.arcx[10][12]=52;
G.arcx[11][15]=56;G.arcx[11][25]=40;G.arcx[11][27]=48;
G.arcx[12][13]=80;
G.arcx[13][20]=68;G.arcx[13][27]=50;
G.arcx[14][17]=56;G.arcx[14][23]=50;
G.arcx[15][18]=58;G.arcx[15][25]=46;G.arcx[15][42]=28;
G.arcx[16][18]=75;G.arcx[16][21]=58;G.arcx[16][23]=65;
G.arcx[17][23]=52;
G.arcx[18][19]=22;G.arcx[18][23]=45;G.arcx[18][25]=30;
G.arcx[19][22]=72;G.arcx[19][26]=28;
G.arcx[20][22]=80;G.arcx[20][24]=50;
G.arcx[21][22]=45;
G.arcx[24][26]=30;
G.arcx[25][26]=18;
G.arcx[26][27]=70;
G.arcx[27][40]=32;
G.arcx[28][29]=60;G.arcx[28][42]=32;
G.arcx[29][30]=62;
G.arcx[30][39]=15;
G.arcx[31][32]=50;
G.arcx[32][31]=50;G.arcx[32][34]=25;G.arcx[32][35]=98;G.arcx[32][38]=68;G.arcx[32][39]=62;
G.arcx[33][36]=40;G.arcx[33][37]=38;]
G.arcx[35][39]=102;
G.arcx[37][38]=35;
G.arcx[41][42]=26;
因为是无向图，所以Vij＝Vji，得到图完整的邻接矩阵，语句如下：
for（i=1;ifor（j=1;jG.arcx[i][j]=G.arcx[j][i];
3.算法设计
图论中的最短路径算法包括指定的顶点之间的最短路径算法和全部顶点间的最短路径算法。
前者可用于运输的合理化决策分析，一般用迪杰斯特拉（Dijkstra）算法实现,而后者很适合于选址合理的中心等,使总的路程最短,一般用弗洛伊德（Flyod）算法求解。
3.1算法的基本思想
全部顶点间最短路径算法具有代表性的是1962年有福劳德（Flyod）提出的算法。
它的主要思想是从代表任意2个顶点
到
的距离带权邻接矩阵开始，每次插入一个顶点
，然后将
到
间的已知最短路径于插入顶点
作为中间顶点（一条路径中始点外和终点外的其他顶点）时可能产生的
到
路径距离比较，取较小值以得到新的距离矩阵。
如此循环迭代下去，依次构造出n个矩阵D
（1）,D
（2）,D（3）…,D（n），当所有的顶点均作为任意2个顶点
到
中间顶点时得到的最后带权邻接矩阵D就反映了所以顶点对之间的最短距离信息，成为图G的距离矩阵。
最后对G中各行元素求和值并比较大小，决定单个或多个最佳的中心。
3.2Flyod算法构造距离矩阵的原理
对一个有n个顶点的图G，将顶点用n个整数（从1到n）进行编号。
把G的带权邻接矩阵W作为距离矩阵的初值，即D（0）＝（d（0）ij）n*n＝W。
第一步构造D
（1）＝（d
（1）ij）n*n，其中dij＝min｛d
（1）i1＋d
（1）1j｝是从
到
的允许到
作为中间点的路径中最短距离长度。
第二步构造D
（2）＝（d
（1）ij）n*n，其中dij＝min｛d
（2）ij，d
（2）i2＋d
（2）2j｝是从
到
的只许以
，
作为中间点的路径最短长度。
第n步构造D（n）＝（d（n）ij），其中dij＝min｛d（n）ij，d（n）in＋d（n）nj｝是从
到
的只允许以
，
，
，…，
作为中间点的所有路径中最短路的长度，即是从
到
中间可插入任何顶点的路径中最短路的长度，因此D即是距离矩阵。
4.程序实现
4.1图的初始化
for（i=1;ifor（j=1;j{
if（i==j）
G.arcx[i][j]=0;
else
G.arcx[i][j]=INFINITY;
}
4.2任意两个顶点之间最短距离的计算
计算任意两个顶点之间的最短距离的方法有很多，最基本的有迪杰斯特拉（Dijkstra）算法和弗洛伊德（Flyod）算法。
相比之下，Flyod算法比Dijkstra算法更容易理解，算法在一次运算中可以求出任意两个顶点之间的距离,并且它们的时间复杂度都是o（n3）。
以下代码是整个程序中最重要的部分，它将求解出图的距离矩阵。
for（v=1;vfor（w=1;w{
D[v][w]=G.arcx[v][w];
for（u=1;uP[v][w][u]=FALSE;
if（D[v][w]{P[v][w][u]=TRUE;P[v][w][w]=TRUE;}
}
for（u=1;ufor（v=1;vfor（w=1;wif（D[v][u]+D[u][w]{
D[v][w]=D[v][u]+D[u][w];
for（i=1;iP[v][w][i]=P[v][u][i];
}
4.3确定医院地址的算法
得到图的距离矩阵后，要想从中得到医院的地址。
我们分析，医院选址的要求是使所有的顶点到医院的距离之和最短，既然已经求出了图的距离矩阵，那么把矩阵的没一行或者每一列进行相加，就得到所有顶点到该顶点的距离之和，重复此操作42次就会得到所以的顶点到每个顶点距离之和，然后从中选取最小值，该数对应的点则为医院的地址。
for（v=1;v{
sum[v]=0;
for（w=1;w{
sum[v]+=D[v][w];
}
}
temp=sum[1];
for（v=1;vif（sum[v]{
temp=sum[v];
node=v;
}
4.4运行结果
这是一个42*42的矩阵,即是图的距离矩阵,矩阵中的每一个元素对应的横纵结点之间的最短距离。
为了检查结果的正确与否，另外用优化软件lingo对其进行建模，取其中结点1的数据，即所以结点到结点1的最短距离：
D1（N1,N1）0.000000
D1（N1,N2）40.00000
D1（N1,N3）75.00000
D1（N1,N4）178.0000
D1（N1,N5）168.0000
D1（N1,N6）160.0000
D1（N1,N7）90.00000
D1（N1,N8）284.0000
D1（N1,N9）102.0000
D1（N1,N10）117.0000
D1（N1,N11）190.0000
D1（N1,N12）169.0000
D1（N1,N13）192.0000
D1（N1,N14）320.0000
D1（N1,N15）246.0000
D1（N1,N16）335.0000
D1（N1,N17）357.0000
D1（N1,N18）260.0000
D1（N1,N19）240.0000
D1（N1,N20）260.0000
D1（N1,N21）357.0000
D1（N1,N22）312.0000
D1（N1,N23）305.0000
D1（N1,N24）242.0000
D1（N1,N25）230.0000
D1（N1,N26）212.0000
D1（N1,N27）142.0000
D1（N1,N28）266.0000
D1（N1,N29）209.0000
D1（N1,N30）147.0000
D1（N1,N31）120.0000
D1（N1,N32）70.00000
D1（N1,N33）60.00000
D1（N1,N34）45.00000
D1（N1,N35）168.0000
D1（N1,N36）100.0000
D1（N1,N37）98.00000
D1（N1,N38）133.0000
D1（N1,N39）132.0000
D1（N1,N40）130.0000
D1（N1,N41）208.0000
D1（N1,N42）234.0000
把结果与C代码运行的结果做比较，可以发现结果是一致的。
sum[i]表示其他顶点到i点距离之和，如图所示，从中选取最小值则为医院建立的地址，从结果中可以看到社区27适合建立医院。
。
5设计体会
这次课程设计给了我一个很好的机会去锻炼运用所学知识去解决实际问题的能力。
在学习了数据结构之后，对书上的算法的了解也仅仅停留在理论阶段，但是一但需要用它解决实际问题的时候，问题常常接踵而至。
首先感到棘手的就是将伪代码转化为可以执行的C代码，特别是涉及到指针与函数之间参数传递的算法，必须将C语言教材中关于指针的知识弄懂，然后才能把伪代码中引用参数转化为正确的代码。
其次就是如何从整体中、全局中去看待问题，这时算法只是求解问题中的一个很关键的步骤，如何去正确处理它与整个算法和其他语句之间的关系，如何使其函数化，模块化，都是非常重要的，处理的好，可以降低时间复杂度。
理论与实际是紧密相连的，这是我第二次运用它解决实际问题。
上次在“五一”参加数学建模期间就运用过。
当时我们小组做的题目是如何运输防洪物资满足地图上大大小小的防洪物资站的需求，那个题目里面有很多约束条件。
不过首要摆在我们面前的就是如何确定点与点之间的最短距离,然后建立关于运费的约束函数。
当时觉得应该有一中算法可以解决这方面的问题,就在数据结构书本上找到了这方面的内容，看懂后用优化软件Lingo软件求解。
6结束语
本次课程设计的目的是要运用Flyod算法确定医院的地址，其实质是要在一个无向网络中找出一点使其他各点到该点的距离之和最小。
根据图论中关于最短距离的理论，很容易想到是运用Flyod算法求解任意两个顶点之间的最短距离，然后将这个距离矩阵的没横行或者纵列相加，得到的便是每个顶点到该顶点的距离之和，最后从中选取最小值，那么该最小值对应的顶点则为医院建立的地址。
参考文献
[1]严蔚敏，吴伟民.数据结构[M].北京:
清华大学出版社,1997:
186-190
[2]胡桔洲,Flyod最短路径算法在陪送中心选择中的应用[J],湖南农业大学学报,2004.08：
382-384
[3]毕亚军，王晓威.网络图中任意两点间最短路径问题的计算机实现[J]，科技资讯，2006.06：
73-74
升级会员 