1、 计算机科学与技术计算机科学与技术专业课程设计任务书专业课程设计任务书 学生姓名学生姓名 专业班级专业班级 学号学号 题题 目目 学校超市选址问题 课题性质课题性质 工程设计 课题来源课题来源 自拟课题 指导教师指导教师 同组姓名同组姓名 无 主要内容主要内容 对于某一学校超市，其他各单位到其的距离不同， 同时各单位人员去超市的频度也不同。 请为超市选址，要求实现总体最优。 任务要求任务要求 1.实现公司到超市距离，频率最优。 2. 确定超市位置，要求实现总体最优。 参考文献参考文献 C 程序设计第三版 谭浩强 著 清华大学出版社 数据结构 （C 语言版） 严蔚敏 著 清华大学出版社 数据结构
2、与算法赵文静 祁飞等编著 科学出版社 审查意见审查意见 指导教师签字： 教研室主任签字： 1 1 1 需求分析需求分析 核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少) 数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度) 存储结构: typedef struct string vexsMAX_VERTEX_SIZE; int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE; int vexnum;/ ,arcnum; MGraph; 核心算法: Floyd 算法(弗洛伊德算法-每一对顶点之间的最短路径) 输入数据: 各单位名称，距离，频度，单位
3、个数 输出数据: 所选单位名称 总体思路: 如果超市是要选在某个单位，那么先用 floyd 算法得出各顶点 间的最短距离/最小权值。 假设顶点个数有 n 个，那么就得到 n*n 的一张表格，arcs(i,j)表示 i 单位到 j 单位的最短距离/最小权值 , 这张表格中和最小的那一行(假设为第 t 行)，那 么超市选在 t 单位处就是最优解。 2 2 运行环境运行环境 Visual Stdio C+6.0 Windows Vista/2003/XP 3 3 概要设计概要设计 Floyd 算法利用动态规划思想，通过把问题分解为子问题来解决任意两点见 的最短路径问题。设 G=(V, E, w)是一
4、个带权有向图，其边 V=v1, v2, , vn。 对于 kn，考虑其结点 V 的一个子集。对于 V 中任何两个结点 vi、vj，考虑从 vi 到 vj 的中间结点都在 vk 中的所有路径，设是其中最短的，并设的路径长度 为。如果结点 vk 不在从 vi 到 vj 的最短路径上，则；反之则可以把分为两段， 其中一段从 vi 到 vk，另一段从 vk 到 vj，这样便得到表达式。上述讨论可以归 2 纳为如下递归式： 原问题转化为对每个 i 和 j 求，或者说求矩阵 流程图 4 4 详细设计详细设计 第一步，让所有路径加上中间顶点 1，取 Aij与 Ai1+A1j中较 小的值作 Aij的新值，完成后得到 A(1),如此进行下去，当第 k 步完成后，A 开始 Main（） 输入基本信息 建立邻接矩阵的存储结构 GreatMgraph（Gh） Floyd 算法 Aij=INF,i!=j 输出 i-j的路
