如何找到有向无环图的最大独立集？

假设我们有一个类似于链表（或有向无环图）的图。一个独立的集合由不与集合中的任何其他节点共享边的节点组成。如果每个节点都是加权的，我们如何计算独立节点集的最大可能值？我知道我们必须使用动态编程，所以我有一点线索，但我希望有人能解释他们将如何处理它。谢谢！如何找到有向无环图的最大独立集？

来源

2014-10-19 Sticky

我认为这个问题对于任意有向无环图是NP难的。已知无向图的相应问题是NP-hard，并且可以通过以使得所得图形成为DAG的方式引导所有边来将该问题转换为问题的定向版本。原始图中的任何独立集都将成为有向图中的独立集合，反之亦然，因此任何针对有向情形的解决方案都将解决无向情况。

你的问题是关于在链表上解决这个问题的。如果您只是为链表解决问题，那么使用动态编程就有一个多项式时间解决方案。作为提示，如果您在链接列表中选择一个节点，则必须跳过下一个节点，然后应该最大化剩下的部分。如果您不选择节点，那么只需最大化其余列表的值即可。充分利用这两个选项并评估这种自下而上的方法会给你一个非常快速的DP算法。

希望这会有所帮助！

来源

2014-10-19 22:01:48 templatetypedef

谢谢！我试图用一棵树想象，但我认为你的解释是比我的树更重要的解决方案... – Sticky 2014-10-19 22:24:13

只是好奇，这会提供一个线性运行时间吗？由于它会缓存到基本情况，并且每次我们做一个子问题时，我们都会将它存储在某个表中，从而创建持续的检索时间，并执行n次。（因此是线性的？） – Sticky 2014-10-20 01:29:03

@Sticky Yep，这是一个线性时间解决方案！ – templatetypedef 2014-10-20 05:35:38

如何找到有向无环图的最大独立集？

回答

相关问题