运筹说 第70期 | 算法:动态规划一
本期我们进行运筹学之动态规划算法的讲解,我们将对动态规划的基础知识进行一个简单的回顾,并介绍求解动态规划问题的MATLAB、Python和C 相关代码,以帮助大家利用工具快速求解动态规划问题,做到事半功倍。由于篇幅有限,小编接下来只展示部分代码,小伙伴们可以关注“运筹说”公众号→后台回复“算法介绍之动态规划(一)”获取完整代码。话不多说,我们一起来看看吧!
一、基础知识
1、多阶段决策的特点
(1)多阶段决策是与时间相关的;
(2)多阶段决策依赖于当前的状态;
(3)每一个时段都要作出决策;
(4)全部过程的决策是一个决策序列;
(5)本段决策的执行将影响下一阶段的决策;
(6)不仅要考虑本阶段最优,更要考虑全局最优。
2、动态规划的基本概念
使用动态规划方法解决多阶段决策问题,首先要将实际问题写成动态规划模型,此时要用到以下概念:
3、动态规划的基本思想与最优化原理
★ 最优化原理
最优化原理可以表述为:“一个过程的最优策略具有这样的性质:即无论初始状态及初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策应构成最优策略。”
(1)将多阶段决策过程划分阶段,恰当地选取状态变量、决策变量及定义最优指标函数,从而把问题化成一族同类型的子问题,然后逐个求解。
(2)求解时从边界条件开始,逆(或顺)过程行进方向,逐段递推寻优。在每一个子问题求解时,都要使用它前面已求出的子问题的最优结果,最后一个子问题的最优解,就是整个问题的最优解。
(3)动态规划方法是既把当前一段与未来各段分开,又把当前效益和未来效益结合起来考虑的一种最优化方法,因此每段的最优决策选取是从全局考虑的,与该段的最优选择一般是不同的。
式中opt可根据题意取min 或max,vk(sk,uk)为状态sk ,决策uk 时对应的第k 阶段的指标函数值。
★ 动态规划与静态规划的关系
4、动态规划模型的建立与求解
★ 使用动态规划的一般前提
(1)满足动态规划的最优化原理;
(2)满足动态规划的无后效性原则,即某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。
★ 动态规划模型的建立
★ 逆序解法与顺序解法
逆序解法:寻优的方向与多阶段决策过程的实际行进方向相反,从最后一段开始计算逐段前推,求得全过程的最优策略,称为逆序解法。
顺序解法:寻优方向与过程的行进方向相同,计算时从第一段开始逐段向后递推,计算后一阶段要用到前一阶段的求优结果,最后一段计算的结果就是全过程的最优结果。
顺序解法与逆序解法本质上并无区别,一般来说,当初始状态给定时可用逆序解法,当终止状态给定时可用顺序解法。若问题给定了一个初始状态与一个终止状态,则两种方法均可使用。
★ 逆序解法与顺序解法在建模时的区别
二、算法实现
1、例题介绍
如图所示,给定一个线路网络图,要从A地向F地铺设一条输油管道,各点间连线上的数字表示距离,问应选择什么路线,可使总距离最短?
2、平台实现
我们以上述例题为例,借助MATLAB、Python和C 介绍实现求解动态规划问题的相关代码。
(1)顺序解法
① Python
★ 代码展示
如图所示,在编写代码时用0替换A,用1替换B1,依次类推……用12替换F。
★ 代码调用
代码运行及最终结果展示如下,最短路长为17,最短路径为0→1→4→8→11→12,即对应例题中的A→B1→C2→D2→E2→F。
★ 平台介绍
C 代码的编写依靠Lightly平台来实现,Lightly支持C 工程项目开发,支持CMake,可选不同C 语言标准,语法高亮,智能提示,自动补全。它可以自动构建环境,实时同步资源到云端,支持多人协作,支持在线C 代码编辑、编译、运行。
输入项目名称,点击新建项目,开始编写代码。
★ 代码展示
如图所示,在编写代码时,用1替换A,用2替换B1,依次类推……用13替换F,逆序解法的代码同理。
★ 代码调用
代码运行及最终结果展示如下,最短路长为17,最短路径为1→2→5→9→12→13,即对应例题中的A→B1→C2→D2→E2→F。
(2)逆序解法
① MATLAB
★ 代码展示
★ 代码调用
代码运行及最终结果展示如下,最短路长为17,最短路径为1→2→5→9→12→13,即对应例题中的A→B1→C2→D2→E2→F。
② C
★ 代码展示
★ 代码调用
代码运行及最终结果展示如下,最短路长为17,最短路径为1→2→5→9→12→13,即对应例题中的A→B1→C2→D2→E2→F。
三、参考资料
【顺序解法Python实现】
【C 平台网址】
【顺序解法、逆序解法C 实现】
【逆序解法MATLAB实现】
本期的内容就介绍到这里,想要进一步了解运筹学,关注本公众号,快快学起来吧!
责编 | 刘文志
审核 | 徐小峰
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbbii
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13