算法第四章

1. 数学建模第四章 图论 part4.2最短路径问题-Dijkstra算法

1.Dijkstra算法介绍

算法特点：

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

算法的思路

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。 

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点， 

然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。 

然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

2、Dijkstra算法示例演示

我求下图，从顶点v1到其他各个顶点的最短路径.

首先第一步，我们先声明一个dis数组，该数组初始化的值为：

我们的顶点集T的初始化为：T={v1}

既然是求 v1顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后，dis[2]（下标从0开始）的值就已经从“估计值”变为了“确定值”，即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。 

为什么呢？因为目前离 v1顶点最近的是 v3顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.

OK，既然确定了一个顶点的最短路径，下面我们就要根据这个新入的顶点V3会有出度，发现以v3 为弧尾的有： < v3,v4 >,那么我们看看路径：v1–v3–v4的长度是否比v1–v4短，其实这个已经是很明显的了，因为dis[3]代表的就是v1–v4的长度为无穷大，而v1–v3–v4的长度为：10+50=60，所以更新dis[3]的值,得到如下结果： 

因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3]，通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛v1顶点到其余各个顶点的路程。

然后，我们又从除dis[2]和dis[0]外的其他值中寻找最小值，发现dis[4]的值最小，通过之前是解释的原理，可以知道v1到v5的最短距离就是dis[4]的值，然后，我们把v5加入到集合T中，然后，考虑v5的出度是否会影响我们的数组dis的值，v5有两条出度：< v5,v4>和 < v5,v6>,然后我们发现：v1–v5–v4的长度为：50，而dis[3]的值为60，所以我们要更新dis[3]的值.另外，v1-v5-v6的长度为：90，而dis[5]为100，所以我们需要更新dis[5]的值。更新后的dis数组如下图： 

然后，我们使用同样原理，分别确定了v6和v2的最短路径，最后dis的数组的值如下： 

因此，从图中，我们可以发现v1-v2的值为：∞，代表没有路径从v1到达v2。所以我们得到的最后的结果为：

2. 《算法分析与设计》课程讲什么内容

《算法分析与设计》课程是理论性与应用性并重的专业课程。本课程以算法设计策略为知识单元，系统地介绍计算机算法的设计方法和分析技巧。课程教学主要内容包括：第一章，算法概述；第二章，递归与分治策略；第三章，动态规划；第四章，贪心算法；第五章，回溯法；第六章，分支限界法。通过介绍经典以及实用算法让同学掌握算法设计的基本方法。结合实例分析，让同学深入理解算法设计的技巧，以及分析算法的能力。

3. 冒泡排序算法 [“排序算法设计”教学设计]

一、教材依据本节课是奥教版《算法与程序设计》(选修1)第四章《算法与程序实现》的第4节第1课时。二、设计思想【教学指导思想】：基于问题主导的教学模式。
【设计理念】：本节课采用基于问题主导的创新教学模式，指导学生在问题解决视野下去亲历算法分析与程序设计实践、理解算法思想、发现新问题，从而全面提升学生的能力。
【教材分析】：排序算法是程序设计的基本算法，主要要求学生理解选择排序算法，选择排序算法的特点，进一步分析排序算法时间和空间效率。
【学情分析】：高二年级的学生在高一阶段袜亩山的必修教材中已经学习了编制程序解决问题，他们已经具有较强的逻辑思维能力和分析问题的能力，只要讲清楚算法，本节课的内容对学生来说应该容易掌握。
三、教学目标
【知识目标】：理解选择排序算法思想，学会使用选择排序算法思想解决问题。
【能力目标】：通过学习选择排序算法，提高学生分析与解决问题的能力。
【情感态度与价值观】：通过上机完成“大型国际运动会上的国家排序问题"VB程序设计，体验编程快乐、感受成功的喜悦与程序的魅力。
四、教学重点
选择排序算法的基本思想及相关的程序实现。
五、教学难点
如何使用选择排序算法解决实际的问题。
六、教学准备
1.用PowerPoint 2003制作的课件。
2.从网上下载选择排序的动画演示文件。
七、教学过程
1.引入新课：(以一些现实生活的实际问题开始，启发同学们去思考)
教师：同学们每次的考试成绩我们会以Excel表格的形式公布给大家，同学们想想计算机是如何在瞬间进行分数排序的呢?
学生想。
2.启发思考，分析选择排序算法及程序实现。
教师：好，今天我们就来学习选择排序算法。
开始新课学习：
教师：现在我们一起看看人工是如何进行数据的排序的，老师给出8位同学的分数，同学们把它们由小到大地排成顺序。数据分别是：86.5，77.5，87，68.9，89.6，77.2，79.7，71.1。同学们想想笫一个位置应该放哪个数?
学生：放最小的。
教师：好，那么，我们是不是只需要将最小的数68.9与在第一个位置的数86.5进行交换呢?
学生：是。
教师：同学们再想一下第二个位置是不是应该放置的是除了第一个以外的数中最小的呢?
学生：是。
教师：那么第N-1个位置应该放什么呢?
学生：应该放置告中的是除了前N-2个以外的数中最小的。
教师：老师是不是可以总结我们刚才的算法，所谓选择排序，就是给数组的N-1个位置选择合适的数据，而每次是选择第i个位置的数据到最后一个位置(第Ⅳ个位置)的数据的最小值，然后将找到的最小数据与第i个位置上的数据交换?
学生：是的。
教师：下面我用一个动画演示刚才的算法，请同学们看大屏幕。
现在我们只需要将刚才的算法用VB语言表达出来，就是选择排序的程序，那么我们需要解决三个问题：
(1)给数组的N-1个位置选择合适的数据?这个问题显然我们可以用一个循环结构来完成：For i=l【o
N-1Next i
(2)如何寻找第i个位置的数据到最后一个位置(第Ⅳ个位置)的数据的最小值?
这个问题也就是在数组中的极值(最大值或最小值)的问题。其实我们只关心最小值数据的位置，用变量M记录其位置。
于是我们很容易写出选择排序的程序。
3.调试程序：
教师：同学们想不想看一下运行结果呢?
学生：想(很耐橘强烈)。
教师：运行程序后，输入测试数据，可得排序后的输出结果在窗体上。
4.课堂实践练习与知识拓宽：
(1)完成课本127页的国家名排序问题。
【设计意图】：使学生看到选择排序不仅可以对数字排序，也可以对字符串排序，同时也能达到对选择排序的应用练习。
(2)明明的随机数(题目描述发送到学生机的桌面)
【设计意图】：这个问题是很现实的例子，学生对这个问题很感兴趣，激发他们探索的欲望，要求学习优秀的学生必须完成，我想通过这个问题，一方面提升学生学习的积极性；另一方面再通过这个实际问题的解决，实现本节课的知识目标。
【学习评价】：教师随机让个别学生讲解练习题的算法、演示其所编程序，师生共同进行点评。
【课堂小结】：
(1)什么是选择排序算法?
(2)选择排序算法的实质及时间和空间效率。
(3)选择排序算法的优点、缺点。
八、教学反思
通过本节课的 教学设计 ，我认识到信息技术教学的关键是要调动学生的积极性，算法与程序设计这部分知识如果课堂教学设计不当，就会让学生觉得很枯燥，所以我将抽象的问题通俗化，复杂的问题分解成几个小问题来解决，这样学生就很容易接受，再加上所举的例子都是学生身边的实际事例，使学生很想知道问题的答案，从而极大地调动了学生的积极性。
(作者单位陕西省成阳市礼泉县第一中学)

4. 算法分析与设计这门课程第四章贪心算法的知识点有哪些

算法分析与设计这门课第四章贪心算法的知识点包含章节导引,第一节活动安排问题,第二节贪心算法基本要素,第三节最优装载,第四节单源最短路径,第五节多机调度问题,课后练习,。