假设我们有一个类似于链表（或有向无环图）的图。独立集合由不与集合中任何其他节点共享边的节点组成。如果每个节点都被加权，我们如何计算独立节点集的最大可能值？我知道我们必须使用动态编程，所以我有一点线索，但我希望有人能解释他们将如何处理它。谢谢！
问问题
2494 次
1 回答
3
我相信这个问题对于任意有向无环图来说是 NP-hard 的。已知无向图的相应问题是 NP 难的，并且可以通过以使结果图成为 DAG 的方式引导所有边来将该问题转换为问题的有向版本。原始图中的任何独立集都将是有向图中的独立集，反之亦然，因此任何有向情况的解决方案都将解决无向情况。
您的问题涉及在链表上解决此问题。如果您仅针对链表解决问题，则可以使用动态规划的多项式时间解决方案。作为提示，如果您在链表中选择一个节点，则必须跳过下一个节点，然后应该最大化剩余的节点。如果您不选择节点，您只需最大化列表其余部分的值。取这两个选项中的一个更好并评估这个自下而上将为您提供一个非常快速的 DP 算法。
希望这可以帮助！
于 2014-10-19T22:01:48.480 回答