路径图的最大权无关集问题

Question

在使用算法:设计与分析(二)类时，其中一个问题询问路径图的最大权重独立集问题。下面显示的是问题陈述的(模糊)屏幕截图，相应的讲座视频在YouTube上显示：

https://www.youtube.com/watch?v=0awkct8SkxA

https://www.youtube.com/watch?v=pLOkbHGRsv0

zjFkZDCY

​

这个问题可以通过动态编程巧妙地解决，只需一行代码即可。

a[i] = max(a[i - 1], a[i - 2] + w[i])

问题如下：

对于我们计算路径图的最大权独立集的动态规划算法，下列哪一项是正确的？(假设没有联系。)

• 只要输入图至少有两个顶点，算法就不会选择最小权顶点。
• 算法总是选择最大权顶点.
• 如果一个顶点被排除在两个连续子问题的最优解之外，那么它就被排除在所有较大子问题的最优解之外。
• 如果一个顶点被排除在子问题的最优解之外，那么它就被排除在所有较大子问题的最优解之外。

事实证明，正确的答案是#3，这有点直观，因为子问题的最优解只取决于前两个子问题的解决方案。但我不清楚为什么选择1和2是不正确的。由于该算法查看了所有的顶点，这两个选项似乎也应该是正确的。

Answer 1

the algorithm never selects the minimum-weight vertex.

考虑：**3-100-4- 1 -1-5-100-6选择1是合理的，因为我们想选择两个100。

The algorithm always selects the maximum-weight vertex.

考虑：5-99-100-99-7

这是有意义的，排除最大值，以支持到99年代。

对于这两个例子，试着看看算法会做什么以及它为什么工作。

对这些类型的问题进行推理的一种很好的方法是尝试(0,0,0,1,1,1,2,2,2,3,3,3,99,99,99,100,100,100)的所有排列，它应该会给你大部分的可能性。

Answer 2

在这里:这是一个完整的完整的答案，灵感来自@robert-king的答案。

考虑路径10-2-1-4。算法选择的顶点是10, 1，其中选择了最小的1。因此，备选案文1是不正确的。

考虑路径1-3-10-9。算法选择的顶点是3, 9，其中没有选择最大10。因此，备选案文2是不正确的。

考虑路径1-9-7-1-5。算法选择的顶点为1, 7, 5。然而，7不包括在子问题1-9-7的最优解中。注意，7也没有包含在子问题1-9-7-1的最优解中，因为它的前一个顶点是“更重的”，而且由于所有的权重都是正的，所以下一个权重和较重的顶点的和肯定大于7。因此，备选案文4是不正确的。

备选案文3是正确的。这源于归纳法，因为子问题的最优解只取决于前两个子问题的解。