找到具有 k 个蓝色顶点的树的最佳顶点覆盖
Find the Optimal vertex cover of a tree with k blue vertices
我需要为以下问题找到一种 'dynamic - programming' 的解决方案：
Input:
- 完美Binary-Tree,T = (V,E)-（每个节点正好有2个children 除了树叶）。
V = V（蓝色）∪ V（黑色）。
V(蓝)∩V(黑)=∅.
（也就是说，树中的一些顶点是蓝色的）
- 树的根'r'。
- 整数k
A legal Solution:
顶点子集 V' ⊆ V 是 T 的 顶点覆盖，并且 |V' ∩ V(blue)| =k。 （也就是说，封面V'包含k个蓝色顶点）
Solution Value:
合法解 V' 的值是集合中的顶点数 = |V'|。
为了方便起见，我们将 "un-legal" 解的值定义为 ∞.
What we need to find:
具有 最小 值的解决方案。
（换句话说，最好的解决方案是覆盖，恰好包含k个蓝色顶点和集合中的顶点数 最少。）
我需要定义一个典型 sub-problem。 （比如，如果我知道子树的价值解决方案是什么，我就可以用它来找到问题的价值解决方案。）
并提出一个公式来解决它。
在我看来，您的方向是正确的！
不过，我认为您将不得不使用一个额外的参数来告诉我们任何选定的顶点距离当前子树的根有多远。
例如，它可以只是指示我们是否选择当前顶点，如下所示。
设 fun (v, b, p) 为根为 v 的子树的最佳大小，这样，在该子树中，我们恰好选择 b 个蓝色顶点，如果我们选择 p = 1如果我们不选择顶点 v 或 p = 0。
答案是 fun (r, k, 0) 和 fun (r, k, 1) 中的最小值：我们想要完整树 (v = r) 的答案，恰好 k 个顶点被蓝色覆盖(b = k)，我们可以选择根，也可以不选择根。
现在，我们如何计算呢？
对于叶子，fun (v, 0, 0)是0，fun (v, t, 1)是1，其中t告诉我们顶点v是否是蓝色（1 如果是，0 如果不是）。
所有其他组合都是无效的，我们可以通过说各自的值是正无穷大来模拟它：例如，对于叶顶点v，值fun (v, 3, 1) = +infinity。
在实现中，无穷大可以是任何大于任何可能答案的值。
对于所有内部顶点，设v为当前顶点，u和w为其子顶点。
我们有两个选择：选择或不选择顶点 v.
假设我们选择它。
那么我们得到的 f (v, b, 1) 的值是 1（选择的顶点 v）加上 fun (u, x, q) + fun (w, y, r) 的最小值，使得 x + y 是 b如果顶点 v 是黑色或 b - 1 如果它是蓝色，并且 q 和 r 可以是任意的：如果我们选择顶点 v，则边v--u 和 v--w 已经被我们的顶点覆盖所覆盖。
现在让我们不要选择顶点 v。
然后我们得到的 f (v, b, 0) 的值只是 fun (u, x, 1) + fun (w, y, 1) 的最小值，这样 x + y = b：如果我们没有选择顶点 v，边 v--u 和v--w 必须被 u 和 w 覆盖。
我需要为以下问题找到一种 'dynamic - programming' 的解决方案：
Input:
- 完美Binary-Tree,T = (V,E)-（每个节点正好有2个children 除了树叶）。
V = V（蓝色）∪ V（黑色）。 V(蓝)∩V(黑)=∅.
（也就是说，树中的一些顶点是蓝色的）
- 树的根'r'。
- 整数k
A legal Solution:
顶点子集 V' ⊆ V 是 T 的 顶点覆盖，并且 |V' ∩ V(blue)| =k。 （也就是说，封面V'包含k个蓝色顶点）
Solution Value:
合法解 V' 的值是集合中的顶点数 = |V'|。 为了方便起见，我们将 "un-legal" 解的值定义为 ∞.
What we need to find:
具有 最小 值的解决方案。
（换句话说，最好的解决方案是覆盖，恰好包含k个蓝色顶点和集合中的顶点数 最少。）
我需要定义一个典型 sub-problem。 （比如，如果我知道子树的价值解决方案是什么，我就可以用它来找到问题的价值解决方案。）
并提出一个公式来解决它。
在我看来，您的方向是正确的！ 不过，我认为您将不得不使用一个额外的参数来告诉我们任何选定的顶点距离当前子树的根有多远。 例如，它可以只是指示我们是否选择当前顶点，如下所示。
设 fun (v, b, p) 为根为 v 的子树的最佳大小，这样，在该子树中，我们恰好选择 b 个蓝色顶点，如果我们选择 p = 1如果我们不选择顶点 v 或 p = 0。
答案是 fun (r, k, 0) 和 fun (r, k, 1) 中的最小值：我们想要完整树 (v = r) 的答案，恰好 k 个顶点被蓝色覆盖(b = k)，我们可以选择根，也可以不选择根。
现在，我们如何计算呢？
对于叶子，fun (v, 0, 0)是0，fun (v, t, 1)是1，其中t告诉我们顶点v是否是蓝色（1 如果是，0 如果不是）。
所有其他组合都是无效的，我们可以通过说各自的值是正无穷大来模拟它：例如，对于叶顶点v，值fun (v, 3, 1) = +infinity。
在实现中，无穷大可以是任何大于任何可能答案的值。
对于所有内部顶点，设v为当前顶点，u和w为其子顶点。
我们有两个选择：选择或不选择顶点 v.
假设我们选择它。
那么我们得到的 f (v, b, 1) 的值是 1（选择的顶点 v）加上 fun (u, x, q) + fun (w, y, r) 的最小值，使得 x + y 是 b如果顶点 v 是黑色或 b - 1 如果它是蓝色，并且 q 和 r 可以是任意的：如果我们选择顶点 v，则边v--u 和 v--w 已经被我们的顶点覆盖所覆盖。
现在让我们不要选择顶点 v。
然后我们得到的 f (v, b, 0) 的值只是 fun (u, x, 1) + fun (w, y, 1) 的最小值，这样 x + y = b：如果我们没有选择顶点 v，边 v--u 和v--w 必须被 u 和 w 覆盖。