最优子结构与贪婪选择
我在读关于贪婪问题的两个属性，我试图理解以下两者之间的区别
- 最优子结构性质：最优全局解包含其所有子问题的最优解
- 贪婪选择性质：通过贪婪地选择局部最优选择，可以获得全局最优解
两者不是等价的吗？这两者似乎是一回事；能不能举个例子，最优子结构满足，贪婪选择不满足？以及一个贪婪选择得到满足而最优子结构没有得到满足的例子？
共有2个答案
对于将来可能不熟悉顶点覆盖或动态编程的读者来说，这些定义的措辞听起来确实很相似。
我认为重新表述贪婪选择的一个有用方法是，最优解将始终包含贪婪算法选择的第一个选择，尽管它不一定是所述最优解中的第一个选择**-
这就是为什么它们是不同的，尽管贪婪选择可以导致最优子结构，但它并没有证明它有最优子结构。证明最优子结构的常见论点是交换论点和保持领先论点，它们建立在算法显示贪婪选择属性的知识之上。
它们不等效：
假设我们想在树中找到最小顶点覆盖，其中每个节点都有一个成本（覆盖的成本是该覆盖中节点所有成本的总和）。这里可以使用动态编程：f（v，取）是覆盖植根于v的子树的最小成本，这样v在封面中，f（v，未取）是覆盖该子树而不取v的最小成本。最优子结构属性成立，因为我们可以最优地解决子问题（即为每个子树找到一个最优解），然后将它们组合起来找到全局最优解。然而，贪婪选择属性在这里并不成立：选择成本最小的顶点，直到所有边都被覆盖，并不总是会产生最优结果。
贪婪选择属性可能成立，但如果无法定义子问题是什么，则最优子结构属性则不成立。例如，霍夫曼代码构造算法总是合并两个最小的子树（并产生最优解），所以它是一个贪婪的算法，但不清楚子问题是什么，所以谈论第一个属性根本没有多大意义。
-
我试图更全面地了解动态规划中最优子结构属性的使用，但我对为什么我们必须证明问题的任何最优解都包含子问题的最优解视而不见。 难道仅仅证明问题的某些最优解决方案具有这个属性，然后用它来论证由于我们的递归算法构建的解决方案至少与最优解决方案一样好，它本身将是最优的，这还不够吗？换句话说，我未能发现在我们的算法的正确性参数中，我们需要所有最优解都包含子问题的最优解。 要澄清： 最佳子结构的CLRS定义说，
-
贪婪 vs 不贪婪 当重复一个正则表达式时，如用 a*，操作结果是尽可能多地匹配模式。当你试着匹配一对对称的定界符，如 HTML 标志中的尖括号时这个事实经常困扰你。匹配单个 HTML 标志的模式不能正常工作，因为 .* 的本质是“贪婪”的 #!python >>> s = '<html><head><title>Title</title>' >>> len(s) 32 >>> print re.
-
用餐问题: 几家人一起出去吃饭。为了增加他们的社会交往，他们愿意坐在桌子上，这样同一家庭的两个成员就不会在同一张桌子上。假设晚餐特遣队有家庭，而家庭有成员。另外，假设有桌可用，并且第1桌的座位容量为。 问题是：我们可以坐在桌子上的最多人数是多少？ 编辑：创建一个图并运行最大流算法可以解决这个问题。但如果我们用Dinic算法有2*10^3个顶点，则全局复杂度为O(10^6*10^6)=O(10^12
-
图是由节点和连接节点的边构成的。节点之间可以由路径，即边的序列。根据路径，可以从一点到达另一点。在一个复杂的图中，图中两点可以存在许多路径。最短路径讨论了一个非常简单的图论问题，图中从A点到B点 ，那条路径耗费最短？ 这个问题又异常复杂，因为网络的构成状况可能很复杂。 一个最简单的思路，是找出所有可能的从A到B的路径，再通过比较，来寻找最短路径。然而，这并没有将问题简化多少。因为搜索从A到B的路径
-
本文向大家介绍php正则表达式中贪婪与非贪婪介绍，包括了php正则表达式中贪婪与非贪婪介绍的使用技巧和注意事项，需要的朋友参考一下 一、贪婪与非贪婪 什么叫贪婪，比如说要从字符串中<td>面包一</td><td>面包二</td>吃面包，本来你只可以吃面包一，可是你贪心，于是就把第一个<td>到最后一个</td>里面的两个面包取出来了，你想多吃点，非贪婪也就是你不贪吃了，就只吃面包一。 我们来看看正
-
本文向大家介绍贪婪算法相关面试题，主要包含被问及贪婪算法时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策