1、 算法设计与分析课程设计算法设计与分析课程设计 题目：题目： 校园导航问题 文档：文档： 物联网工程 学 院 物联网工程 专 业 学 号 学生姓名 班 级 二一三年十二月 校园导航问题校园导航问题 一、一、问题描述与分析问题描述与分析 课程设计主要内容及要求： 设计你的学校的平面图,至少包括 10 个以上的场所,每两个场所 间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场 所的最佳路径(最短路径). 首先， 根据江南大学的主要场所设计江南大学的学校平面图如下 所示： 图 1：江南大学主要场所平面图 之后，需要进行算法的选择与分析，显然，这是一个主要涉及贪 婪算法的问题， 简单的描述
2、就是计算求解一个节点到其他所有节点的 最短路径的问题，通过查阅算法设计与分析的相关资料， 最终选择了 狄斯奎诺算法来设计解决这个问题。 二、二、设计概要设计概要 贪婪法的设计思想：贪婪法的设计思想： 在实际生活中，经常有这样一类问题：它有 n 个输入，它的解由 这 n 个输入中的一个子集组成， 但这个子集必须满足事先给定的某些 条件。有时，把这些条件称为约束条件，把满足约束条件的解称为问 题的可行解。满足约束条件的解可能不止一个，因此可行解也不是唯 一的。为了衡量可行解的优劣，事先给出一定的标准，这些标准通常 以函数的形式给出， 把这些函数称为目标函数。 使目标函数取极值 （极 大或极小）的可
3、行解，称为最优解。 贪婪法通常用来解决具有最大值或最小值的优化问题。 它犹如登 山一样，一步一步地向前推进，从某一个初始状态出发，根据当前局 部的而不是全局的最优决策， 以满足约束方程为条件、以使得目标函 数的值增加最快或最慢为准则， 选择一个能够最快地达到要求的输入 元素，以便尽快地构成问题的可行解。 在一般情况下， 贪婪法由一个迭代的循环组成， 在每一轮循环中， 通过少量的局部的计算，试图去寻求一个局部的最优解， 而不考虑将 来如何。因此，它是一步一步得建立问题的解的。每一步的工作都增 加了部分解的规模， 每一步的选择都极大地增长了它所希望实现的目 标函数。 因为每一步都是由少量的工作基于
4、少量的信息组成的， 因此 所产生的算法特别有效。适合于用贪婪法求解的问题，一般具有下面 两个重要性质， 即贪婪选择性质和最优子结构性质。所谓贪婪选择性 质，是指所求问题的全局最优解，可以通过一系列局部最优的选择来 达到。每进行一次选择，就得到一个局部的解，并把所求解的问题简 化为一个规模更小的类似子问题。所谓最优子结构，是指一个问题的 最优解中包含其子问题的最优解。 基于贪心算法的最短路径算法（基于贪心算法的最短路径算法（狄斯奎诺算法狄斯奎诺算法）具体如下：）具体如下： 最短路径算法关键先把已知最短路径顶点集(只有一个源点)和 未知的顶点分开， 然后依次把未知集合的顶点按照最短路径加入到已 知
5、结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入 完毕后回溯找到每个顶点的最短路径和权重。 算法把一个图（G）中的点划分成了若干部分： （1） ：原点（v） （2）：所有周边点（C） 另外有一个辅助集合 S， 从 v到 S 中的点的最短路径已经求得。 S 的 最初状态是空集。 这样就可以进一步划分图（G） ： （1） ：原点（v） ； （2） ：已求出 v 至其最短路径的周边点（S） ； （3） ：尚未求出 v 至其最短路径的周边点（Other=C-S） ； 算法的主体思想： A、找到 v - Other 所有路径中的的最短路径 vd = v - d（Other 的 一个元素） ；
6、B、找到 v - S - Other 所有路径中的的最短路径 vi = v - i（Other 的一个元素） ； C、比较 vd 和 vi 如果 vd = vi 则将 d 加入 S 且从 Other中删除，否 则将 i 加入 S 且从 Other中删除。 D、重复以上步骤直至 Other 为空集。 系统功能框图设计如下：系统功能框图设计如下： 图 2：系统功能框图 相关函数及函数名称的设计相关函数及函数名称的设计: : 1、邻接矩阵创建函数：CreateMGraph() 2、校园平面图展示函数：Map() 3、资料介绍函数：Info() 4、求最短路径函数：Dijkstra() 5、主菜单函数：Menu() 6、输出结果函数：Display() 7、主函数：main() 各函数之间的调用关系设计如下： 图 3:函数调用关系图 三、三、流程图及主要源程序流程图及主要源程序 主程序流程图如下所示：主程
