适合用动态规划方法求解的问题必须具备何种特征
发布网友
发布时间:2022-03-24 06:02
我来回答
共2个回答
热心网友
时间:2022-03-24 07:32
可以用动态规划的问题的基本特征:
1,最优子结构
母问题的最优解包含其子问题的最优解,我们就称此问题具有最优子结构。即也就是说,子问题最优时,母问题通过优化一定能求得最优解
2,子问题重叠
子问题本质上是和母问题一样的,只是问题的输入参数不一样,就可以称之为子问题重叠,这是动态规划解决问题的高效的本质所在,我们可以利用很多子问题具有相同的输入参数这一个性质,来减少计算量。
3,问题存在边界
子问题在一定情况下就不存在子问题了, 我们称这种情况为问题存在边界,对于自顶向上和自底向下的方法,边界分别是问题的出口和入口。
4,子问题相互独立
个子问题在求解最优解时事相互独立的,即本自问题的求解和其他平行子问题是不相干的。当平行子问题解决后,选择权交给母问题时,它才会考虑各子问题之间的关系,是求最大值还是最小值,还是要做相关的运算得到母问题的最优解。
热心网友
时间:2022-03-24 08:50
动态规划的子问题是不独立的,很多子问题重复