algorithm - 找到具有 k 个蓝色顶点的树的最佳顶点覆盖

Question

我需要为以下问题找到一种“动态编程”的解决方案:

Input:

• Perfect Binary-Tree，T = (V,E) -(每个节点只有 2 个 child ，叶子除外)。
  V = V(蓝色) ∪ V(黑色) V(蓝色)∩V(黑色)=∅。

(换句话说，树中的某些顶点是蓝色的)

• 树“r”的根。
• 整数 k

---

A legal Solution:

顶点子集 V' ⊆ V 是 T 的顶点覆盖，并且|V' ∩ V(blue)| = k。 (换句话说，封面V'包含k个蓝色顶点)

---

Solution Value:

合法解 V' 的值是集合中的顶点数 = |V'|。 为方便起见，我们将“非法”解的值定义为∞。

---

What we need to find:

具有最小值(value)的解决方案。

(换句话说，最好的解决方案是一个覆盖的解决方案，恰好包含k个蓝色顶点和顶点数在集合中是最小。)

---

我需要定义一个典型的子问题。 (比如，如果我知道子树的值(value)解决方案是什么，我就可以用它来找到问题的值(value)解决方案。)

并提出一个公式来解决它。

Answer 1

在我看来，您的方向是正确的! 不过，我认为您将不得不使用一个额外的参数来告诉我们任何选定的顶点距离当前子树的根有多远。 例如，它可以只是指示我们是否选择当前顶点，如下所示。

设 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) = +无限。 在实现中，无穷大可以是大于任何可能答案的任何值。

对于所有内部顶点，令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 覆盖。