选修1 算法与程序设计《第六章 程序设计实践 6.2 数据库管理软件的开发 6.2.1 从程序设计到软件开发》优秀教案

选修1 算法与程序设计《第六章 程序设计实践 6.2 数据库管理软件的开发 6.2.1 从程序设计到软件开发》优秀教案

1、了解动态规划算法原理；

2、理解动态规划算法可以解决的试题类型

3、理解阶段、状态、状态转移；

4、简单应用；

教学重点：

阶段、状态、状态转移。

教学难点：

理解算法思想，学以致用。

教学过程与环节设计分析：

基本原理

1、多阶段最优化决策：即由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条最优的活动路线。

带权有向的多段图

基本概念

⑴状态（State）：表示事物的性质，是描述“动态规划”中的“单元”的量。亦是每一阶段求解过程的出发点。

⑵阶段（Stage）：阶段是一些性质相近，可以同时处理的状态集合，或者说，阶段只是标识那些处理方法相同、处理顺序无关的状态。

⑶决策（Decision）：每个阶段做出的某种选择性的行动，是程序所需要完成的选择。

⑷状态转移方程：是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态变化的方程，是“动态规划”的中心。设

fk(i)—k阶段状态i的最优权值，即初始状态至状态i的最优代价

fk+1(i)=min{xk(j)+u(i,j)}

基本原理

1、最优性原理

作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。

2、无后效性原则

给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。