算法导论35 Problems 答案

35-1

a

首先先为这个问题构造出一个判定性问题：对于这组物体$T={s_i}$，是否至多可以用$k$个大小为$1$的箱子，可以将这些物品全部装入其中。假设判定性问题的语言定义为BIN：

$$\begin{aligned} \text{BIN}=\{\langle T, k\rangle:&T\text{ is a set of values in }(0,1),\\ &k \ge 1\text{ is an integer, and}\\ &\text{all objects in $T$ can be place can be placed in $k$ or fewer bins.} \end{aligned}$$

注意到BIN问题并没有限制每个箱子有多满。BIN问题的其中一个特殊问题EX-BIN，则要求了其中一个箱子恰好装满：

$$\begin{aligned} \text{EX-BIN}=\{\langle T, k\rangle:&T\text{ is a set of values in }(0,1),\\ &k \ge 1\text{ is an integer, and}\\ &\text{all objects in $T$ can be place can be placed in $k$ or fewer bins, at least one of them is exactly full.} \end{aligned}$$

首先证明EX-BIN属于$\text{NP}$。考虑某个问题实例$\langle T, k\rangle$，以及其某个证据，即一个装箱方案$P$，检验程序只需要检验$P$是否大小至多为$k$，并且对于$P$中的每个箱子，是否所有物品大小之和都不超过$1$即可。检验程序可以在多项式内完成检验，因此EX-BIN属于$\text{NP}$。

接下来证明EX-BIN是NP困难的，考虑使用子集和问题进行规约，即证明$\text{SUBSET-SUM}\le_P\text{EX-BIN}$。对于SUBSET-SUM问题中的任意一个实例$\langle S, t\rangle$，规约算法$F$构造出如下一个EX-BIN问题的实例$\langle T,k\rangle$，使得$S$包含一个和为$t$的子集，当且仅当物品$T$可以装在$k$个箱子中，并且其中一个箱子恰好装满。

规约过程是：令$T={x/t:x\in S},k=|S|$。可见构造出集合$S$所需要花费的时间是多项式的。

现在证明$S$包含一个和为$t$的子集，当且仅当物品$T$可以装在$k$个箱子中，并且其中一个箱子恰好装满。

充分性：如果$S$包含一个子集和为$t$的子集$S’$，那么在$T$对应的子集$T’={x/t:s\in S’}$中，其和值为$1$。由于$k=|S|$，因此这意味着$S$中所有物品必定能够被装得下，因此$T’$以及其它物品各自放在一个盒子中，是问题EX-BIN的一个解。

必要性：可见这$|S|$个盒子必定能够装满这$|S|$个物品。如果存在一个子集$T’\subseteq T$，其中恰好能够装在一个盒子中，那么对$T’$构建对应在$S$中的子集$T’={xt:x\in T’}$，那么$S’$是$S$的一个和为$t$的子集。

因此$\text{SUBSET-SUM}\le_P\text{EX-BIN}$。由于SUBSET-SUM是NP完全的，那么EX-BIN是NP困难的，也是NP完全的。从而得知它的一般化问题BIN也是NP完全的，因此原问题是NP困难的。

b

由于所有物品总共的大小为$S$，然而每个箱子的大小为$1$，因此哪怕是最优的解法，都需要保证箱子的总大小不低于物品的总大小。因此
最优解法至少需要$\lceil S\rceil S$个箱子。

c

将使用反证法来证明。不失一般性，假设某个时刻中存在两个箱子$B_1,B_2$，它们都是不到半满的。并且不失一般性，在这个时刻之前，假设在$B_1$放置最后一个物品时刻后，有一个新物品$s_i$放置到了$B_2$。由于放置$s_i$到$B_2$后，$B_2$仍然不到半满的，因此$s_i< 0.5$。在放置$s_i$到$B_2$之前，由于$B_1$也尚未达到半满，因此按照首先适合的策略，$s_i$应该放在$B_1$而不是$B_2$。因此放置$s_i$到$B_2$违背了首先适合策略。因此原结论成立。

d

按照题目35-1-c的结论，由于至多一个箱子不是半满的，其余箱子都至少是半满的，因此哪怕除了最后一个箱子，其余箱子都至少需要装上大小之和为$0.5$的物品。因此这种首先适合策略最多只需要$\lceil S/0.5\rceil=\lceil 2S\rceil$个箱子。

e

根据题目35-1-d可知首先适合算法所求出的解至多使用$\lceil 2S\rceil$个箱子；并且根据题目35-1-b可知最优解至少使用$\lceil S\rceil$个箱子。因此首先适合算法的近似比至多为$\lceil 2S\rceil/\lceil S\rceil\le2\lceil S\rceil/\lceil S\rceil=2$，即它是一个$2$近似比的算法。

f

装箱问题的首先适应算法由BIN-PACKING-FIRST-FIT给出。由于这个算法每次都是按顺序寻找第一个能够放置它的算法，因此其时间复杂度为$O(n^2)$。

BIN-PACKING-FIRST-FIT(S, n)
  let A be a new array by set
  let sum be a new array by 0
  for i = 1 to n
    index = -1
    for j = 1 to A.size
      if sum[j] + S[i] <= 1
      sum[j] = sum[j] + S[i]
      index = j
      break
    if index == -1
      // 需要另开箱子
      INSERT(A, Ø)
      INSERT(sum, S[i])
      index = A.size
    A[index] = A[index] ⋃ {S[i]}
  return A

另外一种解法可以使用最小堆进行解决，每次选择现有的并且占用容量最小的箱子，装一个物品进去。如果装不下，那么再新开一个箱子。这个改编后的首先适应算法由BIN-PACKING-FIRST-FIT'给出，其时间复杂度为$O(n\lg n)$。

BIN-PACKING-FIRST-FIT'(S, n)
  let A be a new array by set
  let Q be a new array
  // 堆中的每个节点包含两个属性key和id，其中key表示节点
  for i = 1 to n
    if Q.qize == 0 or MIN-HEAP-MINIMUN(Q).key + S[i] > 1
      INSERT(A, Ø)
      let z be a new node
      z.id = A.size
      z.key = S[i]
      MIN-HEAP-INSERT(A, z, n)
      index = z.id
    else
      z = MIN-HEAP-EXTRACT-MIN(Q)
      z.key = z.key + S[i]
      index = z.id
      MIN-HEAP-INSERT(A, z, n)
    A[index] = A[index] ⋃ {S[i]}
  return A

35-2

a

假设$G$中有一个大小为$m$的最大团$C$，令$C^{(k)}$表示$C$中顶点的所有有序$k$元组的构成的集合，可以知道$C^{(k)}\subseteq V^k$，并且$C^{(k)}$是$G^{(k)}$的一个最大团，其大小为$m^k$。因为对于任意$u^{(k)},v^\in C^{(k)},\forall i\in[1,k]$，都有$(u_i^{(k)},v_i^{(k)})\in E$，所以$(u^{(k)},v^)\in E^{(k)}$。故$C^{(k)}$是$G^{(k)}$中一个大小为$m^k$的团。

接下来证明$G^{(k)}$中最大团的大小为$m^k$，使用归纳法来证明。

当$k=1$时，$V^{(1)}=V,E^{(1)}=E$，那么$G^{(1)}=G$，因此$G^{(1)}$的最大团大小为$m$。

当$k>1$时，假设图$G^{(k-1)}$的最大团大小为$m^{k-1}$。令$u’^{(k)}\in V^{(k-1)}$是节点$u^{(k)}$的前$k-1$个元素所构成的节点，如果$(u^{(k)},v^{(k)})\in E^{(k)}$，那么$(u’^{(k)},v’^{(k)})\in E^{(k-1)}$。假设$G^{(k)}$存在一个团$C^{(k)}$，其大小为$c$，满足$c>m^k$，那么令$C’={u’^{(k)}\mid u^{(k)}\in C^{(k)}}$，可见$C’$是图$G^{(k-1)}$中的一个团，按照假设，$|C’|\le m^{k-1}<c/m$。由于$C’$中的任意一个节点都是由$C$中的每个节点的前$k-1$个元素得来，因此$C$中的所有节点的第$k$个元素必须有超过$m$种不同的选择才能使$C’$的大小超过$m^{k}$。如果是这样，那么按照$G^{(k)}$的定义，意味着$G$有一个大小超过$m$的团，这和最大团大小为$m$矛盾，因此原结论成立。

b

假设现在存在一个近似比为常数$\rho$的算法$A$用于找出一个图的团，令图$G=(V,E)$，假设其最大团的大小为$m$。按照整数$k$构造出图$G^{(k)}$后，通过对图$G^{(k)}$使用算法$A$，可以找到一个大小为$n$的团，并满足$m^k/n\le c$。那么这将在图$G$中可以找到一个大小为$n^{1/k}$的团，其中满足$m/c^{1/k}\le n^{1/k}$。对于给定的一个近似参数$\epsilon$，令$k=1/\log_c (1+\epsilon)$，那么算法$A$就能找到图$G$一个接近$\dfrac{m}{1+\epsilon}$的团，这也符合了近似参数$\epsilon$越低，找到的团越大的直觉。

接下来证明$k$是$1/\epsilon$的一个多项式。可以知道：

$\begin{aligned}
k&=1/\log_c(1+\epsilon)\
&=\dfrac{\ln c}{\ln 1+\epsilon}\
&\ge \dfrac{\ln c}{\epsilon}
\end{aligned}$

因此，对图$G^{(k)}$，其中$k=1/\log_c(1+\epsilon)$使用算法$A$求取最大团，从而构建出图$G$的一个团$C$的算法$A’$是一个$1+\epsilon$近似的算法。由于这个近似模式是输入规模的多项式，也是一个$1/\epsilon$的多项式，因此这是一个完全多项式时间近似模式。

35-3

一个贪心的带权集合覆盖启发式算法是：每次选择单位费用下能够加入尽量多元素到$U$中的集合。更具体的，这个算法的伪代码由GREEDY-SET-COVER-WEIGHTED给出。

GREEDY-SET-COVER-WEIGHTED(X, F, w)
  U_0 = X
  C = Ø
  i = 0
  while U_i != Ø
    select select S ∈ F that maximizes |S ∩ U_i| / w(S)
    U_{i + 1} = U_i - S
    C = C ⋃ {S}
    i = i + 1
  return C

接下来证明这个算法具有近似比$H(d)$，其中$d=\max{|S|:S\in \mathcal{F}}$。证明过程参考了这篇文章

令$c_x$表示分配给元素$x$的代价。每一个元素$x$在第一次被某个集合$S_i$覆盖时，才会被分配代价，其分配的代价为

$$c_x=\dfrac{w_i}{|S_i-(S_1\cup S_2\cup\dots \cup S_{i-1})|}$$

直观上，这个代价比例就是为了使用集合$Si$覆盖$S_i-(S_1\cup S_2\cup\dots \cup S{i-1})$中的每个元素时所均摊的代价。

令$\mathscr{C}$是一个由GREEDY-SET-COVER-WEIGHTED产生的带权集合覆盖，$\mathscr{C}^{\ast}$是一个带权最优集合覆盖。

按照代价等价的定义，有

$$\sum_{S_i\in \mathscr{C}}w_i=\sum_{x\in X}c_x$$

考虑任意在$\mathscr{C}^{\ast}$中选中的一个集合$Si={x_k,x{k-1},\dots,x1}$。不失一般性，假设这个贪心算法按照$x_k,x{k-1},\dots,x1$的顺序依次覆盖这些元素。在这个算法从$x_j$开始覆盖$S_i$的元素时，$S_i$中至少仍然有$j$个元素仍然未被覆盖。因此，如果贪心算法在某个迭代时刻选择了集合$S_i$，那么对于$\forall p\in[1,k],c{xp}\le w_i/j$，即贪心算法将会最多会为每个元素支付$w_i/j$的代价用于覆盖$S_i$中剩余的元素。这意味着元素$x_j$被使用了$w_i/j$代价进行覆盖。由于$j$的取值从$1$至多为$d$，因此计算$\displaystyle{H(d)=\sum{i=1}^d\dfrac{1}{i}}$，以求覆盖到任何情况。

因此一个贪心算法的权值之和最多为$\displaystyle{\sum{S_i\in \mathscr{C}^{\ast}}w_iH(d)=H(d)\cdot{\sum{S_i\in \mathscr{C}^{\ast}}w_i}}$，因此它是一个$H(d)$近似的算法。

35-4

a

考虑图$G=(V,E),V={a,b,c,d},E={(a,b),(c,d),(b,c)}$。那么其中一个极大匹配是${(b,c)}$，但它不是一个最大匹配（最大匹配是${(a,b),(c,d)}$）。

b

只需要将算法APPROX-VERTEX-COVER修改成以边返回即可。题目35.1-2证明了这个算法生成的边集是一个极大匹配。修改后的算法由程序MAXIMAL-MATCHING给出。

MAXIMAL-MATCHING(G)
  M = Ø
  E' = G.E
  while E' ≠ Ø
    let (u, v) be an arbitrary edge of E'
    M = M ∪ {(u, v)}
    remove from E' edge (u, v) and every edge incident on either u or
  return M

c

由于$G$中的一组匹配$|M|$，任意两条边都不和同一顶点关联。因此至少需要$|M|$个节点才能覆盖这$|M|$条边，故$G$的一个最大匹配的规模是$G$中任何顶点覆盖规模的下界。

d

这意味着这个图只有一些孤立节点，没有边。如果仍然存在一条边$(u,v)$，那么说明匹配$M$不是一个极大匹配，可以把$(u,v)$加入到$M$中。

e

根据题目35-4-d的结论，一组极大匹配中的所有节点$T$，关联了$G=(V,E)$中的所有边。因此$T$是一个大小为$|T|=2|M|$的点覆盖。

f

令$|M^{\ast}|$是一组最大匹配，令$|C^{\ast}|$是一组最小点覆盖。那么根据题目34-4-c的结论，有$|C^{\ast}|\ge |M^{\ast}|$。

根据题目35-4-e的结论，$T$是$G$中的一个点覆盖，因此$|T|\ge |C^{\ast}|$。

由于$|T|=2|M|$，因此有$2|M|\ge |M^{\ast}|$，因此算法MAXIMAL-MATCHING是一个近似比为$2$的最大匹配算法。

35-5

a

由于这些调度是非抢占式的，并且一台机器完整地运行任务$J_i$需要花费$p_i$的时间。因此一个任务$J_i$的结束时间至少为$p_i$，即$C_i\ge p_i$。

由于$\displaystyle{C{\max}=\max{k=1}^m Ck}$，因此有$\displaystyle{C{\max}^{\ast}\ge \max_{k=1}^m p_k}$。

b

使用反证法证明。如果$\displaystyle{C{\max}<\dfrac{1}{m}\sum{k=1}^m pk}$，那么意味着$\displaystyle{m\cdot C{\max}<\sum{k=1}^m p_k}$。也就是说，哪怕每台机器都使用$C{\max}$的时间进行处理，都无法完成处理所有任务（因为每个任务在每台机器上需要执行的单位时间为$1$），因此这是不可能的，最终原结论成立。

c

考虑使用一个最小堆进行实现。堆中的每一个节点$x$有两个属性$id$和$key$，分别表示机器编号和当前机器完成当前任务的最后时间。每次取出堆顶的机器$m$（因为它是所有机器中，当前最早结束的），然后选择一个任务$J_i$，并赋予给机器$m$，那么将$m$对应的节点的关键字加上$p_i$后，重新加入最小堆中。

具体过程由PARALLEL-TASKS-ASSIGNED给出。由于进行了$O(n+m)$次堆操作，并且堆的大小至多为$O(m)$，因此总时间复杂度为$O((n+m)\log m)$。

PARALLEL-TASKS-ASSIGNED(J, n, m)
  let Q[1 : m] be a new array
  let L[1 : m] be a new array by empty array
  for i = 1 to m
    let Q[i] be a new node
    Q[i].id = i
    Q[i].key = 0
  BUILD-MIN-HEAP(Q, m)
  for i = 1 to n
    x = MIN-HEAP-EXTRACT-MIN(Q)
    INSERT(L[x.id], J_i)
    x = x.key + p_i
    MIN-HEAP-INSERT(Q, x, m)
  return L

d

定理26.1证明了这个问题的更一般的结论（因为这里任务间是不构成依赖的，定理26.1任务间可能会构成依赖）。

因此，根据题目35-5-a和35-5-b的结论，最终有

$\begin{aligned}
C{\max}&\le \dfrac{1}{m}\sum{k=1}^n pk+\max{p_k:1\le k\le n}\
&\le\max\left{\dfrac{1}{m}\sum{k=1}^n pk,\max{p_k:1\le k\le n}\right}+\max\left{\dfrac{1}{m}\sum{k=1}^n pk,\max{p_k:1\le k\le n}\right}\
&=2\cdot \max\left{\dfrac{1}{m}\sum{k=1}^n pk,\max{p_k:1\le k\le n}\right}\
&=2\cdot C{\max}^{\ast}
\end{aligned}$

因此这个贪心调度算法是$2$近似的。

35-6

a

令图$G=(V,E),V={a,b,c,d},E={(a,b),(b,c),(c,d)},w(a,b)=1,w(b,c)=2,w(c,d)=3$。那么对于这个边权，有$S_G=E=T_G$。图$G$和权值函数$w$为题目所求。

b

令图$G=(V,E),V={a,b,c,d},E={(a,b),(b,c),(c,d)},w(a,b)=2,w(b,c)=1,w(c,d)=3$。那么对于这个边权，有$S_G={(a,b),(c,d)}$；然而$T_G=E$，因此有$S_G\neq T_G$。图$G$和权值函数$w$为题目所求。

c

使用反正法进行证明。假设$G=(V,E)$存在一棵最大生成树的边集$T_G$以及一条边$(u,v)\in S_G$，并且$(u,v)\not\in T_G$。

不失一般性，假设$\max(u)=(u,v)$，考虑$T_G$上的一条从$u$到$v$的路径，令$x$是这条路径上和$w$相邻的那个节点（也就是这条路径的第二个节点。由于每条边都有不同边权，并且$\max(u)=(u,v)$，因此有$w(u,x)w(T_G)$，由此构造出了一棵更优的生成树，这和$T_G$是最大生成树是矛盾的。因此原结论成立。

d

可见，由于$V$中的所有节点在边集$S_G$中都有边关联着，因此有$|S_G|\ge |V|/2$，也就是有$|T_G-S_G|<|V|/2$。

按照题目35-6-c的结论，我们可以从森林$S_G$构造出一棵最大生成树。接下来证明，对于所有边$T_G-S_G$，在$S_G$中存在一组边的子集$S_G’\subseteq S_G$，且$|S_G’|=|T_G-S_G|$，在$T_G-S_G$中的每一条边$e$都和$S_G’$中的一条边$e’$对应，并且有$w(e)\le w(e’)$。

可见，为了连接森林$S_G$中的任意连通块，需要从$E$中寻找边进行连接。可见，在整个迭代过程中，每个森林的连通块中都会有一条$S_G$中的边$e’$仍未被对应。当每次从$E$中加入一条边$e$连通两个块时，总存在一条从$e$到$e’$的“增广路径”（这条路径中，$S_G$的边和非$S_G$中的边交叉出现），使得对应关系改变。因此这组对应关系总是存在的。因此得到$w(S_G’)\ge w(T_G-S_G)$。

也就是说，$w(S_G)\ge w(S_G’)\ge w(T_G-S_G)=w(T_G)-w(S_G)$，因此有$w(S_G)\ge w(T_G)/2$，原结论成立。

e

这个贪心算法首先求出$S_G$中的所有边，然后再寻找$|V|-1-|S_G|$中条边，构建出一棵近似最大生成树。按照题目35-6-c的结论，这棵最大生成树$T_G’$的权值满足$w(T_G’)\ge w(S_G)$。也就是有$w(T_G’)\ge w(T_G)/2$，因此这是一个$2$近似算法。

具体过程由APPROX-MAX-SPANNING-TREE给出，其内部使用了并查集进行实现。这个算法时间复杂度为$O(V+E)$。

APPROX-MAX-SPANNING-TREE(G, w)
  SG = Ø
  for each vertex u in G.V
    v = NIL
    max = -∞
    for each vertex x in G.Adj[u]
      if w(u, x) > max
        max = w(u, x)
        v = x
    SG = SG ∪ {(u, v)}
  TG = SG
  for each vertex u in G.V
    MAKE-SET(u)
  for each edge (u, v) in TG
    UNION(u, v)
  for each vertex u in G.V
    for each vertex v in G.Adj[u]
      if FIND-SET(u) != FIND-SET(V)
        TG = TG ∪ {(u, v)}
        UNION(u, v)
  return TG 

35-7

a

对于问题实例$I_j$，其0-1背包问题的解的选择方式（包括超出背包容量的解）一共有$2^{n-j}$个（即物品$j+1,j+2,\dots,n$可以自由选择是否存放在背包中）。对于问题实例$I_k(k>0)$，任意一个0-1背包问题的解选择方式都必定和$I_j$的解选择方式必定不一样，因为$I_k$要求选择物品$k$，$I_j$要求不选择物品$k$。因此，问题实例$I_1,I_2,\dots,I_n$一共包含了$2^{n-1}+2^{n-2}+\dots+2^{0}=2^n-1$个不同的解选择方式，它们的最优解分别由$P_1,P_2,\dots,P_n$代表。这$2^n-1$个解选择方式对应了原本问题实例$I$的解选择方式。

因此，问题$I$的0-1背包最优解必定是$P_1,P_2,\dots,P_n$之一。

b

问题实例$I_j$要求强制装入物品$j$装入背包中，那么接下来就是将物品${j+1,j+2,\dots,n}$选择装入一个大小为$W-w_i$背包中。对于这个分数背包问题实例，题目15.2-1证明了这种选择策略的贪心选择性质，从而完成了本题的证明。

c

按照题目35-7-b的思想，可以先按照$v_i/w_i$将每个物品进行排序。由于是尽量取价值较大的物品，因此只需要尽量地完整取一个价值最大物品即可。因此一直迭代下来，如果能够完整地取完一个大价值的物品，那么就继续往下取；否则只尽量取完这个物品的一部分后，算法终止。因此，最多只有一个物品会被部分装进背包。

d

对于任意0-1背包问题的解，它都是分数背包中的一个解。也就是说，对于同一问题实例下，0-1背包的解空间是分数背包解空间的子集，从0-1背包问题放松限制而来的分数背包问题将会存在更优的解，因此有$v(Q_j)\ge v(P_j)$。

接下来证明$v(R_j)\ge v(Q_j)/2$。对于问题实例$I_j$，由于物品$j$必须完整地放进这个背包，因此这个背包必定包含了价值$v_j$。由于对于其他$i>j$的物品而言，都有$v_j\ge v_i$，并且根据题目37-7-c的结论，所移除的被放进背包的物品必定是$J_i$中的某一部分。因此，移除的这一部分价值必定不会超过$v_j$。由于$R_j$相比$Q_j$而言，仅仅是移除了被部分装入的那个物品$i$，因此有$v(R_j)\ge V(Q_j)/2$。

最终证明得到$V(R_j)\ge v(Q_j)/2\ge v(P_j)/2$，

e

首先依次求解每个问题实例$I_j$的0-1背包近似解$Q_j$，然后在这$n$个近似解中选取最优的一个即可。

具体过程由APPROX-0-1-KNAPSACK-PROBLEM给出，可见这是一个$O(n^2\log n)$的简单实现，它是多项式的。

// 数组J中的每个元素J[i]都含有两个属性w和v，分别表示物品的重量和价值。
FRACTIONAL-KNAPSACK-PROBLEM-DELETE-FRACTIONAL-ITEM(J, n, W)
  sort J in descending order by J[i].v / J[i].s
  p = n
  sum = 0
  for i = 1 to n
    sum += J[i].s
    if sum > W
      p = i - 1
      break
  return J[1 : m]

APPROX-0-1-KNAPSACK-PROBLEM(J, n, W)
  sort J in ascending order by J[i].s
  let now be a new array
  for i = n down to 1
    sol = FRACTIONAL-KNAPSACK-PROBLEM-DELETE-FRACTIONAL-ITEM(J[i + 1: n], n - i, W - J[i].s)
    INSERT(sol, J[i])
    if sol is better then now
      now = sol
  return sol

接下来分析这个算法的近似比例。在每一次迭代中，都求出了问题实例$I_j$的0-1背包问题的一个近似解$Q_i$。按照题目37-7-d的结论，这是一个近似比例为$2$的解。根据题目37-7-a的结论，问题实例$I$的0-1背包问题的最优解$P$必定是某个解$P_j$，那么意味着$Q_j$也是问题实例$I$的0-1背包问题的一个近似比为$2$的解。因此算法APPROX-0-1-KNAPSACK-PROBLEM是一个0-1背包问题近似比为$2$的多项式时间算法。