资源简介

教学设计
课程基本信息
学科 信息技术 年级 高三 学期 秋季
课题 搜索算法
教学目标
1. 理解广度优先搜索算法的基本思想和基本框架。 2. 熟练应用搜索算法求解一些实际问题。
教学内容
教学重点： 1. 理解广度优先搜索算法的基本思想。
2. 掌握广度优先搜索算法的算法框架。
教学难点： 1. 理解与体会搜索算法中的相关概念。
2. 熟练应用搜索算法求解一些实际问题。
教学过程
一、开门见山，直接引入 搜索的概念：搜索是计算机程序设计中一种最基本、最常用的算法。当面对一个程序设计问题时，如果能够我到数学类的方法，如递推法、构造法，或者类似贪心、动态规划求最优值的方法,那么对于该题而言,已经基本解决。如果没有找到行之有效的方法，搜索便成了一个经常性的选择。 搜索算法是直接基于计算机高速运算的特点而使用的计算机求解方法。它是从问题的初始状态出发,根据其中的约束条件，按照一定的策略，有序推进，不断深人，对于达到的所有目标状态(解空间)，一—验证，找到符合条件的解(可行解)，或者找出所有可行解中的最优解。按照推进的控制策略，搜索一般分为宽度优先搜索和深度优先搜索。 二、新知讲解 广度优先搜索的基本思想：它是从初始结点开始，应用产生式规则和控制策略生成第一层结点，同时检查目标结点是否在这些生成的结点中。若没有，再用产生式规则将所有第一层结点逐一拓展，得到第二层结点，并逐一检杳第二层结点是否包含目标结点。若没有，再用产生式规则拓展第二层结点。如此依次拓展,检查下去，直至发现目标结点为止。如果拓展完所有结点,都没有发现目标结点,则问题无解 在搜索的过程中，广度优先搜索对于结点是沿着深度的断层拓展的。如果要拓展第n+1层结点，必须先全部拓展完第n层结点。对于同一层结点来说,它们对于问题的解的价值是相同的。所以，这种搜索方法定能保证找到最短的解序列。也就是说，第一个我到的目标结点,一定是应用产生式规则最少的。因此，宽度优先搜素算法适合求最少步骤或者最短解序列这类最优解问题。 例题：小华从某起点到某目的地需要经过若干次公交转车（乘车不存在绕圈现象，但不保证可以到达目的地），显然换乘公交的方案可能不唯一。如图所示，小华从起点A到目的地H最少需要转车两次，公交线路为“A->D->G->H”。 基本框架： def bfs(): while head备注：教学设计应至少含教学目标、教学内容、教学过程等三个部分，如有其它内容，可自行补充增加。

展开更多......

收起↑