9 Greedy Algorithm¶
Make the best decision at each stage, under some greedy criterion. A decision made in one stage is not changed in a later stage, so each decision should assure feasibility.
Note
Greedy algorithm works only if the local optimum is equal to the global optimum. Greedy algorithm does not guarantee optimal solutions. However, it generally produces solutions that are very close in value (heuristics) to the optimal, and hence is intuitively appealing when finding the optimal solution takes too much time.
9.1 Activity Selection Problem¶
Given a set of activities \(S = { a_1, a_2, …, a_n }\) that wish to use a resource (e.g. a classroom). Each \(a_i\) takes place during a time interval \([s_i, f_i)\).
Activities \(a_i\) and \(a_j\) are compatible if \(s_i\ge f_j\) or \(s_j\ge f_i\) (i.e. their time intervals do not overlap).
QUESTION: Select a maximum-size subset of mutually compatible activities.
SOLUTION 1 (DP)
\(S(i,j)={a_k,f_i<=s_k<f_k<=s_j}\) 表示在活动 \(a_i\) 结束之后，在 \(a_j\) 开始之前的活动集，则整个问题空间可表示为 \(S(0,n+1)\), 其中添加活动 \(a_0\) 和 \(a_{n+1}\)，\(s_0=f_0=0\), \(s_{n+1}=f_{n+1}=2^{32}-1\)
根据 \(\text{dp}[i][j]\) 的含义,假设 \(S(i,j)\) 中不包含任何的活动序列(即满足 \(S(i,j)\) 定义的活动不存在)，则 \(\text{dp}[i][j]=0\)； 否则，假设 \(a_k\) 时 \(S(i,j)\) 中存在的一个兼容活动,那么这里存在问题\(S(i,j)\)的最优子结构: \(S(i,k)和S(k,j)\).
根据上面叙述，可以定义问题的递归解结构:
\(\text{dp}[i][j]=0\), 如果 \(S(i,j) =NULL\)
\(\text{dp}[i][j]=\max\{\text{dp}[i][k]+\text{dp}[k][j]+1\},i<k<j\)
最后要求的结果是\(\text{dp}[0][n+1]\)
需要注意的是： 在对区间队列进行动态规划之前，要对区间的结束时间按照时间从小到大进行排序，保证 \(f_1 <= f_2 <= f_3 <= ...<= f_n\)
SOLUTION 2 (Greedy)
在当前环境下选择最早结束的那一个课程
正确性验证：
记贪心算法所求得的解为\(G = < x_1,x_2,...,x_p>\)，而任意最优解为\(O = < y_1 , y_2 , . . . , y_q >\) 。由于 \(O\) 是最优解，一定有\(p ≤ q\)
从下标为 \(1\) 开始比较，假设第一个不同的活动为 \(x_i ≠ y _i\) ，那么一定有\(s_{x_i} ≥ f_{x_{i − 1}}\)，\(s_{y_i} ≥ f_{y_{i − 1}}=f_{x_{i − 1}}\)。又因为贪心算法总是选择结束时间最早的活动，有\(f_{x_i}\le f_{y_i}\)。因此，方案 \(O\) 可以不选择\(y_i\)活动而选择\(x_i\)活动，且保持一天参加活动数不变。
重复以上动作，可以使 \(O\) 的前 \(p\) 个活动与 \(G\) 的 \(p\) 个活动相同。由于 \(x_p\) 之后已经安排不下任何活动了，转化后的 \(O\) 也只有 \(p\) 个活动（或者说转化前就一定有 \(p = q\)）。这样，最优解 \(O\) 就被转化为了我们贪心算法的解 \(G\) 。贪心算法的正确性得证。
算法复杂度：\(N\)门课程，时间复杂度 \(O(N\log N)\)
如果我将每门课程加上一个权重，那么此时贪心算法就不成立了，我们只能使用动态规划来做
将式子改为dp[i][j]=max{dp[i][k]+dp[k][j]+Wj},i<k<j
所以贪心能做的，动态规划一定可以做；动态规划能做的，贪心就不一定能做了。
9.2 Huffman Codes¶
我们将文本的各个字符进行编码得到一串数字，为了防止有歧义，我们不能让其中一个字符的编码是另一个字符的前缀，那么为了让文本转化后的数字串长度尽可能短，那么我们需要让频率出现高的字符编码尽可能短。表示编码可以使用二叉树
一个简单的贪心思路就是先将字符按照频率从小往大排列，选出最小的两个进行合并成一棵子树然后再加入原先的堆，接着继续选择最小的两个合并，如此往复，直到得到一棵编码树。
这样的时间复杂度是 \(O(n\log n)\)
如果一开始给你的就是一个排好序的序列，那么我们能找到 \(O(n)\) 的算法吗？
我们可以再开一个队列，现有队列1，队列2。每次只要从队列1和队列2中选出最小的两个合并，然后进入队列2即可（由于合并的肯定是当前最小的，故每次合并得到的结果一定是单增的）
这样的时间复杂度就是 \(O(n)\)
评论区
对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！