Prim 算法与集合覆盖

前六条边依次为：AB, BE, DE, EH, GH, HI。

算法过程：

Prim 算法从顶点 A 开始，维护已访问集合 \(S\)。每次选择连接 \(S\) 与 \(V\setminus S\) 的最小权边加入 MST，若有多个相同权重的边，按字典序选择。

1. \(S = \{A\}\)，可选边 AB(1), AD(34)，选择 AB。
2. \(S = \{A,B\}\)，可选边 BE(2), AD(34), BC(8)，选择 BE。
3. \(S = \{A,B,E\}\)，可选边 DE(5), EH(6), AD(34), BC(8), EF(9)，选择 DE。
4. \(S = \{A,B,D,E\}\)，可选边 EH(6), AD(34), BC(8), CF(9), DG(9), EF(9)，选择 EH。
5. \(S = \{A,B,D,E,H\}\)，可选边 GH(7), HI(7), AD(34), BC(8), CF(9), DG(9), EF(9), FI(9)，选择 GH（字典序 \(G < I\)）。
6. \(S = \{A,B,D,E,G,H\}\)，可选边 HI(7), AD(34), BC(8), CF(9), DG(9), EF(9), FI(9), GJ(10)，选择 HI。

时间复杂度： 使用二叉堆实现为 \(O((V+E) \log V)\)，对于连通图可简化为 \(O(E \log V)\)。

考虑基础集合 \(U = \{1, 2, 3, \ldots, 2^k\}\)，其中 \(k \geq 2\)。令

\[T_1 = \{1, 3, 5, \ldots, 2^k - 1\}, \quad T_2 = \{2, 4, 6, \ldots, 2^k\}.\]

这两个集合 \(T_1\) 与 \(T_2\) 构成一个最优覆盖（optimal cover）。

我们再添加集合 \(S_1, \ldots, S_{k-1}\)，定义

\[\ell_i = 2 + \sum_{j=1}^{i} 2^{k-j} \quad (\text{取 } \ell_0 = 0),\]

并令

\[S_i = \{\ell_{i-1} + 1, \ldots, \ell_i\}.\]

直观上，\(S_i\) 覆盖了略多于全集 \(1/2^i\) 比例的元素，且特别地 \(S_1\) 比 \(T_1\) 和 \(T_2\) 都大。

贪心选择分析： 由于 \(S_1\) 包含 \(2^{k-1} + 2\) 个元素，贪心算法会首先选中 \(S_1\)。当算法已选中 \(\{S_1, S_2, \ldots, S_i\}\) 后，\(T_1\) 与 \(T_2\) 各自仅能再覆盖 \(2^{k-i-1} - 1\) 个新元素，而 \(S_{i+1}\) 能覆盖 \(2^{k-i-1}\) 个新元素。因此在每一步中，\(S_{i+1}\) 覆盖的新元素都多于 \(T_1\) 或 \(T_2\) 单独覆盖的新元素，贪心算法会继续选择 \(S_{i+1}\)。

因此贪心算法最终选出的覆盖为 \(\{S_1, S_2, \ldots, S_{k-1}\}\)，共 \(k - 1 = \log n - 1\) 个集合，即 \(\Omega(\log n)\) 个集合。

具体示例（\(n = 64\)）： 令 \(T_1 = \{1, 3, \ldots, 63\}\)，\(T_2 = \{2, 4, \ldots, 64\}\)，选 \(T_1, T_2\) 为最优解。再令

• \(S_1 = \{1, 2, \ldots, 32, 33, 34\}\)，即比 \(64/2\) 多 2 个元素；

• \(S_2\) 包含接下来的 \(64/4 = 16\) 个元素；

• \(S_3\) 包含接下来的 \(64/8 = 8\) 个元素；

• \(S_4\) 包含接下来的 \(64/16 = 4\) 个元素；

• \(S_5\) 包含最后剩下的 \(2\) 个元素。

这是因为 \(64 = 32 + 16 + 8 + 4 + 2 + 2\)，我们只是将项重新分组为 \(64 = (32 + 2) + 16 + 8 + 4 + 2\) 并据此构造集合。

贪心算法将选中 \(S_1, S_2, S_3, S_4, S_5\) 而非 \(T_1, T_2\)。由于 \(n = 64\) 时 \(k = 6\)，贪心算法共选中 \(k - 1 = 5\) 个集合，即 \(\log n - 1\) 个集合。前两段的推导将此推广到了所有 \(k\)。

复杂度与结论： 该实例中贪心算法选出 \(\Theta(\log n)\) 个集合，而最优解仅需 2 个集合，因此贪心算法的近似比达到 \(\Theta(\log n)\)，证明了课上给出的 \(O(\log n)\) 上界是紧的。

解：初始时令 \(G\) 为原图，\(I = \emptyset\)。重复以下过程直到 \(G = \emptyset\)：

1. 在 \(G\) 中任选一个顶点 \(v\)，令 \(I = I \cup \{v\}\)。
2. 从图中删除 \(v\) 及其所有邻居。
3. 令 \(G\) 为新的图。

根据构造方式，\(I\) 显然是一个独立集（每次加入 \(v\) 时，它的所有邻居都会被删除，不可能再被加入）。每一步中，\(I\) 恰好增加一个顶点，而从图中最多删除 \(d + 1\) 个顶点（因为 \(v\) 最多有 \(d\) 个邻居，加上 \(v\) 本身）。因此，整个算法至少执行 \(\frac{|V|}{d+1}\) 轮。

设 \(K\) 为最大独立集的大小，显然 \(K \leq |V|\)。利用上面的讨论可得：

\[ |I| \geq \frac{|V|}{d+1} \geq \frac{K}{d+1} \]

因此，算法找到的独立集大小至少是最优解的 \(\frac{1}{d+1}\)。

（a）运行时间分析

运行时间的递推式为 \(T(n) = T(n-1) + T(n-2)\)。

下界：\(T(n) \geq 2T(n-2)\)，因此 \(T(n) = \Omega(2^{n/2})\)。

上界：\(T(n) \leq 2T(n-1)\)，因此 \(T(n) = O(2^n)\)。

综上，\(T(n) = 2^{\Theta(n)}\)。

更精确的运行时间：设 \(T(n) = \Theta(a^n)\)，代入递推式得 \(a^n = a^{n-1} + a^{n-2}\)，即 \(a^2 = a + 1\)，\(a^2 - a - 1 = 0\)。由求根公式得 \(a = \frac{1 \pm \sqrt{5}}{2}\)。由于 \(a\) 必须为正，故 \(a = \frac{1+\sqrt{5}}{2}\)，因此 \[ T(n) = \Theta\left(\left(\frac{1+\sqrt{5}}{2}\right)^n\right). \]

（b）fibo(5) 的递推树

                          fibo(5)
                        /          \\
                  fibo(4)          fibo(3)
                 /      \\         /      \\
          fibo(3)    fibo(2)  fibo(2)  fibo(1)
          /    \\     /    \\    /    \\
     fibo(2) fibo(1) fibo(1) fibo(0) fibo(1) fibo(0)
     /    \\
fibo(1) fibo(0)

可以观察到大量重复计算的节点（例如 fibo(1) 被计算了 5 次，fibo(0) 被计算了 3 次）。

（c）记忆化实现

def optimized_fibo(n):
    stored_fibos = [-1 for _ in range(n+1)]
    def fibo(n):
        # base case
        if n <= 1:
            return n
        # if we've already computed fibo(n) before, we can reuse it via stored_fibos!
        if stored_fibos[n] != -1:
            return stored_fibos[n]
        # if we haven't already computed fibo(n), then we need to recurse as before:
        # make sure to store it in stored_fibos so that we can use it in the future!
        stored_fibos[n] = fibo(n-1) + fibo(n-2)
        return stored_fibos[n]

（d）新算法的运行时间

观察：对于每个 \(k \leq n\)，第 \(k\) 个斐波那契数只会被计算一次，其余时候直接返回已保存的值。此外，fib(k) 最多被调用两次（分别由 fib(k+1) 和 fib(k+2) 调用）。

因此，运行时间为 \(O(n)\)。

（e）自底向上实现

def fibo_dp_bottom_up(n):
    stored_fibos = [-1 for _ in range(n+1)]
    # define base cases at the "bottom"
    stored_fibos[0] = 0
    stored_fibos[1] = 1
    # build your subproblems "up" from your smaller subproblems
    for i in range(2, n+1):
        stored_fibos[i] = stored_fibos[i-1] + stored_fibos[i-2]
    # what element in stored_fibos represents the nth fibonacci number?
    answer = stored_fibos[n]
    return answer

（f）空间复杂度与 \(O(1)\) 优化

原算法的空间复杂度为 \(O(n)\)，因为我们需要创建一个长度为 \(n+1\) 的数组来保存 \(F_0, F_1, \dots, F_n\)。

注意到每个斐波那契数只依赖于前两个数，因此我们只需保存最近计算的两个斐波那契数。优化后的实现如下：

def fibo_dp_bottom_up(n):
    # define base cases here
    if n <= 1:
        cur_fib = n
    prev_2_fib = 0
    prev_1_fib = 1
    # build your subproblems "up" from your smaller subproblems
    for i in range(2, n+1):
        cur_fib = prev_2_fib + prev_1_fib
        # update prev_2_fib and prev_1_fib for i+1
        prev_2_fib = prev_1_fib
        prev_1_fib = cur_fib
    # where are you storing the nth fibonacci number?
    answer = cur_fib
    return answer

该优化版本只使用了常数个额外变量，因此额外空间复杂度为 \(O(1)\)。