【算法】可用动态规划求解的问题的基本特征 |
您所在的位置:网站首页 › 一个算法的基本特征是 › 【算法】可用动态规划求解的问题的基本特征 |
对于动态规划思想,每一个刚刚接触的人都会都会十分迷惑,哪些问题可以用动态规划思想求解呢?最近一直在学习动态规划,书中也讲了好多关于能用动态规划求解问题的特征,根据自己的想法,我总结了以下几个可以用动态规划的问题的基本特征: 1,最优子结构 母问题的最优解包含其子问题的最优解,我们就称此问题具有最优子结构。即也就是说,子问题最优时,母问题通过优化一定能求得最优解 2,子问题重叠 子问题本质上是和母问题一样的,只是问题的输入参数不一样,就可以称之为子问题重叠,这是动态规划解决问题的高效的本质所在,我们可以利用很多子问题具有相同的输入参数这一个性质,来减少计算量。 3,问题存在边界 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |