医院选址问题VIP免费

课程设计任务书2011—2012学年第1学期电子与信息工程系计算机科学与技术专业班级课程设计名称：数据结构课程设计设计题目：医院选址问题完成期限：自2012年1月2日至2012年1月6日共1周一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题

二、设计要求1

重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；2

按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩

凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；3

学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；4

认真编写课程设计报告

三、设计内容医院选址问题1

问题描述n个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄i到村庄j的道路长度

现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近

基本要求(1)建立模型，设计存储结构；(2)设计算法完成问题求解；(3)分析算法的时间复杂度

设计思想医院选址问题实际是求有向图中心点的问题

首先定义顶点的偏心度

设图G=（V，E），对任一顶点k，称E(k)=max{d(i,k)}（i∈V）为顶点k的偏心度

显然，偏心度最小的顶点即为图G的中心点

如图7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示

1123451253214顶点偏心度ab6b8d5e7(a)(b)图7带权有向图及各顶点的偏心度医院选址问题的算法用伪代码描述如下：1．对加权有向图，调用Floyd算法，求每对顶点间最短路径长度的矩阵；2．对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；3．具有最小偏心度的顶点即为所求

【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧