斯坦福算法专项课程Course3 week1习题解析

这一部分将带来Course3 week1的习题解析。

选择题

选择题 1

我们作为输入给出了一组$n$请求（例如，使用礼堂），对于每个请求$i$有已知的开始时间$s_i$和完成时间$t_i$。假设所有开始和结束时间都是不同的。如果两个请求在时间上重叠，则会发生冲突 ——如果其中一个请求在另一个请求的开始和结束时间之间开始。我们的目标是选择不包含冲突的给定请求的最大子集。（例如，给定三个请求的时间区间为$[0，3]$， $[2，5]$，和$[4，7]$，我们想要返回第一个和第三个请求。）我们的目标是使用以下形式为此问题设计一个贪心算法：在每次迭代时，我们选择一个新请求$i$，将其加入到目前为止的解决方案，并在未来删除所有与之冲突的请求。

以下哪种贪婪规则可以保证始终能够计算出最佳解决方案？

• 在每次迭代中，选择与剩余请求冲突最少的剩余请求（重复时任意选取）。

• 在每次迭代时，使用最早的开始时间选择剩余的请求。

• 在每次迭代中，选择需要最少时间的剩余请求（具有最小$t_i-s_i$的剩余请求）（重复时任意选取）。

• 在每次迭代时，选择最早完成时间的剩余请求。

答案为最后一项，每次选择完成时间最早的请求。

下面证明这个结论，假设按照该贪心算法得到的请求数为$s$，实际的最大请求数为$t$，下面利用反证法证明$s= t$，假设$s< t$，设贪心算法得到的安排为（按结束时间排序）

$$a_1,...,a_s$$

实际的最优安排为（按结束时间排序）

$$b_1,...,b_t$$

因为$s<t$，那么必然存在$i$，使得

$$a_k = b_k (k<i)\\ a_{i} \neq b_{i}$$

由贪心算法的定义可知，我们必然有$a_i$的结束时间早于$b_i$的结束时间，以此类推可得$a_{i+j}$的结束时间都早于$b_{i+j}$的结束时间，因此$a_s$的结束时间早于$b_s$的结束时间，而$s<t$，所以$b_{s+1}$必然可以安排在$a_s$之后，这就贪心算法的定义相矛盾，从而$s=t$

选择题 2

我们作为输入给出了$n$组工作，工作$j$有一个处理时间$p_j$止日期$d_j$。回想一下视频讲座中完成时间$C_j$的定义。给定一个时间表（即工作的排序），我们定义工作$j$在工作完成的截止日期之后的延迟时间$l_j$为$C_j -d_j$，如果$C_j \le d_j$则为$0$。我们的目标是尽量减少最大的延迟的时间$\max_j l _j$

以下哪个贪婪规则会产生最小化最大延迟的排序？您可以假设所有处理时间和截止日期都不同。

• 没有其他答案是正确的。

• 按处理时间$p_j$的递增顺序安排请求。

• 按$d_jp_j$的递增顺序安排请求。

• 按截止日期$d_j$的递增顺序安排请求。

答案为最后一项，下面利用课件中的交换法证明该结论，依旧利用课件中的图：

假设左边为按照$d_k$递增排序得到的安排，现在交换相邻$i,j$（交换前$d_i < d_j$），记$i$之前的完成时间为$C_0$，那么交换前的$C_k -d_k$为

$$i:C_0 + p_i - d_i \\ j:C_0 + p_i+p_j - d_j$$

因为$d_i < d_j$，所以

交换后：

$$i:C_0 + p_j - d_j \\ j:C_0 + p_i+p_j - d_i$$

利用$d_i < d_j$，所以

$$C_0 + p_i+p_j - d_i > C_0 + p_i+p_j - d_j \\ C_0 + p_i+p_j - d_i > C_0 + p_i - d_i$$

这说明交换为$j$的延迟时间大于等于交换前$i,j$中的最大延迟时间，而交换$i,j$是不改变其余的延迟时间的，所以这样交换为的最大延迟时间的最小值会增加，从而原贪心算法是正确的。

选择题 3

在这个问题中，您将获得一个图$ T =(V，E)$作为输入，该图是一棵树（即，$T$是无向的，连通的和非循环的）。$T$的一个完美匹配是边的子集$F\subset E$，使得每个顶点$v \in V$是恰好是$F$中某条边的终点。同样地，$F$中每个顶点恰有$T$中一条边。例如，当且仅当路径图具有偶数个顶点时，路径图才具有完美匹配。（更详细的描述)）

考虑以下两种算法，试图确定给定树是否具有完美匹配。图中顶点的度数是入射到它的边的数量。（这两种算法的区别仅在于选择第5行$v$的选择。）

算法A：

当T至少有一个顶点：

  如果T没有边： 

    停止并输出“T没有完美匹配。”

  否则：

    设v是T中度数最大的顶点。

    选择v的任意相邻边e。

    从T中删除e及其两个端点

[while循环结束]

暂停并输出“T具有完美匹配”。

算法B：

当T至少有一个顶点：

  如果T没有边： 

    停止并输出“T没有完美匹配。”

  否则：

    设v是T中具有最小非零度数的顶点。

    选择v的任意相邻边e。

    从T中删除e及其两个端点

[while循环结束]

暂停并输出“T具有完美匹配”。

算法是否正确？

• 算法B总是正确地确定给定的树图是否具有完美匹配; 算法A没有
• 两种算法都不能始终正确地确定给定的树图是否具有完美匹配
• 两种算法总是正确地确定给定的树图是否具有完美匹配
• 算法A总是正确地确定给定的树图是否具有完美匹配; 算法B没有

选择题 4

考虑一个无向图$G=(V,E)$的每一个边$e\in E$有给定的花费$c_e$。假设所有边的花费都是正的并且不同。让$T$是$G$的最小的生成树和$P$为$s$到$t$的最短路径。现在假设每个边$e$的花费增加了$1$变成$c_e+1$。称新图为$G’$。关于$G’$以下哪一项是正确的？

• $T$ 始终是最小的生成树，$P$永远是最短的$s-t$路径
• $T$ 可能不是最小的生成树，$P$可能不是最短的$s-t$路径
• $T$ 可能不是最小的生成树，$P$永远是最短的$s-t$路径
• $T$ 始终是最小的生成树，$P$可能不是最短的$s-t$路径

由于生成树的边的数量固定，所以每条边增加$1$后每个生成树增加的数量相同，从而$T$始终为最小生成树，但是最短路径和边的数量有关，如果每条边增加$1$之后就不一定为最短路径了

选择题 5

假设$T$是连接图$G=(V,E)$的最小生成树。令$H$是$G$的一个连通的诱导子图。（选择子集$S\subseteq V$，选择$E$中两个顶点都在$S$中的子图$H$，另外，假设$H$连通）以下哪一项是关于$T$在$H$中的边是正确的？假设边的花费是不同的。[选择最强的真实陈述。]

• 对每一个$G$和$H$和$H$的生成树$T_H$，$T_H$至少缺少$T$中一条边
• 对每一个$G$和$H$，这些边形成$H$的一个最小的生成树
• 对每一个$G$和$H$，这些边形成$H$的一个的生成树
• 对每一个$G$和$H$，这些边包含在$H$的某个最小生成树中

答案为最后一项，可以按如下方式考虑：假设Prim算法的起点选为$H$中某一点$h_0$，第一步会选择离$h_0$最近的一点$h_1$，如果$h_1\in H$，那么$h_0-h_1$显然同时属于$H$中的最小生成树以及$G$中的最小生成树，这个步骤可以一直持续下去，从而得到最后一项

下面一题是老版课程的选择题，coursera上没有

选择题 6

考虑一个无向图$G=(V,E)$，边$e\in E$具有权重$c_e $。最小的瓶颈生成树$T$是一种生成树，可以最大限度地降低最大边权重$\max_{e \in T} c_e$。下列哪项为真？假设边的权重是不同的。

• 最小瓶颈生成树并不总是最小生成树，并且最小生成树并不总是最小瓶颈生成树。
• 最小瓶颈生成树始终是最小生成树，最小生成树始终是最小瓶颈生成树。
• 最小瓶颈生成树始终是最小生成树，但最小生成树并不总是最小瓶颈生成树。
• 最小瓶颈生成树并不总是最小生成树，但最小生成树始终是最小瓶颈生成树。

最小瓶颈生成树可能会选择$5,7,9$三条边，而最小生成树可能会选择$4,6, 10$，所以最小瓶颈生成树并不总是最小生成树，反过来可以利用反证法证明，记$T$为最小生成树，$T’$为最小瓶颈生成树，如果结论不成立，那么：

$$\max_{e \in T} c_e > \max_{e \in T'} c_e$$

记

$$e= \arg \max _{e \in T} c_e ,对应节点为v_1,v_2\\ e'= \arg \max _{e \in T'} c_e,对应节点为v_1',v_2'$$

那么

$$c_e > c_{e'}$$

按课本中证明方法将$e’$加入，$v_1,v_2,v_1’,v_2’$会形成环，在这个环中去除$e$得到依旧是一颗生成树，并且总权重更小，这就小最小生成树的定义矛盾，从而最小生成树一定是最小瓶颈生成树