当前课程知识点:计算思维导论 >  第七章 问题求解 >  7.13 算法策略之动态规划 >  图文教学

返回《计算思维导论》慕课在线视频课程列表

图文教学资料文件与下载

图文教学

多阶段决策过程,是指这样一类的决策问题:由问题的特性,可将过程按时间、空间等标志分为若干个互相联系又相互区别的阶段,在它的每一个阶段都需要做出决策,从而使整个过程达到最好的效果。

(1)什么是动态规划?

20世纪50年代,美国数学家Bellman在研究多阶段决策过程的优化问题时,提出了著名的最优化原理。这种优化理论,把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,从而创立了解决这类过程优化问题的新方法——动态规划。

(2)动态规划的特点

◇ 决策者需要作出时间上有先后之别的多次决策。

◇ 前一次决策的选择将直接影响到后一次决策,后一次决策的状态取决于前一次决策的结果。

◇ 决策者关心的是多次决策的最终结果,而不是各决策的即时结果。

(3)基本概念

◇阶段:把一个复杂的决策问题按时间或空间特征分解为若干个相互联系的阶段,以便顺序求解。一般用 k 表示。阶段是对整个过程的自然划分。

◇状态:每个阶段有若干个状态,表示某一个阶段决策面临的条件或所处的位置。一般用 s 表示。

◇决策:就是关于状态的选择,是决策者从给定阶段状态触发对下一阶段状态作出的选择。一般用Xk=XK(SK)表示。表示k阶段,状态Sk时的决策。

◇状态转移方程:一个状态到另一个状态的转移过程由状态转移过程描述。大多数情况下可以用数学公式表达。

◇ 指标函数:分为阶段函数和过程函数(目标函数)两种。它是全过程或子过程或各阶段上确定数量的函数。如费用、成本、距离、利润、时间等。

◇ 最优解:对指标函数求解,称为最优解。

(4)动态规划步骤

划分阶段à选择状态à确定决策à写出状态转移方程à确定决策变量取值范围(包括边界条件)à写出指标函数递推公式à逆序求解。

(5)适用条件

◇最优化子结构

最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,

对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简言之,一个最优化

策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

◇无后效性

将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态

无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历

史的一个完整总结。这就是无后效性。

◇重叠子问题

子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。

(6)动态规划的优缺点

优点:解决复杂问题、找到全局最优解、可以得到一组解。

缺点:依赖于经验和技巧、无后效性局限大、维数灾难。


7)动态规划算法框架

input 阶段变量,状态变量,决策变量,状态数组

for i = 阶段最大值 downto 1 step -1        // 倒推每一个阶段

   for j = 状态最小值 to 状态最大值          // 枚举阶段i的每一个状态

       for k = 决策最小值 to 决策最大值     // 枚举 i 阶段 j 状态下的每一种决策

            目标函数

output 最优方案

示例:最短路径问题

解析:

(1)阶段变量:按空间划分阶段。分为6个阶段。K=1, … , 6

(2)状态变量:可用城市编号作为状态变量。S1={A},S2={B1,B2},S3={C1,C2,C3,C4},S4={D1,D2,D3},S5={E1,E2,E3},S6={F1,F2},S7={G}。

(3)决策变量:也可用城市编号作为决策变量。X1(S1)=A,X2(S2)=B1,X3(S3)=C2,X4(S4)=D1,X5(S5)=E2,X6(S6)=F2,X7(S7)=G

(4)写出状态转移方程:Sk+1=Xk

(5)指标函数

阶段函数:Vk=( Sk,XK )

目标函数:fk(Sk)=min{Vk+fk+1(Sk+1)}

(6)逆序求解:从k=6开始计算。

K=6

    f6(F1)=4,f6(F2)=3

K=5

    f5(E1)=min{3+f6(F1)=7*,5+f6(F2)=8}=7

    f5(E2)=min{5+f6(F1)=9,2+f6(F2)=5*}=5

    f5(E3)=min{6+f6(F1)=10,6+f6(F2)=9*}=9

K=4

    f4(D1)=min{2+f5(E1)=9,2+f5(E2)=7*}=7

    f4(D2)=min{1+f5(E2)=6*,2+f5(E3)=11}=6

    f4(D3)=min{3+f5(E2)=8*,3+f5(E3)=12}=8

K=3

    f3(C1)=min{6+f4(D1)=13*,8+f4(D2)=14}=13

    f3(C2)=min{3+f4(D1)=10*,5+f4(D2)=11}=10

    f3(C3)=min{3+f4(D2)=9*,3+f4(D3)=11}=9

f3(C4)=min{8+f4(D2)=14,4+f4(D3)=12*}=12

K=2

    f2(B1)=min{1+f3(C1)=14,3+f3(C2)=13*,

               6+f3(C3)=15}=13

    f2(B2)=min{8+f3(C2)=18,7+f3(C3)=16*,

               6+f3(C4)=18}=16

K=1

    f1(A)=min{5+f2(B1)=18*,3+f2(B2)=19}=18

故,最短路径为:à B1 à C2 à D1 à E2 à F2 à G


下一节:什么是动态规划?

返回《计算思维导论》慕课在线视频列表

计算思维导论课程列表:

第一章 计算思维概述

-1.1 计算与计算思维1

--计算与计算思维1

--延伸学习:计算无所不在

--延伸学习:智能家居(计算无所不在)

--延伸学习:曲道奎谈机器人

--延伸学习:局座召忠谈AI

--图文教学

--VARK 学习风格调查表

--请你用计算思维的本质解决下列问题

--1-1 巩固练习--作业

-1.2 计算与计算思维2

--计算与计算思维2

--延伸学习:周以真2014教育峰会讲话

--图文教学

--计算思维对你的学习、从事的学科、专业有价值吗?

--1-2 巩固练习--作业

-1.3 计算工具与计算机

--计算工具与计算机

--延伸学习:帕斯卡加法器

--延伸学习:手摇式差分机

--延伸学习:神威超算计算机1

--延伸学习:神威超算计算机2

--延伸学习:局座召忠谈超算

--图文教学

--什么是摩尔定律?

--1-3 巩固练习--作业

-实验1-1 初识计算思维

--周以真2012教育峰会讲话

--计算机发展简史

--这才是大学

--实验1-1 初识计算思维

-本章小结

--知识点回顾

--习题与解析

--章节自测--作业

第二章 计算基础

-2.1 初识二进制

--初识二进制

--图文教学

--计算机为什么采用二进制?

--2-1 巩固练习--作业

-2.2 二进制的运算

--二进制的运算

--图文教学

--二进制的进位原则和借位原则是什么?

--2-2 巩固练习--作业

-2.3 数制转换

--数制转换

--延伸学习:李永乐老师讲老鼠吃药与二进制

--延伸学习:李永乐老师讲加法器

--常见进制

--图文教学

--数制转换口诀

--2-3 巩固练习--作业

-2.4 数的表示

--数的表示

--图文教学

--负数补码问题

--2-4 巩固练习--作业

-2.5 字符编码

--字符编码

--图文教学

--汉字编码问题

--2-5 巩固练习--作业

-2.6 声音图像编码

--声音图像编码

--延伸学习:李永乐老师讲RGB三原色

--延伸学习:小趣闻

--图文教学

--矢量图和位图有什么区别?

--2-6 巩固练习--作业

-本章小结

--知识点回顾

--习题与解析

--本章测验--作业

第三章 计算平台

-3.1 计算机系统构成

--计算机系统构成

--图文教学

--冯诺依曼原理的基本思想是什么?

--3-1 巩固练习--作业

-3.2 主板

--主板

--延伸学习:华硕游戏主板

--图文教学

--主板的作用

--3-2 巩固练习--作业

-3.3 接口与总线

--接口与总线

--图文教学

--总线和接口的区别

--3-3 巩固练习--作业

-3.4 CPU

--CPU

--李永乐老师讲“中国芯”

--延伸学习:局座召忠谈芯片-01

--延伸学习:局座召忠谈芯片-02

--延伸学习:局座召忠谈芯片-03

--延伸学习:从沙子到CPU的制造过程告诉你造芯片到底有多难

--图文教学

--什么是超频?如何来进行超频?

--什么是主频?

--3-4 巩固练习--作业

-3.5 内存

--内存

--图文教学

--主流内存类型

--3-5 巩固练习--作业

-3.6 外存

--外存

--图文教学

--硬盘类型

--3-6 巩固练习--作业

-3.7 输入输出设备

--输入输出设备

--延伸学习:极光尔沃3D打印机

--延伸学习:卢秉恒院士谈走进神奇的3D打印世界

--延伸学习:李永乐老师讲传感器与鼠标

--图文教学

--微机故障检测

--I/O设备

--3-7 巩固练习--作业

-3.8 计算机工作原理

--计算机工作原理

--延伸学习:计算机工作原理

--延伸学习:计算机工作原理

--延伸学习:微机维护专题之预防性维护

--延伸学习:微机维护专题之故障排除

--延伸学习:微机维护专题之PC常见问题

--图文教学

--人类与计算机

--3-8 巩固练习--作业

-3.9 操作系统1

--操作系统之处理机功能

--延伸学习:操作系统革命

--图文教学

--虚拟内存?

--3-9 巩固练习--作业

-3.10 操作系统2

--操作系统之其他功能

--延伸学习:Windows发展历史

--图文教学

--操作系统

--3-10 巩固练习--作业

-实验3-1 计算机原理与硬件组装

--延伸学习:微机组装

--延伸学习:计算机拆解

--上机实验3-1:计算机工作原理与硬件组装

-本章小结

--知识点回顾

--习题与解析

--章节自测--作业

第四章 网络技术与数据共享

-4.1 初识网络

--初识网络

--延伸学习:邬贺铨院士谈互联网改变了我们什么?

--延伸学习:美国分分钟让中国断网?

--图文教学

--互联网改变了我们什么?

--4.1 巩固练习--作业

-4.2 网络分类

--网络分类

--延伸学习:李永乐老师讲GPS与手机定位

--延伸学习:什么是VPN?

--图文教学

--校园网

--4.2 巩固练习--作业

-4.3 网络体系结构

--网络体系结构

--图文教学

--TCP/IP协议和OSI协议的异同点

--4.3 巩固练习--作业

-实验4-1:简单网络布线

--实操:简单网络布线 - 1

--实操:简单网络布线 - 2

--实操:简单网络布线 - 3

-4.4 网络设备

--网络设备

--延伸学习:网线制作

--图文教学

--路由器的作用是什么?

--4.4 巩固练习--作业

-实验4-2:将计算机添加到现有网络中

--实操:将计算机添加到现有网络中 - 1

--实操:将计算机添加到现有网络中 - 2

--实操:将计算机添加到现有网络中 - 3

-4.5 局域网搭建

--局域网搭建

--延伸学习:无线局域网的搭建

--延伸学习:共享文件夹设置

--图文教学

--有线局域网和无线局域网

--4.5 巩固练习--作业

-实验4-3 无线路由器连接与设置

--实操:无线路由器连接与设置 - 1

--实操:无线路由器连接与设置 - 2

--实操:无线路由器连接与设置 - 3

-4.6 IP与域名系统

--IP与域名系统

--延伸学习:IPV4与IPV6

--延伸学习:网络 CLI 命令

--图文教学

--一台电脑可以同时有两个IP吗,怎样设置?

--4.6 巩固练习--作业

-实验4-4:测试无线连接

--实操:测试无线连接

-4.7 划分子网

--划分子网

--图文教学

--子网掩码

--4.7 巩固练习--作业

-4.8 Internet 服务

--Internet 服务

--延伸学习:吴建平院士谈中国互联网的新时代

--延伸学习:苏恒谈5D

--工信部部长谈5G

--延伸学习:局座召忠谈华为与5G

--延伸学习:互联网+

--图文教学

--您最常用的Web服务是什么?

--4.8 巩固练习--作业

-4.9 数字公民与网络安全

--数字公民与网络安全

--延伸学习:李永乐老师谈数字签名

--延伸学习:李永乐老师讲RSA加密算法

--延伸学习:Dos攻击

--延伸学习:DDos攻击

--延伸学习:云计算与数据中心

--延伸学习:网络维护专题

--图文教学

--数字签名

--4.9 巩固练习--作业

-本章小结

--知识点回顾

--习题与解析

--章节自测--作业

第五章 数据库技术与数据管理

-5.1 数据库基本概念

--数据库基本概念

--图文教学

--细数你身边的数据库系统

--5.1 巩固练习--作业

-5.2 数据库的设计方法

--数据库的设计方法1

--数据库的设计方法2

--数据库的设计方法3

--图文教学

--数据库的设计步骤

--5.2 巩固练习--作业

-5.3 数据库的规范化设计1

--数据库的规范化设计(1)

--数据库规范化设计(2)

--图文教学

--为什么要规范化数据库设计?如果不规范化设计会有什么问题?

--5.3 巩固练习--作业

-5.4 数据库的规范化设计2

--数据库规范化设计(3)

--数据库规范化设计(4)

--图文教学

--规范化设计数据库

--5.4 巩固练习--作业

-5.5 ACCESS数据库的创建与查询

--ACCESS数据库的创建与查询

--图文教学

--主键与外键

--5.5 巩固练习--作业

-5.6 关系代数理论

--关系代数理论

--延伸学习:浪漫的爱情故事

--图文教学

--为什么关系代数是一种抽象的查询语言?

--5.6 巩固练习--作业

-5.7 SQL语句查询

--SQL语句查询

--图文教学

--简述SQL语句的特点

--5.7 巩固练习--作业

-实验5-1:数据库设计与实现(PBL直播课)

--PBL直播课:数据库设计与实现

--延伸学习:王小云教授讲密码学与系统安全

--延伸学习:悲观锁和乐观锁

-本章小结

--知识点回顾

--习题与解析

--章节自测--作业

第六章 逻辑思维

-6.1 逻辑思维及其训练方法

--逻辑思维及其训练方法

--延伸学习:逻辑训练之李永乐老师讲皇帝新装

--延伸学习:逻辑训练之李永乐老师讲三姬分金

--图文教学

--白马非马论

--6-1 巩固练习--作业

-6.2 命题及命题判断

--命题及命题判断

--延伸学习:什么是悖论?

--延伸学习:十大悖论

--图文教学

--命题判断条件

--6.2 巩固练习--作业

-6.3 命题符号化

--命题符号化

--延伸学习:WORD文档中逻辑符号的录入

--图文教学

--蕴含运算符

--6-3 巩固练习--作业

-6.4 布尔代数与真值表

--布尔代数与真值表

--图文教学

--构造真值表

--6-4 巩固练习--作业

-6.5 命题演算和逻辑推理

--命题演算和逻辑推理

--图文教学

--永真式和永假式

--6-5 巩固练习--作业

-实验6-1:用真值表进行逻辑推理(PBL录屏课)

--PBL录屏课:用真值表进行逻辑推理

-本章小结

--知识点回顾

--习题与解析

--章节自测--作业

第七章 问题求解

-7.1 什么是问题求解

--什么是问题求解

--图文教学

--传统思维模式与计算思维模式

--7-1 巩固练习--作业

-7.2 算法与算法描述

--算法与算法描述

--延伸学习:算法接管世界

--图文教学

--算法描述方法

--7-2 巩固练习--作业

-7.3 顺序结构设计

--顺序结构设计

--图文教学

--温度转换问题

--7-3 巩固练习--作业

-7.4 选择结构设计

--选择结构设计

--图文教学

--细数一下我们身边的选择

--7-4 巩固练习--作业

-7.5 循环结构设计

--循环结构设计

--图文教学

--细数一下我们身边的循环

--7-5 巩固练习--作业

-7.6 算法策略基础之数组

--算法策略基础之数组

--图文教学

--为什么要引入数组?

--7.6 巩固练习--作业

-7.7 算法策略基础之函数

--算法策略基础之函数

--图文教学

--用户自定义函数

--7.7 巩固练习--作业

-实验7-1:Raptor的基本操作(PBL录屏课)

--PBL录屏课:Raptor软件基本操作

--延伸学习:李永乐老师讲鸡兔同笼

--延伸学习:李永乐老师讲闰年

-7.8 算法策略之枚举法

--算法策略之枚举法

--图文教学

--细数一下我们身边的枚举?

--7-8 巩固练习--作业

-7.9 算法策略之递归法

--算法策略之递归法

--图文教学

--德罗斯特效应

--7.9 巩固练习--作业

-7.10 算法策略之递推法

--算法策略之递推法

--延伸学习:斐波那契数列

--图文教学

--举例说明,如何由递推法推导出通项公式

--7-10 巩固练习--作业

-7.11 算法策略之迭代法

--算法策略之迭代法

--延伸学习:辗转相除法是什么鬼?

--图文教学

--细数生活中的迭代现象

--7-11 巩固练习--作业

-实验7-2:算法设计与分析(PBL直播课)

--PBL直播课:算法设计与分析

-7.12 算法策略之分治法

--算法策略之分治法

--图文教学

--分治法思想

--7-12 巩固练习--作业

-7.13 算法策略之动态规划

--算法策略之动态规划

--延伸学习:什么是动态规划?

--图文教学

--什么是动态规划?

--7-13 巩固练习--作业

-7.14 算法策略之贪心算法

--算法策略之贪心算法

--图文教学

--贪心策略

--7.14 巩固练习--作业

-7.15 算法策略之回溯法

--算法策略之回溯法

--图文教学

--回溯现象

--7-15 巩固练习--作业

-7.16 算法策略之查找算法

--算法策略之查找算法

--图文教学

--二分查找方法的先决条件是什么?

--7-16 巩固练习--作业

-7.17 算法策略之排序算法

--算法策略之排序算法

--延伸学习:舞动的排序算法(冒泡法)

--图文教学

--冒泡排序

--7-17 巩固练习--作业

-本章小结

--知识点回顾

--习题与解析

--章节自测--作业

第八章 数据分析与数据挖掘

-8.1 数据挖掘概述

--数据挖掘概述

--延伸学习:梅宏院士谈大数据时代

--延伸学习:十个有趣的“大数据”经典数据挖掘案例

--图文教学

--数据挖掘案例

--8-1 巩固练习--作业

-8.2 数据采集

--数据采集

--图文教学

--数据采集

--8-2 巩固练习--作业

-8.3 数据探索之数据质量分析

--数据探索之数据质量分析

--图文教学

--异常值处理

--8-3 巩固练习--作业

-8.4 数据探索之数据特征分析

--数据探索之数据特征分析

--图文教学

--帕累托法则

--8-4 巩固练习--作业

-8.5 数据特征分析之分布分析

--数据特征分析之分布分析

--图文教学

--分组方法

--8-5 巩固练习--作业

-8.6 数据特征分析之统计分析

--数据特征分析之统计分析

--图文教程

--加权平均数

--8-6 巩固练习--作业

-8.7 数据特征分析之统计分析(续)

--数据特征分析之统计分析(续)

--图文教学

--无量纲数

--8-7 巩固练习--作业

-8.8 数据预处理

--数据预处理

--图文教学

--数据预处理

--8-8 巩固练习--作业

-8.9 数据挖掘之分类

--数据挖掘之分类

--延伸学习:李永乐老师讲概率与三门问题

--李永乐老师讲贝叶斯概率与酒鬼问题

--图文教学

--加法原理和乘法原理

--8-9 巩固练习--作业

-8.10 数据挖掘之预测

--数据挖掘之预测

--图文教学

--分类与预测

--8-10 巩固练习--作业

-8.11 数据挖掘之聚类分析

--数据挖掘之聚类分析

--图文教学

--聚类和分类

--8-11 巩固练习--作业

-8.12 数据挖掘之关联规则

--数据挖掘之关联规则

--图文教学

--智能推荐系统

--8-12 巩固练习--作业

-本章小结

--知识点回顾

--习题与解析

--章节自测--作业

期中考试(1-4章)

-期中考试(1-4章)

期末考试(5-8章)

-期末考试(5-8章)

图文教学笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。