开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >寻找顶点的最小子集-回溯？

问寻找顶点的最小子集-回溯？
EN

Stack Overflow用户

提问于 2014-04-09 16:54:26

回答 1查看 194关注 0票数 1

设图G中所有边的E-集问题是求图G中顶点的最小子集S，满足条件:S=E中每个顶点的所有出界边之和。

换句话说，边缘是街道，我们可以在顶点上放置路灯。如果我们在一个顶点上放置一盏路灯--从这个顶点出发的所有街道都会被照亮。如何找到廉价的方法使所有的街道变得明亮？

有什么比回溯更好的吗？

graph-algorithm

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2014-04-09 18:24:05

这是一个np完全问题.但是像往常一样，有许多接近最优的解。试试这一个

票数 0

EN

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/22969107

复制

相似问题