Skip to content

9 Greedy Algorithms

基本性质

Which of the following is NOT an element of Greedy strategy?

\(\textnormal{A}\). works only if the local optimum is equal to the global optimum

\(\textnormal{B}\). optimal substructure

\(\textnormal{C}\). make a choice before solving the remaining sub-problem

\(\textnormal{D}\). overlapping sub-problems

答案

重叠子问题是动态规划的核心要素，贪心算法并不要求这一性质，故答案为 \(\textnormal{D}\)

In a greedy algorithm, a decision made in one stage is not changed in a later stage.

答案

\(\textnormal{T}\)

Activity Selection

Let S be the set of activities in Activity Selection Problem. Then the earliest finish activity \(a_m\) must be included in all the maximum-size subset of mutually compatible activities of S.

答案

\(\textnormal{F}\)

Let S be the set of activities in Activity Selection Problem. Then there must be some maximum-size subset of mutually compatible activities of S that includes the earliest finish activity.

答案

\(\textnormal{T}\)

Let S be the set of activities in Activity Selection Problem. The greedy rule of "collecting the activity that starts the latest" is correct for finding a maximum-size subset of mutually compatible activities of S.

答案

选择最早结束的活动和选择最晚开始的活动都是活动选择问题被严格证明正确的贪心策略，答案为 \(\textnormal{T}\)

For the Activity Selection Problem, we can get the optimal solution by selecting the interval which starts earliest.

答案

\(\textnormal{F}\)

In the Activity Selection problem, consider any non-empty set of activities \(S\), and let \(a_m\) be an activity in \(S\) with the shortest lasting time. Then \(a_m\) must be included in some maximum-size subset of mutually compatible activities of \(S\).

答案

\(\textnormal{F}\)

In Activity Selection Problem, we are given a set of activities \(S=\{a_ 1, a_ 2, \ldots, a_ n \}\) that wish to use a resource (e.g. a room). Each \(a_ i\) takes place during a time interval \([s_ i, f_ i)\).

Let us consider the following problem: given the set of activities \(S\), we must schedule them all using the minimum number of rooms.

Greedy1:

Use the optimal algorithm for the Activity Selection Problem to find the max number of activities that can be scheduled in one room. Delete and repeat on the rest, until no activities left.

Greedy2:

  • Sort activities by start time. Open room 1 for \(a_ 1\).
  • for \(i = 2\) to \(n\) if \(a_ i\) can fit in any open room, schedule it in that room; otherwise open a new room for \(a_ i\).

Which of the following statement is correct?

\(\textnormal{A}\). None of the above two greedy algorithms are optimal.

\(\textnormal{B}\). Greedy1 is an optimal algorithm and Greedy2 is not.

\(\textnormal{C}\). Greedy2 is an optimal algorithm and Greedy1 is not.

\(\textnormal{D}\). Both of the above two greedy algorithms are optimal.

答案

\(\textnormal{C}\)

Schedule Problems

We are given \(n\) jobs \(J_1, J_2, ..., J_n\) (where job \(i\) is associated with deadlines \(d_i\) and processing times \(t_i\)) to be scheduled on a single machine. The lateness of job \(i\) is defined as \(L_i = \max(0, f_i - d_i)\), where \(f_i\) is the completion time of job \(i\). Our goal is to schedule all jobs such that \(L = \max_i L_i\) is minimized.

The following greedy algorithms first sort jobs in some orders, then process the jobs in that order. Which of the following greedy algorithms always return an optimal schedule?

\(\textnormal{A}\). Earliest deadline first: jobs are sorted according to the non-decreasing order of due dates \(d_i\).

\(\textnormal{B}\). Shortest slack first: jobs are sorted according to the non-increasing order of their slack times \(d_i - t_i\).

\(\textnormal{C}\). None of the other three options.

\(\textnormal{D}\). Shortest job first: jobs are sorted according to the non-increasing order of their processing times \(t_i\).

答案

\(\textnormal{A}\)

Huffman Codes

A binary tree that is not full cannot correspond to an optimal prefix code.

答案

若二叉树不是满的，则存在内部节点仅含一个子节点。此时，该子节点的编码路径可缩短（去掉仅含一个子节点的内部节点，直接将父节点与子节点连接），从而减少总编码长度，故答案为 \(\textnormal{T}\)

A Huffman tree with 61 nodes is the optimal coding tree for n characters. What a conclusion can we make for n?

答案

若字符个数为 \(C\)，则哈夫曼树的节点数为 \(2C − 1\)，编码位长不超过 \(C − 1\)，由 \(61 = 2n - 1\) 得 \(n=31\)，故答案为 \(31\)

Coin Change

Consider the problem of making change for \(n\) cents using the fewest number of coins. Assume that each coin's value is an integer. The coins of the lowest denomination (面额) is the cent.

(I) Suppose that the available coins are quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent). The greedy algorithm always yields an optimal solution.

(II) Suppose that the available coins are in the denominations that are powers of \(c\), that is, the denominations are \(c^0, c^1, ..., c^k\) for some integers \(c > 1\) and \(k \geq 1\). The greedy algorithm always yields an optimal solution.

(III) Given any set of \(k\) different coin denominations which includes a penny (1 cent) so that there is a solution for every value of \(n\), greedy algorithm always yields an optimal solution.

Which of the following is correct?

\(\textnormal{A}\). Statement (I) is false. \(\qquad\) \(\textnormal{B}\). Statement (II) is false.

\(\textnormal{C}\). Statement (III) is false. \(\qquad\) \(\textnormal{D}\). All of the three statements are correct.

答案

\(\textnormal{C}\)

Minimum Spanning Tree

Suppose that \(T\) is an minimum spanning tree of the graph \(G\), and \(S\) is a connected sub-graph of \(G\). Then \(T \cap S\) must belong to an minimum spanning tree of \(S\).

答案

\(\textnormal{T}\)

详细证明

设 \(T\) 是图 \(G\) 的最小生成树，\(S\) 是 \(G\) 的连通子图。\(T \cap S\) 表示 \(T\) 与 \(S\) 的边交集（即同时属于 \(T\) 和 \(S\) 的边）。该交集是 \(S\) 中的一个森林（因为 \(T\) 无环）。可以证明，存在 \(S\) 的一个最小生成树包含 \(T \cap S\) 中的所有边。

对于任意 \(e \in T \cap S\)，若 \(S\) 的某个最小生成树 \(M\) 不包含 \(e\)，则将 \(e\) 加入 \(M\) 会形成一个环。根据最小生成树的环性质，该环中所有边的权重至少为 \(w(e)\)。特别地，存在一条边 \(f\) 在该环中且 \(f \neq e\)，满足 \(w(f) \leq w(e)\)。但 \(f\) 在 \(S\) 中，且 \(f\) 不在 \(T\) 中（否则 \(T\) 会有环）。将 \(f\) 加入 \(T\) 也会在 \(G\) 中形成一个环，且该环包含 \(e\)。由于 \(T\) 是最小生成树，该环中 \(e\) 的权重必须不大于 \(f\) 的权重，即 \(w(e) \leq w(f)\)。因此 \(w(e) = w(f)\)。于是，在 \(M\) 中用 \(e\) 替换 \(f\) 可得到另一个最小生成树 \(M'\)，且 \(M'\) 包含 \(e\)。重复此过程，可逐步将 \(T \cap S\) 中的所有边纳入 \(S\) 的一个最小生成树中。

由于 \(T \cap S\) 中的边无环，它们可以同时被包含在同一棵生成树中。因此，存在 \(S\) 的一个最小生成树包含 \(T \cap S\) 中的所有边，即 \(T \cap S\) 属于 \(S\) 的某个最小生成树。故原陈述正确。