斯坦福算法专项课程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$,设贪心算法得到的安排为(按结束时间排序)

实际的最优安排为(按结束时间排序)

因为$s<t$,那么必然存在$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$为

因为$d_i < d_j$,所以

交换后:

利用$d_i < d_j$,所以

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

选择题 3

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

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

算法A:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
当T至少有一个顶点:

如果T没有边:

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

否则:

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

选择v的任意相邻边e。

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

[while循环结束]

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

算法B:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
当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’$为最小瓶颈生成树,如果结论不成立,那么:

那么

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