时间:2024-10-23 13:05:29
简要说明动态规划的基本特征
动态规划求解问题的基本特征包括:
1. 最优子结构:母问题的最优解包含其子问题的最优解,即子问题最优时,母问题通过优化一定能求得最优解。
2. 子问题重叠:子问题本质上是和母问题一样的,只是问题的输入参数不一样,这就是子问题重叠,这是动态规划解决问题的高效的本质所在。
3. 问题存在边界:子问题在一定情况下就不存在子问题了,我们称这种情况为问题存在边界,对于自顶向上和自底向下的方法,边界分别是问题的出口和入口。
4. 子问题相互独立:个子问题在求解最优解时事相互独立的,即本自问题的求解和其他平行子问题是不相干的。当平行子问题解决后,选择权交给母问题时,它才会考虑各子问题之间的关系,是求最大值还是最小值,还是要做相关的运算得到母问题的最优解。
科技之家 广州小漏斗信息技术有限公司 版权所有 提供支持 粤ICP备20006251号