中国科学院大学《计算机算法设计与分析》第三次作业

贪心

国科大(UCAS)卜东波老师算法课作业答案.

第一题

Given a list of n natural numbers $d_1, d_2,…,d_n$, show how to decide in polynomial time whether there exists an undirected graph $G = (V; E)$ whose node degrees are precisely the numbers $d_1, d_2,…,d_n$. $G$ should not contain multiple edges between the same pair of nodes, or “loop” edges with both endpoints equal to the same node.

  • The basic idea and pseudo-code

如果 $d_1, d_2,…,d_n$ 都为0,那么必然存在一个图,由n个顶点和0条边组成. 否则,将 $d_1, d_2,…,d_n$ 降序排列,使得 $d_1 \geq d_2 \geq … \geq d_n$,则存在一个图 $G$,其顶点的度恰好对应 $d_1, d_2,…,d_n$,当且仅当存在存在一个图 $G’$,其顶点的度恰好对应 $d_2 - 1, d_3 - 1, …, d_k - 1, d_{k+1} - 1, d_{k+2}, …, d_n$,其中 $k = d_1$. 也就是说,当图 $G$ 存在时,度最大的顶点 $v_1$(度为 $d_1$) 与 顶点 $v_2, v_3, …, v_{k+1}$ 都有边相连.

设 $D[1…n]$ 为序列 $d_1, d_2,…,d_n$,$n$ 为序列长度,伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function FindGraph(D[1...n], n)
if D.length < 1 then
return True
end if
D = sort(D) // 降序排列
if D[1] < 0 or D[n] < 0 then
return False
else if D[1] == 0 and D[n] == 0 // 所有顶点的度都为0
return True
else
k = D[1]
D = D.drop(D[1]) // 去掉度最大的顶点
for i = 1 to k do
D[i] = D[i] - 1
end for
FindGraph(D, n - 1)
end if
end function
  • The greedy-choice property and optimal substructure
  • Prove the correctness

以下表述中,度的序列均为降序排列.

充分性

若存在一个图 $G’$,其对应的度序列为 $d_2 - 1, d_3 - 1, …, d_k - 1, d_{k+1} - 1, d_{k+2}, …, d_n$,其中 $k = d_1$,则加入一个顶点,分别与度为 $d_2 - 1, d_3 - 1, …, d_k - 1, d_{k+1} - 1$ 的顶点连一条边,就得到了图 $G$,其对应的度序列就是 $d_1, d_2, …, d_n$.

必要性

若存在一个图 $G$,其对应的度序列为 $d_1, d_2, …, d_n$. 设 $2 \leq i \leq k + 1$,其中 $k = d_1$,假设不存在边 $(v_1, v_i)$,因为顶点 $v_1$ 的度为 $d_1$,所以必定存在一条边 $(v_1, v_j)$,其中 $k + 1 \leq j \leq n$,又因为 $d_i \geq d_j$,则必定存在一个顶点 $v$,$G$ 中包含边 $(v_i, v)$,不包含边 $(v_j, v)$,若移除边 $(v_1, v_j)$ 和 $(v_i, v)$,加入边 $(v_1, v_i)$ 和 $(v_j, v)$,此时不会改变顶点 $v_i$ 和 $v_j$ 的度,但是增加了一条从顶点 $v_1$ 到顶点 $v_2, v_3, …, v_{k+1}$ 的边,重复上述过程,最终必能使顶点 $v_1$ 与顶点 $v_1, v_2, …, v_{k+1}$ 都有一条边,去掉顶点 $v$,就可以得到图 $G’$,其度序列就是 $d_2 - 1, d_3 - 1, …, d_k - 1, d_{k+1} - 1, d_{k+2}, …, d_n$.

  • Analyse the complexity

最坏的情况,算法递归复杂度为 $O(n)$,每次递归中排序复杂度为 $O(n\log n)$

第二题

There are n distinct jobs, labeled $J_1, J_2, …, J_n$, which can be performed completely independently of one another. Each jop consists of two stages: first it needs to be preprocessed on the supercomputer, and then it needs to be finished on one of the PCs. Let’s say that job $J_i$ needs $p_i$ seconds of time on the supercomputer, followed by $f_i$ seconds of time on a PC. Since there are at least $n$ PCs available on the premises, the finishing of the jobs can be performed on PCs at the same time. However, the supercomputer can only work on a single job a time without any interruption. For every job, as soon as the preprocessing is done on the supercomputer, it can be handed off to a PC for finishing.

Let’s say that a schedule is an ordering of the jobs for the supercomputer, and the completion time of the schedule is the earlist time at which all jobs have finished processing on the PCs. Give a polynomial-time algorithm that finds a schedule with as small a completion time as possible.

  • The basic idea and pseudo-code

按照 PC 上的运行时间 $f_i$ 对 jobs 降序排列,得到的就是最优的 schedule.

1
2
3
4
5
输入:Jobs结构体数组
function Schedule(Jobs)
sort(Jobs) // 按 job 在PC上的运行时间 f 降序排列
return Jobs
end function
  • The greedy-choice property and optimal substructure

每次选择在 PC 上运行时间最长的 job 放入 supercomputer.

  • Prove the correctness

设 schedule $S$ 按 job 在 PC 上的运行时间 f 从大到小的顺序执行 job,现任意给出一个 schedule $T$,满足条件 $S \neq T$,则 $T$ 中必定存在相邻的一对 job $J_m$ 和 $J_n$,$J_m$ 在 $J_n$ 之前执行,但 $f_m < f_n$,交换两者的执行顺序,得到 schedule $T’$,$J_n$ 在 $T$ 中开始转到 PC 执行的时间 与 $J_m$ 在 $T’$ 中开始转到 PC 执行的时间是相等的,因为这两个 job 之前的 job执行顺序没有变,而这两个 job 在 supercomputer 上执行的总时间始终为 $p_m + p_n$,但因为 $f_m < f_n$,所以 $J_m$ 在 $T’$ 中结束运行时间早于 $J_n$ 在 $T$ 中结束运行的时间,所以 $J_m$ 和 $J_n$ 在 $T’$ 中结束运行的时间早于在 $T$ 中的时间. 因此,$T$ 经过上述操作,运行的时间不可能增长,而重复进行有限次的上述操作,必能使 $T$ 转变为 $S$,所以 $S$ 的运行时间不可能大于任意一个不同于它的 schedule,$S$ 就是最优解.

  • Analyse the complexity

算法只需一次排序即可完成:

第五题

Write a program in your favorate language to compress a file using Huffman code and then decompress it. Code information may be contained in the compressed file if you can. Use your program to compress the two files (graph.txt and Aesop_Fables.txt) and compare the results (Huffman code and compression ratio).

这题可以参考《算法(第4版)》

压缩率 = 7443072 / 16757760 = 44.42%

压缩率 = 867768 / 1520528 = 57.07%


版权声明

作者:萝卜姓胡
许可协议:Creative Commons Attribution-ShareAlike 4.0 International License
本文永久链接:http://hw2007.com/2018/10/09/中国科学院大学《计算机算法设计与分析》第三次作业/