ImageVerifierCode 换一换
格式:DOCX , 页数:18 ,大小:120.15KB ,
资源ID:17389168      下载积分:3 金币
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

加入VIP,免费下载
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.bingdoc.com/d-17389168.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录   QQ登录  

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(基于floyd算法的医院选址实现.docx)为本站会员(b****2)主动上传,冰点文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知冰点文库(发送邮件至service@bingdoc.com或直接QQ联系客服),我们立即给予删除!

基于floyd算法的医院选址实现.docx

1、基于floyd算法的医院选址实现题 目: 基于Floyd算法的医院选址实现初始条件:理论:学习了数据结构课程,掌握了基本的数据结构和常用的算法;实践:计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)1、系统应具备的功能:(1)以邻接表为存储结构,建立n个结点的无向图;(2)用Floyd算法实现医院选址;(3)运行程序。2、数据结构设计;3、主要算法设计;4、编程及上机实现;5、撰写课程设计报告,包括:(1)设计题目;(2)摘要和关键字;(3)正文,包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、

2、设计体会等;(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+语言实现的全过程。关键词:最优化规划,

3、Flyod算法,医院选址,图论 0引言“数据结构”在计算机科学中是一门综合性的专业基础课。“数据结构”的研究不仅涉及到计算机硬件(特别是编码理论、存储装置和存取方法等)的研究范围,而且和计算机软件的研究有着更密切的关系,无论是编译程序还是操作系统,都涉及到数据元素在存储器中的分配问题。选址问题,是指为一个和几个服务设施在一定区域内选定它的位置,使某一指标达到最优解。这类问题,在规划建设中经常可以碰到,这里所谓的服务设施,可以是某些公共服务设施,如医院,消防站,物流中心等。也可以是生产服务设施,如仓库,转运站等等。可以认为,选址问题,就是把服务设施与服务对象,反映与统一的网络中,便于对问题进行研

4、究。尽管对选址的目标、要求有不同的评判标准,但是要求服务对象与服务设施之间易于沟通、易于达到,这是一个最基本的要求。本课程设计为基于Flyod算法的医院选址的实现,因此在把实际的问题简化为网络模型后,建立约束函数和最终目标函数,运用Flyod算法求出最优解。例如本次设计中医院选址关心的是如何找到一个社区建立医院使所有的社区到医院的路径之和最短,没有约束函数,目标函数则为。1需求分析1.1影响医院选址的因素1.1.1空间距离由于建医院的主要目的是收治病人,方便病人就医,使病人能在最短的时间内到达医院接受医治,因此院方必需调查所在地区各大社区到医院的空间距离,即病人到医院的直接距离。此距离受地理条

5、件,城市建筑等社会因素的限制。1.1.2时间距离必需考虑时间距离。这是病人从发病点到医院所需的时间(最好有80%的病人能在一个小时内到达医院),它受城市交通状况影响较大。在我国城市当前交通不发达的情况下,应十分重视时间距离。近年来,某大城市新建几所大医院的地址,虽然环境安静,地形理想,离社区的空间距离不太长,道路也较好,但唯独交通不便,时间距离长,开诊后病人少,并未减轻其他医院的压力,可谓目前城市新建医院选址的教训。1.1.3其他因素建院选址,除考虑上述要求外,还应做到:纳入城市规划,合理布局;环境安静,利于修养;地形理想,便于绿化;公用设施,尽量利用;地质合适,易防污染;运输方便,运费低廉等

6、到,这些条件也应综合考虑。2.数据结构设计为了使问题更加具体,更加形象,便于求解,设计了一张网络图如下:75655258457280452250302830186870508078404870324028303832301048562826325846505636385060406270851510252625048425235504050456040380356898622825202116171819131415121011976842543122524232922282730263132333435363738394041图中的每个节点表示一个社区,一共有42个社区,社区与社区之间的数字

7、为社区之间的距离。要求是要在这42个社区里面选择一个社区建立医院,使其余社区到医院的距离之和最短。2.1自定义结构体struct Graphint vexnum; long arcxM_vexnumM_arcnum;其中vexnum为图中的顶点数,在本图中它的值为43(0号单元为用),arcxM_vexnumM_arcnum用来表示任意两个节点之间的距离,初始化的时候把不同顶点间的距离都设为无穷大,相同顶点间的距离设为0。2.2结点距离矩阵的初始化与赋值for(i=1;iG.vexnum;i+)for(j=1;jG.vexnum;j+) if(i=j) G.arcxij=0;else G.ar

8、cxij=INFINITY; 在程序运行的时候再对它们赋值,对于上图对其上三角矩阵赋值为: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

9、.arcx814=36;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.arc

10、x1723=52; G.arcx1819=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.arcx3

11、235= 98; G.arcx3238=68; G.arcx3239=62;G.arcx3336=40;G.arcx3337=38; G.arcx3539=102; G.arcx3738=35; G.arcx4142=26;因为是无向图,所以VijVji ,得到图完整的邻接矩阵,语句如下:for(i=1;iG.vexnum;i+)for(j=1;ji;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;iG.vexnum;i+)for(j=1;jG.vexnum;j+) if(i=j) G.arcxij=0;else G.arcxij=INFINITY; 4.2任意两个顶点之间最短距离的计算计算任意两个顶点之间的最短距离的方法有很多,最基本的有迪杰斯特拉(Dijkstra)算法和弗洛伊德(Flyod)算法。相比之下,Flyod算法比Dijkstra算法更容易理解,算法在一次运算中可以求出任意两个顶点之间的距离,并且它们的时间复杂度都是o(n3)。

15、以下代码是整个程序中最重要的部分,它将求解出图的距离矩阵。for(v=1;vG.vexnum;v+)for(w=1;wG.vexnum;w+)Dvw=G.arcxvw;for(u=1;uG.vexnum;u+)Pvwu=FALSE;if(DvwINFINITY)Pvwu=TRUE;Pvww=TRUE;for(u=1;uG.vexnum;u+)for(v=1;vG.vexnum;v+)for(w=1;wG.vexnum;w+)if(Dvu+DuwDvw)Dvw=Dvu+Duw;for(i=1;iG.vexnum;i+)Pvwi=Pvui;4.3确定医院地址的算法得到图的距离矩阵后,要想从中得到医

16、院的地址。我们分析,医院选址的要求是使所有的顶点到医院的距离之和最短,既然已经求出了图的距离矩阵,那么把矩阵的没一行或者每一列进行相加,就得到所有顶点到该顶点的距离之和,重复此操作42次就会得到所以的顶点到每个顶点距离之和,然后从中选取最小值,该数对应的点则为医院的地址。for(v=1;vG.vexnum;v+)sumv=0;for(w=1;wG.vexnum;w+)sumv+=Dvw;temp=sum1;for(v=1;vG.vexnum;v+)if(sumvtemp)temp=sumv;node=v;4.4运行结果这是一个42*42的矩阵,即是图的距离矩阵,矩阵中的每一个元素对应的横纵结点

17、之间的最短距离。为了检查结果的正确与否,另外用优化软件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) 117.0000D1( N1, N11) 190.0000D1( N1, N12) 1

18、69.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.0000D1( N1, N25) 230.0000D1( N1, N26) 212.000

19、0D1( 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( N1, N39) 132.0000D1( N1, N40) 130.0000D1( N

20、1, N41) 208.0000D1( N1, N42) 234.0000把结果与C代码运行的结果做比较,可以发现结果是一致的。 sumi表示其他顶点到i点距离之和,如图所示,从中选取最小值则为医院建立的地址,从结果中可以看到社区27适合建立医院。5 设计体会 这次课程设计给了我一个很好的机会去锻炼运用所学知识去解决实际问题的能力。在学习了数据结构之后,对书上的算法的了解也仅仅停留在理论阶段,但是一但需要用它解决实际问题的时候,问题常常接踵而至。首先感到棘手的就是将伪代码转化为可以执行的C代码,特别是涉及到指针与函数之间参数传递的算法,必须将C语言教材中关于指针的知识弄懂,然后才能把伪代码中引

21、用参数转化为正确的代码。其次就是如何从整体中、全局中去看待问题,这时算法只是求解问题中的一个很关键的步骤,如何去正确处理它与整个算法和其他语句之间的关系,如何使其函数化,模块化,都是非常重要的,处理的好,可以降低时间复杂度。理论与实际是紧密相连的,这是我第二次运用它解决实际问题。上次在“五一”参加数学建模期间就运用过。当时我们小组做的题目是如何运输防洪物资满足地图上大大小小的防洪物资站的需求,那个题目里面有很多约束条件。不过首要摆在我们面前的就是如何确定点与点之间的最短距离,然后建立关于运费的约束函数。当时觉得应该有一中算法可以解决这方面的问题,就在数据结构书本上找到了这方面的内容,看懂后用优

22、化软件Lingo软件求解。6 结束语本次课程设计的目的是要运用Flyod算法确定医院的地址,其实质是要在一个无向网络中找出一点使其他各点到该点的距离之和最小。根据图论中关于最短距离的理论,很容易想到是运用Flyod算法求解任意两个顶点之间的最短距离,然后将这个距离矩阵的没横行或者纵列相加,得到的便是每个顶点到该顶点的距离之和,最后从中选取最小值,那么该最小值对应的顶点则为医院建立的地址。参考文献1 严蔚敏,吴伟民.数据结构M.北京:清华大学出版社,1997:186-1902 胡桔洲,Flyod最短路径算法在陪送中心选择中的应用J,湖南农业大学学报,2004.08:382-3843 毕亚军,王晓威.网络图中任意两点间最短路径问题的计算机实现J,科技资讯,2006.06:73-74

copyright@ 2008-2023 冰点文库 网站版权所有

经营许可证编号:鄂ICP备19020893号-2