支配集贪婪逼近最坏情况示例
支配集贪婪逼近最坏情况示例
提问于 2012-06-04 21:59:52
要找到无向图G的最小支配集，可以使用如下贪心算法:从一个空集D开始，直到D是一个支配集，添加一个具有最大未覆盖邻居数的顶点v。
该算法一般不会找到最优解，它是一个ln(增量)-approximation。(如果增量是G中顶点的最大次数)
现在我正在寻找一个简单的例子，其中贪婪算法找不到最优解。我找到的唯一一个是集合覆盖问题的相关实例。(右侧的http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm图片)将此图转换为图将导致至少14个顶点和大量边。
有人知道一个小例子吗？
提前感谢
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-06-05 05:18:08
考虑下图：
贪婪的方法会选择B，然后是D和G。同时，E和F形成一个支配集。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/10882599
复制相关文章
相似问题
腾讯云开发者
