假设我们有一个类似于链表（或有向无环图）的图。独立集包含不与集合中任何其他节点共享边缘的节点。如果每个节点都被赋予权重，我们如何计算节点独立集的最大可能价值？我知道我们必须使用动态规划，所以我有一点线索，但我希望有人能解释一下他们如何处理它。谢谢！
1个回答
3
我认为对于任意有向无环图，这个问题都是NP难的。对于无向图的相应问题已知是NP难的，并且可以通过将所有边定向以使得生成的图成为DAG来将该问题转换为问题的有向版本。原始图中的任何独立集在有向图中也将是独立集，反之亦然，因此有向情况下的任何解决方案都将解决无向情况。
你的问题涉及在链表上解决此问题。如果你只是针对链表解决问题，则可以使用动态规划的多项式时间解决方案。提示一下，如果你选择链表中的一个节点，则必须跳过下一个节点，然后应该最大化剩余部分。如果你不选择该节点，则仅需最大化列表其余部分的值。选择这两个选项中更好的一个并进行自底向上的评估将为你提供一个非常快速的DP算法。
希望这能帮到你！
你的问题涉及在链表上解决此问题。如果你只是针对链表解决问题，则可以使用动态规划的多项式时间解决方案。提示一下，如果你选择链表中的一个节点，则必须跳过下一个节点，然后应该最大化剩余部分。如果你不选择该节点，则仅需最大化列表其余部分的值。选择这两个选项中更好的一个并进行自底向上的评估将为你提供一个非常快速的DP算法。
希望这能帮到你！
- templatetypedef
3
1谢谢！我曾试图用树来可视化，但我认为您的解释比我的树更直接。 - Sticky
1只是好奇，这会提供线性运行时间吗？因为它会递归到基本情况，并且每次我们处理一个子问题时，我们都将其存储在某个表中，从而创建恒定的检索时间，这样做n次。（因此是线性的？） - Sticky
1@Sticky 是的，这是一个线性时间的解决方案！ - templatetypedef
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接