【算法】动态规划 ⑧ ( 动态规划特点 )

9月前作者：韩曙亮分类：Toy博客阅读(45) 违法举报

这篇具有很好参考价值的文章主要介绍了【算法】动态规划 ⑧ ( 动态规划特点 )。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、动态规划特点

1、求解类型

求解类型 : 动态规划必须是求最值 , 可行性 , 方案数 , 三者之一 , 如果求其它内容 , 则不能使用动态规划算法 ;

求最值 : 最大值 , 最小值等 ;
- 大规模问题的结果由小规模问题的计算结果取最大值
- 大规模问题的结果由小规模问题的计算结果取最小值
可行性 : 是否可行 , 只要有一种方案可行即可 ;
- 大规模问题的结果由小规模问题的计算结果必须全部可行
- 大规模问题的结果由小规模问题的计算结果只要有一个可行即可
- 大规模问题的结果由小规模问题的计算结果没有可行结果
方案数 : 求一个总数 , 不求具体的方案 ;
- 大规模问题的结果由小规模问题的计算结果可行方案总数

2、方向性

方向性 : 动态规划必须有方向性 , 不能有反复 , 循环依赖 ;

如 : 骑士最短路径问题 , 骑士走 " 日 " 字形 , 可以走 8 个方向 , 在该问题中 , 我们将其行走方向固定在了右侧的四个方向 , 这样就不会出现循环依赖 ;

【算法】动态规划 ⑧ ( 动态规划特点 )

如 : 数字三角形 , 在三角形中 , 只能从上向下走 , 不能向上走 , 这样避免循环依赖 ;

【算法】动态规划 ⑧ ( 动态规划特点 )

3、动态规划状态选择

动态规划状态选择 : 在坐标型动态规划中 , 直接使用坐标的下标来标记相同位置的状态 ;

状态数组中存储的元素是 :

最大值 | 最小值
方案数
可行性

4、动态规划方程设计

动态规划方程设计 : 动态规划方程 , 最主要的作用是体现出下一步坐标状态与上一步坐标状态之间的联系 ;

也就是大规模问题解决方案 ( 下一步坐标状态 ) 与小规模问题解决方案 ( 上一步坐标状态 ) 之间的联系 ;文章来源地址https://www.toymoban.com/news/detail-403409.html

到了这里，关于【算法】动态规划 ⑧ ( 动态规划特点 )的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：

领支付宝红包赞助服务器费用

基于动态规划求解矩阵连乘问题

一、实验目的 1.掌握基于使用动态规划的方法求解矩阵连乘问题最优计算次序和最小计算次数问题的原理。 2.掌握求解矩阵链最小数乘次数动态规划函数的设计方法。 3.掌握基于动态规划方法求解矩阵连乘问题算法的具体步骤。 4.掌握运用动态规划的思想和方法设计算法解决

2023年04月16日
浏览(34)
运筹系列82：使用动态规划求解TSP问题

定义 c ( s , k ) c(s,k) c ( s , k ) 为当前在 k k k ，待访问点的集合 s s s ，最后返回城市0的最短路径，那么Bellman方程为： c ( s , k ) = min ⁡ i ∈ s { c ( s − { i } , i ) + d i , k } c(s,k)=min_{i in s}{c(s-{i},i)+d_{i,k}} c ( s , k ) = min i ∈ s { c ( s − { i } , i ) + d i , k } 为了使用方便，这里

2024年02月06日
浏览(38)
运筹系列87：julia求解随机动态规划问题入门

随机动态规划问题的特点是：有多个阶段，每个阶段的随机性互不相关，且有有限个实现值 (finite realizations) 具有马尔可夫性质，即每个阶段只受上一个阶段影响，可以用状态转移方程来描述阶段与阶段之间的变化过程。我们使用julia的SDDP算法包来求解随机动态规划问题。

2024年01月16日
浏览(40)
【优化数学模型】2. 动态规划DP方法的求解思路

多阶段决策问题，就是要在允许的决策范围内，选择一个最优决策使整个系统在预定标准下达到最佳效果。动态规划 (dynamic programming,DP) 是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n维决策问题变换为几个一维最优化问题，从而一个一个地去

2024年02月21日
浏览(41)
运筹说第67期 | 动态规划模型的建立与求解

通过前一期的学习，我们已经学会了动态规划的基本概念和基本原理。本期小编带大家学习动态规划模型的建立与求解。动态规划模型的建立一概述建立动态规划的模型，就是分析问题并建立问题的动态规划基本方程。成功地应用动态规划方法的关键，在于识别问题的

2024年01月16日
浏览(33)
6-1 求解资源分配问题（动态规划法）[PTA]

6-1 求解资源分配问题（动态规划法）某公司有3个商店A、B、C，拟将新招聘的5名员工分配给这3个商店，各商店得到新员工后，每年的赢利情况如下表所示，求分配给各商店各多少员工才能使公司的赢利最大。函数接口定义：裁判测试程序样例：输入格式: 第一行输入商店数

2024年02月12日
浏览(64)
回溯法，分支限界法，动态规划法求解0-1背包问题(c++)

问题描述给定n种物品和一背包。物品i的重量是wi0，其价值为vi0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？搜索空间: 子集树(完全二叉树) 约束函数(进包用): 如果当前背包中的物品总重量是cw,前面k-1件物品都已经决定是否进包,那

2024年02月10日
浏览(57)
C++ 求解最长公共子序列（不仅仅求出其大小）（简单易懂！！！）（动态规划）

求解两个数组的最长公共子序列我们需要用到的知识点有：动态规划dp，递归算法先来说说动态规划dp 很多初学者在学习动态规划的时候总是百思不得其解，什么是动态规划呢，其实总结来说就是程序将计算过的结果记录下来，在下次使用到这条记录的时候不需要再次计算，

2024年02月04日
浏览(43)
【多目标规划问题求解】ε-约束算法

TIME:2022/07/30 Author:雾雨霜星 Web:雾雨霜星的小站小站原文链接：https://www.shuangxing.top/#/post?id=27 [1]Nima Amjady and Jamshid Aghaei and Heidar Ali Shayanfar. Stochastic Multiobjective Market Clearing of Joint Energy and Reserves Auctions Ensuring Power System Security[J]. IEEE Transactions on Power Systems, 2009, 24(4) : 1841-1854. [

2024年02月05日
浏览(164)
整数规划——分支界定算法（旅行商问题，规约矩阵求解）

一、普通优化问题分枝定界求解题目的原问题为在计算过程中，利用MATLAB中的linprog（）函数进行求解最优解，具体的计算步骤如下： A为约束系数矩阵，B为等式右边向量，C为目标函数的系数向量。进行第一次最优求解以A=[2 9;11 -8],B=[40;82],C=[-3,-13]利用linprog函数求解。解

2024年02月16日
浏览(37)