动态规划算法的局限性
动态规划算法的局限性
提问于 2012-01-21 13:26:54
在研究了这个问题之后，我意识到动态规划算法不能用于解决带有非整数约束的背包问题或类似问题。我的认识是对的吗？动态规划算法还有其他限制吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2012-01-21 14:21:45
基本上，您可以说，可能的分数(解决方案质量)的数量需要是有限的，足够低，以适应内存。非整数通常是指非离散的，这导致无限可能的解分数。
如果只有N个可能的解分数，你知道你最多需要找到其中的N个，才能得到最好的解，而不是达到它们的全部指数型方法。这就是动态规划背后的理念。
Stack Overflow用户
发布于 2012-01-21 16:26:05
我认为另一个限制是不知道动态规划是否是最好的可用技术，因为它的性能不知道与信息论下限匹配。
这是大卫·埃普斯坦的一个例子
给出了n个实数的排序列表，找出了k元素在1~n之间的所有值的最小区间，有一个简单的动态规划算法在二次时间内解决了这个问题，但最著名的下界只是线性的。要么描述一个更快的算法，要么在一些合理的计算模型中证明一个更大的下界。(“动态规划”不是一个合理的复合模型！)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8953331
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号