CS 170 2023年秋季 作业8

本题无需算法解答，只需如实填写本人学习小组成员的姓名与 SID；若无合作者，填写 "none" 即可。

(a)

\[ M(x, m) = M(x-1, m-1) + M(x-1, m) + 1 \]

我们首先推导 \(i\)，即在给定 \(x\) 次扔蛋和 \(m\) 个鸡蛋的情况下，第一次扔鸡蛋的最优楼层。如果鸡蛋从第 \(i\) 层扔下后碎了，问题就转化为第 \(0\) 层到第 \(i-1\) 层，我们可以用剩下的 \(x-1\) 次扔蛋和 \(m-1\) 个鸡蛋解决这个子问题。对于 \(x-1\) 次扔蛋和 \(m-1\) 个鸡蛋，最优策略可以区分 \(M(x-1, m-1) + 1\) 层楼，所以我们应该选择 \(i = M(x-1, m-1) + 1\)。

另一方面，如果鸡蛋没碎，问题就转化为第 \(i\) 层到第 \(n\) 层，用 \(x-1\) 次扔蛋和 \(m\) 个鸡蛋。使用这么多扔蛋次数和鸡蛋能区分的最大楼层数是 \(M(x-1, m) + 1\)，所以我们可以解决 \(n\) 大到 \(i + M(x-1, m) = M(x-1, m-1) + M(x-1, m) + 1\) 的子问题。

(b) 对于基本情况，我们取 \(M(0, m) = 0\)（对任意 \(m\)）和 \(M(x, 0) = 0\)（对任意 \(x\)）。从 \(x = 1\) 开始，我们计算所有 \(1 \le m' \le m\) 的 \(M(x, m')\)，然后对递增的 \(x\) 重复此过程，直到计算出所有需要的 \(M(x, m)\)。返回 \(M(x, m)\)。

我们计算 \(xm\) 个子问题，每个子问题花费常数时间，所以总运行时间是 \(\Theta(xm)\)。

(c) 同样地，从 \(x = 1\) 开始，我们计算所有 \(1 \le m' \le m\) 的 \(M(x, m')\)，并对递增的 \(x\) 重复此过程。这次，我们第一次找到满足 \(M(x, m) \ge n\) 的 \(x\) 时停止，并返回这个 \(x\) 值。

(d) 因为只有 \(n\) 层楼，最优扔蛋次数 \(x\) 最多为 \(n\)。由 (b) 我们知道运行时间是 \(\Theta(xm)\)，所以如果 \(x \le n\)，我们知道运行时间必须是 \(O(nm)\)。（这是一个非常宽松的上界，但比直接使用 \(f(n, m)\) 的递推式得到的朴素 \(O(n^2m)\) 时间算法要好得多。）

(e) 当我们在计算所有 \(1 \le m' \le m\) 的 \(M(x, m')\) 时，我们只需要存储前一轮 \(x-1\) 对应的 \(M(x-1, m')\) 和当前轮 \(x\) 对应的 \(M(x, m')\)，即我们只需要存储 \(O(m)\) 个值。特别地，在计算出所有 \(m'\) 的 \(M(x, m')\) 后，我们可以删除存储的 \(M(x-1, m')\) 值。

(f) 设 \(M_1(x, m)\) 为当第 \(m\) 个鸡蛋还剩 1 条命时的 \(M(x, m)\)，\(M_2(x, m)\) 为当第 \(m\) 个鸡蛋还剩 2 条命时的 \(M(x, m)\)。那么我们的递推关系如下：

\[ M_1(x, m) = M_2(x-1, m-1) + M_1(x-1, m) + 1 \]

\[ M_2(x, m) = M_1(x-1, m) + M_2(x-1, m) + 1 \]

备选解法： 注意这个修改实际上使我们的鸡蛋数量翻倍。因此，我们根本不需要修改递推关系，只需返回 \(M(x, 2m)\) 作为答案。

算法：我们使用长度为 \(L\) 的位串来表示棋盘每一行的配置（1 表示对应格子有骑士，0 表示没有）。

算法的主要思想如下：我们解决 \((h-1) \times L\) 棋盘的有效配置数的子问题，并用它来解决 \(h \times L\) 的情况。注意，当我们逐行递增 \(h\) 时，第 \(h\) 行的骑士只会影响第 \(h+1\) 行和第 \(h+2\) 行的配置。因此，我们定义 \(K(h, u, v)\) 为前 \(h\) 行中，第 \((h-1)\) 行为 \(u\)、第 \(h\) 行为 \(v\) 的可能配置数，然后用动态规划解决此问题。

如果按位串列表的对应方式放置骑士（第一行按第一个位串，第二行按第二个位串，依此类推）不会导致两个骑士互相攻击，则该位串列表是有效的。那么对于所有 \(u, v\) 对，\(K(2, u, v) = 1\) 当且仅当 \(u, v\) 有效，否则为 0。

对于 \(K(h, v, w)\)，当 \(h > 2\) 时：

\[ K(h, v, w) = \sum_{u: u,v,w \text{ 有效}} K(h-1, u, v) \bmod 1337 \]

正确性证明：唯一的以行配置 \(u, v\) 结尾的 2 行骑士配置就是配置 \(u, v\) 本身。因此 \(K(2, v, w) = 1\) 当且仅当 \(u, v\) 有效，否则 \(K(2, v, w) = 0\)。

对于 \(h > 2\)，上述递推关系是正确的，因为对于任意以 \(v, w\) 结尾的有效 \(h\) 行配置，前 \(h-1\) 行必须是以 \(u, v\) 结尾的有效配置（对于某个 \(u\)），并且对于同一个 \(u\)，最后三行 \(u, v, w\) 也必须是有效配置。此外，这种 \(h\) 行配置与 \((h-1)\) 行配置之间的对应关系是双射。

运行时间分析：对于每一行，我们遍历该行所有可能的骑士配置，并对每个配置执行对所有可能有效的前两行配置的求和。检查配置是否有效需要 \(O(L)\) 时间。因此，计算单行子问题需要 \(O(2^{3L} L)\) 时间，总运行时间为 \(O(2^{3L} L H)\) 次操作。虽然可能的配置数量可能是指数级的（最多 \(2^{LH}\)），但我们只关心对 1337 取模的结果，这意味着所有数字都是固定大小的，因此对这些数字的算术运算是常数时间。最终运行时间为 \(O(2^{3L} L H)\)。

四部分解答：

(a) 子问题：\(f(h, u, v)\) 表示前 \(h\) 行中，第 \((h-1)\) 行配置为 \(u\)、第 \(h\) 行配置为 \(v\) 的有效配置数（对 1337 取模）。

(b) 递推关系与基本情况：当 \(h > 2\) 时，\(f(h, v, w) = \sum_{u: u,v,w \text{ 有效}} f(h-1, u, v) \bmod 1337\)。基本情况为 \(f(2, u, v) = 1\) 当且仅当 \(u, v\) 有效，否则为 0。不需要其他基本情况。

(c) 正确性证明：见上述正确性证明。

(d) 运行时间与空间复杂度：运行时间为 \(O(2^{3L} L H)\)。对于空间复杂度，共有 \(O(H \cdot 2^{2L})\) 个子问题（\(H\) 行，第 \((H-1)\) 行有 \(2^L\) 种设置，第 \(H\) 行有 \(2^L\) 种设置）。每个子问题是对 1337 取模的配置数，上界为 1337，因此总空间为 \(O(2^{2L} H)\)。注意，由于每个子问题仅依赖于前一行的子问题，我们可以通过回收前面行的空间将空间减少 \(H\) 倍，降至 \(O(2^{2L})\)。

(a) 算法描述：设 \(f_0[v][i]\) 表示以 \(v\) 为根的子树中，大小为 \(i\) 且 \(v\) 不在集合中的最大权重独立集。设 \(f_1[v][i]\) 表示以 \(v\) 为根的子树中，大小为 \(i\) 的整体最大权重独立集。最终答案为 \(f_1[r][k]\)。

对于每个 \(v, i\)，我们用以下递推关系计算 \(f_b[v][i]\)（其中 \(b \in \{0, 1\}\)）：

\[ f_0[v][i] = \max_{0 \leq j \leq i} f_1[\text{left}(v)][j] + f_1[\text{right}(v)][i - j] \]

\[ f_1[v][i] = \max\left(f_0[v][i], \max_{0 \leq j \leq i-1} A[v] + f_0[\text{left}(v)][j] + f_0[\text{right}(v)][i - j - 1]\right) \]

其中 \(\text{left}(v)\) 和 \(\text{right}(v)\) 分别是 \(v\) 的左子节点和右子节点。这里的思想是需要在左右子树之间"分配"独立集中的 \(k\) 个节点，同时跟踪 \(v\) 是否在独立集中以保持顶点独立性。

基本情况：设 \(f_b[v][0] = 0\)（\(b \in \{0, 1\}\)），对于每个叶节点 \(\ell\) 和 \(j \in [k]\)，设 \(f_0[\ell][j] = 0\)，\(f_1[\ell][j] = A[\ell]\)。

子问题的求解顺序是从叶节点到根节点，即后序遍历。

运行时间分析：对于每个 \(b \in \{0, 1\}\)，共有 \(nk\) 个子问题（\(v\) 可取 \(n\) 个值，\(j\) 可取 \(k\) 个值）。每个子问题需要 \(O(k)\) 时间，因为需要在 \(j \in [i]\) 或 \(j \in [i-1]\) 上取最大值。因此总运行时间为 \(2 \cdot nk \cdot O(k) = O(nk^2)\)。

(b) 转换方法：对于 \(T\) 中每个有超过两个子节点的节点 \(v\)，添加一个权重为 0 的虚拟节点作为 \(v\) 的右子节点，并将 \(v\) 除最左边外的所有子节点连接到该虚拟节点。递归执行此修改将得到一棵二叉树，同时添加最多 \(O(N)\) 个虚拟节点。

例如，如果 \(T\) 是以下树（其中 \(A[v_i] = i\)）：

v1
|\
v2 v3 v4 v5

按照描述的过程后，我们将得到以下二叉树 \(T_b\)：

v1
|\
v2 vd
   /\
  vd v3
     /\
    v4 v5

其中所有虚拟节点 \(v_d\) 的 \(A[v_d] = 0\)。

(c) 推广到一般情况：为了解决一般 \(T\) 的问题，我们想用 (b) 将其转换为二叉树 \(T_b\)，然后在 \(T_b\) 上运行 (a) 的算法。但实际上我们必须调整 (a) 的递推关系以考虑新添加的虚拟节点！

为此，我们需要定义虚拟节点的子问题，使其传播其父节点分配给它们的"状态"（即它们是否在 \(k\)-独立集中）。例如，在 (b) 的树示例中，我们希望如果 \(v_1\) 包含在 \(k\)-独立集中，则我们的算法将通过 \(v_d\) 传播非包含性，以确保 \(v_3, v_4, v_5\) 都不被包含。

算法描述：我们重新定义子问题如下：

• \(f_0[v][i]\) = 以 \(v\) 为根的子树中，大小为 \(i\) 且 \(v\) 不在集合中的最大权重独立集

• \(f_1[v][i]\) = 以 \(v\) 为根的子树中，大小为 \(i\) 且 \(v\) 在集合中的最大权重独立集

• \(f[v][i]\) = 以 \(v\) 为根的子树中，大小为 \(i\) 的整体最大权重独立集

最终答案为 \(f[r][k]\)，其中 \(T_b\) 由 (b) 的过程从 \(T\) 得到。然后我们修改递推关系如下：

\[ f_0[v][i] = \begin{cases} \max_{0 \leq j \leq i} f[\text{left}(v)][j] + f[\text{right}(v)][i - j] & \text{if } A[v] \neq 0 \\ \max_{0 \leq j \leq i} f_0[\text{left}(v)][j] + f_0[\text{right}(v)][i - j] & \text{if } A[v] = 0 \end{cases} \]

\[ f_1[v][i] = \begin{cases} \max_{0 \leq j \leq i-1} A[v] + f_0[\text{left}(v)][j] + f_0[\text{right}(v)][i - j - 1] & \text{if } A[v] \neq 0 \\ \max_{0 \leq j \leq i} f_1[\text{left}(v)][j] + f_1[\text{right}(v)][i - j] & \text{if } A[v] = 0 \end{cases} \]

\[ f[v][i] = \max(f_0[v][i], f_1[v][i]) \]

基本情况和子问题的求解顺序与 (a) 相同。

运行时间分析：将 \(T\) 转换为 \(T_b\) 需要 \(O(|V| + |E|) = O(n)\) 时间。注意 \(T_b\) 比 \(T\) 多 \(O(n)\) 个节点（以及相应边），因此在 \(T_b\) 上运行 (a) 仍需要 \(O(nk^2)\) 时间。因此总运行时间为 \(O(n) + O(nk^2) = O(nk^2)\)。

替代解法：实际上有一种方法可以直接解决一般 \(T\) 的问题，即无需转换为二叉树。设 \(f_0\) 和 \(f_1\) 与 (a) 中定义相同。注意，为了计算 \(f_b[v][i]\)（\(b \in \{0, 1\}\)），我们需要考虑 \(v\) 的每个子节点的 \(f_{\bar{b}}\) 值。然而，如果 \(v\) 有多个子节点，我们还需要考虑在其子树之间分配 \(i\) 的所有可能方式。一种方法是计算额外的 DP 子问题。

设 \(c_\alpha\) 为 \(v\) 的第 \(\alpha\) 个子节点（按某种顺序）。定义 \(g_1[v][\alpha][i]\) 为 \(c_0, \ldots, c_\alpha\) 的子树并集中的最大权重 \(k\)-独立集。类似地定义 \(g_0[v][\alpha][i]\)，附加约束为 \(c_0, \ldots, c_\alpha\) 都不在集合中。

那么我们有以下递推关系：

\[ g_b[v][\alpha][i] = \begin{cases} f_b[c_0][i] & \text{if } \alpha = 0 \\ \max_{0 \leq j \leq i} g_b[v][\alpha - 1][j] + f_b[c_\alpha][i - j] & \text{if } \alpha > 0 \end{cases} \]

对于 \(b \in \{0, 1\}\)。假设 \(v\) 有 \(d(v)\) 个子节点。在如上计算 \(v\) 的 \(g\) 后，我们可以如下计算 \(i > 1\) 时的 \(f[v][i]\)：

\[ f_0[v][i] = g_1[d(v)][i] \]

\[ f_1[v][i] = A[v] + \max(f_0[v][i], g_0[d(v)][i - 1]) \]

运行时间分析：虽然 \(g_b\) DP 看起来像三维数组，但对于每个 \(v\) 只有 \(d(v)\) 个可能的 \(\alpha\) 值。由于 \(\sum_v d(v) = n - 1\)，我们只需要计算 \(O(nk)\) 个 \(g_b\) 值。因此，包括 \(g_b\) 在内，共有 \(O(nk) + O(nk) = O(nk)\) 个子问题，每个子问题需要 \(O(k)\) 时间。这产生总运行时间 \(O(nk) \cdot O(k) = O(nk^2)\)。

算法思路：

1. DFS 后序编号：对树进行 DFS，计算每个节点的后序编号 post[u]。对于边 \((u, v)\)，若 \(v\) 是 \(u\) 的子节点，则 post[v] < post[u]。

2. 自顶向下 DP：定义 dp[u] 为二元组 (最大权重, 是否选择 u)：

• 选择 \(u\)：权重为 \(w[u] + \sum_{v \in \text{grandchildren}(u)} \text{dp}[v].\text{weight}\)

• 不选择 \(u\)：权重为 \(\sum_{v \in \text{children}(u)} \text{dp}[v].\text{weight}\)

• 取两者较大值

1. 回溯重建：从根节点开始，根据 dp[u] 中的选择标志决定：

• 若选择 \(u\)，将 \(u\) 加入独立集，递归检查孙节点

• 若不选择 \(u\)，递归检查子节点

代码实现：

def max_independent_set(adjacency_list, weights):
    """
    Return a list containing the vertices in the maximum weighted independent set.
    """
    n = len(weights)
    if n == 0:
        return []

    # DFS post number computation (modified from HW4)
    def get_post(adj_list):
        time, post, visited = 1, {}, set()
        unvisited = lambda x: x not in visited
        def explore(u):
            nonlocal time
            visited.add(u)
            time += 1
            for v in filter(unvisited, adj_list[u]):
                explore(v)
            post[u] = time
            time += 1
        for i in filter(unvisited, range(len(adj_list))):
            explore(i)
        return post

    post = get_post(adjacency_list)

    # helper function to get the children of node u based on DFS post numbers
    def get_children(u):
        yield from filter(lambda v: post[v] < post[u], adjacency_list[u])

    def get_grandchildren(u):
        for v in get_children(u):
            yield from get_children(v)

    # initialize the DP array
    dp = [None] * n

    def independent_set_helper(u):
        if dp[u] is None:
            choices = (
                (weights[u] + sum(independent_set_helper(v)[0] for v in get_grandchildren(u)), True),
                (sum(independent_set_helper(v)[0] for v in get_children(u)), False),
            )
            dp[u] = max(choices)
        return dp[u]

    # compute the DP values (root doesn't really matter, we choose 0 for ease)
    independent_set_helper(0)

    # reconstruct the sequence starting from the root
    independent_set = []
    to_check = [0]
    while to_check:
        u = to_check.pop()
        if dp[u][1]:
            # u is included in the independent set, so its children are not.
            independent_set.append(u)
            to_check.extend(get_grandchildren(u))
        else:
            # u is not included in the independent set, so check its children.
            to_check.extend(get_children(u))

    return independent_set

正确性证明（归纳法）：

• 基础情况：叶子节点 \(u\)，dp[u] = max((w[u], True), (0, False))，显然最优。

• 归纳假设：假设对于 \(u\) 的所有子节点和孙节点，dp 值已正确计算。

• 归纳步骤：对于节点 \(u\)，若选择 \(u\) 则不能选择子节点，总权重为 \(w[u]\) 加所有孙节点的最优解之和；若不选择 \(u\) 则总权重为所有子节点的最优解之和。两者取最大即为以 \(u\) 为根的子树的最优解。

复杂度分析：

• 时间：\(O(n)\)，每个节点仅访问一次，子节点和孙节点的枚举总计 \(O(n)\)。

• 空间：\(O(n)\)，DP 数组和递归栈。

算法思路：

1. DP 状态定义：dp[(S, i)] 表示从城市 \(i\) 出发，经过集合 \(S\) 中所有城市后返回起点（城市 0）的最短距离。

2. 状态转移：

\[\text{dp}[(S, i)] = \min_{\text{city} \in S} \left\{ \text{dist}[i][\text{city}] + \text{dp}[(S \setminus \{\text{city}\}, \text{city})] \right\}\]

边界条件：\(S = \emptyset\) 时，dp[(S, i)] = dist[0][i]（直接返回起点）。

1. 回溯重建：用字典 prev[(S, i)] 记录使代价最小的城市，从初始状态 \((\{1, ..., n-1\}, 0)\) 开始逐步重建路径。

代码实现：

def tsp_dp(dist_arr):
    """Compute the exact solution to the TSP using dynamic programming and returns the optimal path."""
    n = len(dist_arr)
    dp = {}
    prev = {}

    def tsp_helper(S, i):
        if (S, i) in dp:
            return dp[(S, i)]
        if S == frozenset():
            return dist_arr[0][i]  # Return to the starting city
        min_cost = float('inf')
        prev_city = None
        for city in S:
            cost = dist_arr[i][city] + tsp_helper(S.difference({city}), city)
            min_cost, prev_city = min((min_cost, prev_city), (cost, city))
        dp[(S, i)] = min_cost
        prev[(S, i)] = prev_city
        return min_cost

    best_distance = tsp_helper(frozenset(range(1, n)), 0)

    # Backtracking to reconstruct tour
    S = frozenset(range(1, n))
    city = 0  # start at the origin
    tour = [0]
    while S:
        city = prev[(S, city)]
        tour.append(city)
        S = S.difference({city})

    return tour

正确性证明（归纳法）：

• 基础情况：\(S = \emptyset\) 时，唯一选择是返回起点，代价为 dist[0][i]，显然最优。

• 归纳假设：假设对于所有真子集 \(S' \subsetneq S\) 和任意城市 \(i\)，dp[(S', i)] 已正确计算。

• 归纳步骤：对于状态 \((S, i)\)，路径必须从 \(i\) 前往 \(S\) 中某城市 city，再从 city 经过 \(S \setminus \{\text{city}\}\) 返回起点。由归纳假设，子问题最优，故取最小值即为 \((S, i)\) 的最优解。

复杂度分析：

• 时间：\(O(n^2 \cdot 2^n)\)，共有 \(O(n \cdot 2^n)\) 个状态，每个状态转移耗时 \(O(n)\)。

• 空间：\(O(n \cdot 2^n)\)，存储 DP 表和前驱字典。