路径图的最大权独立集问题

the algorithm never selects the minimum-weight vertex.

考虑:*3-100-4-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,99100100100)的所有排列,它应该给你大部分的位置。

这里有一个完整的答案,灵感来自于@robert king's answer。

考虑一下这条路 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 . 请注意, 七 未包含在子问题的最佳解决方案中 1-9-7-1 或者,因为它的前一个顶点是“重的”,并且由于所有权重都是正的,所以下一个权重和较重的顶点的总和肯定大于 七 . 因此,选项4不正确。

选项3正确。这源于归纳法,因为子问题的最优解只依赖于前两个子问题的解。