2回答
最优子结构
algorithm、optimization、dynamic-programming、proof-of-correctness
我试图更全面地了解最优子结构特性在动态规划中的应用，但我忽略了为什么我们必须证明问题的任何最优解都包含子问题的最优解。如果证明问题的某些最优解具有这个性质，然后用它来论证我们的递归算法所建立的解至少和最优解一样好，那么它本身就会是最优的，这还不够吗？换句话说，在我们的算法的正确性论证中，我们需要所有的最优解都包含子问题的
浏览 8提问于2014-02-27得票数 5
回答已采纳
2回答
科门书的动态规划
algorithm、dynamic-programming
当阅读cormen的“算法导论”(第15章:动态规划)中关于动态规划的文章时，我遇到了这样的说法。
根据计算出的信息构造最优解。步骤1-3构成了一个问题的动态规划解决方案的基础.如果我们只需要最优解的值，而不需要<em
浏览 5提问于2017-02-19得票数 0
2回答
弗洛伊德-沃尔是一个动态的算法吗？
algorithm、language-agnostic、graph-theory、floyd-warshall
因为弗洛伊德沃尔算法是动态的，这意味着它必须在任何时候都提供一个最优解，对吗？所以，让我困惑的是，在算法的每一部分中，这些最优解的本质是什么--特别是，我试图理解以下三个问题：
有人能对
浏览 0提问于2013-04-29得票数 1
回答已采纳
3回答
一个最优的算法会不会不完整？
algorithm
一个完整的算法是一个算法，如果有一个解决方案，如果有。最优算法是一种算法，它的任何解的返回都是最优的，换句话说，没有比返回的解更好的解。
这意味着最优性是建立在完全性的基础上的，对吧？这意味着一个算法不可能是最优的，而是不完整的。还是我搞错了？
浏览 1提问于2018-02-16得票数 1
回答已采纳
2回答
使用贪心算法进行优化
algorithm、optimization、greedy
如果一个优化问题可以用贪心方法解决，那么它的所有最优解是否都必须包含第一个选择(即贪婪选择)？
浏览 2提问于2013-06-17得票数 2
回答已采纳
1回答
0-1背包的贪婪算法
algorithm、combinatorics、knapsack-problem
是否有贪婪算法给出非分数(0-1背包)背包问题的最优解？我知道背包的小数版本有一个，给出了最优解。
浏览 3提问于2013-03-12得票数 4
2回答
一种证明没有贪婪算法来获得最优解的方法？
algorithm、greedy
我需要证明没有贪婪的算法可以得到一个给定问题的最优解。
我不清楚是否有一个问题必须满足的条件，从而存在一个贪婪的算法来获得最优解。或者，如果有任何充分条件，该问题不能由贪婪的算法解决。
浏览 4提问于2015-04-30得票数 3
回答已采纳
1回答
带两个背包的0-1背包问题的反例
algorithm、dynamic-programming、knapsack-problem
考虑以下两种算法方法。下列哪一种说法是正确的？算法(1)保证了对原问题提供1=2的最优可行解。
算法(1)保证对原问题产生最优可行解，但<e
浏览 0提问于2018-12-25得票数 0
回答已采纳
2回答
不依赖于初始解的优化算法
optimization
我知道一些优化算法，比如爬山，模拟退火，遗传算法。我想知道是否有任何优化算法不依赖于初始解，至少不像这三个算法那么多。
浏览 2提问于2012-02-23得票数 0
2回答
路径图的最大权无关集问题
algorithm、dynamic-programming、graph-theory
a[i] = max(a[i - 1], a[i - 2] + w[i])
如果一个顶点被排除在两个连续子问题的最优解之外，那么它就被排除在所有较大子问题的最优解之外。如果一个顶点被排除在子问题的最优解之外，那么它就被排除在所有较大子问题的最
浏览 1提问于2018-12-25得票数 2
回答已采纳
1回答
证明了旅行商的2倍最优逼近算法并不能计算出最优解。
algorithm、traveling-salesman、approximation
本文给出了一个关于旅行商问题(TSP)的2倍最优逼近算法在三角不等式不成立的情况下不计算2倍最优解的例子。我试过一个三角形的例子，它的代价是1，1，10。然而，要得到哈密顿循环，所有三条边都要经过。这样，最优解将与此算法的近似解没有什么不同。我看错了吗？我希望能在这方面提供任何帮助。
浏览 1提问于2015-05-09得票数 2
回答已采纳
1回答
在多目标条件下，如何生成最优指标组合？
indexing、open-gauss
opengauss文档中AI模块的索引建议支持在索引空间的限制范围内引入最优索引组合。然而，指数推荐代码似乎只使用爬山方法。爬山法是一种贪婪的算法.每一次，它只选择一个最大的当前利润和收敛和本地解决方案。然而，在指标返回和空间组合这两个目标的约束下，算法是否无法找到最优解？在这种情况下，如何计算最优解？
浏览 10提问于2022-02-11得票数 -1
2回答
有算法在多项式时间内求k-tsp (旅行商)的最优值吗？
algorithm、time-complexity、traveling-salesman
我读了的文章，它建议(第1025页最后一段)有一个多项式时间算法来寻找一个k-tsp问题的最优使用二进制搜索。使用二进制搜索将意味着有一个算法，以检查是否存在一个解决方案与cost<X，该算法用于二进制搜索。我搜索了一下这个算法，唯一能找到的算法是非确定性算法(这非常微不足道)，但很明显，我正在寻找一个确定性算法。如有任何帮助/链接，将不胜感激。编辑
我指的是寻找最优解的价
浏览 6提问于2011-12-22得票数 1
回答已采纳
1回答
我能解释一下如何使用最优子结构来找到这个powerpoint幻灯片中最长的增长子序列吗？
algorithm、optimization
目前，我正在学习如何在算法类中找到最优解，其中一个主题是如何在问题中找到最优子结构。到目前为止，我对它的理解是，我们能不能找到n个大小问题的最优解，如果可以的话，我们把问题的大小增加1，所以它就是n+1，如果n+1的最优解包括n的整个最优解加上+1引入的新的解，那么我们就有了最优的子结构给出了一个用最优子结构求出给定一组数的最长增长子序列的例子。下面的powerpoint幻灯片显示
浏览 3提问于2016-08-22得票数 4
回答已采纳
1回答
对于任何局部搜索算法，在邻域中搜索的一步是否总是可以在多项式时间内完成？
algorithm、complexity-theory、local、computation-theory
既然找到一个局部最优解可能比找到一个最优解更容易，我们能声称对于任何局部搜索算法，在邻域中搜索的一步总是可以在多项式时间内完成吗？
浏览 2提问于2018-05-31得票数 0
1回答
作业调度算法“最早结束时间优先”的反例
algorithm、job-scheduling、greedy
那么，我们有一个贪婪的算法来调度作业(调度最大的作业数)。所以，它总是给出每一组数据的最优解？我有一个执行器来执行作业，我想要执行最大数量的作业。
浏览 4提问于2016-08-31得票数 3
回答已采纳
4回答
遗传算法-更好的交叉/变异算法？
algorithm、genetic-algorithm
对于具有随机交叉边界和随机位点处随机变异数的基本遗传算法实现，会产生大量劣势子代，并留下最优解被偶然发现。这浪费了大量的CPU，用户不知道什么时候找到最优解，因为它可能总是“下一个”。有没有一种算法可以一直得到更好的孩子，而不是让这个重要的过程听天由命？
谢谢。
浏览 1提问于2014-06-10得票数 2
云服务器
对象存储
ICP备案
云点播
腾讯会议
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号