Method #
基本思想 #
贪心算法基本思想
贪心算法是一个分阶段决策过程，在每个局部阶段，贪心法都做出一个当前 最优的局部决策，并期望通过每次所做的局部最优决策产生一个全局最优解。
贪心算法类似于分治算法和动态规划，也是一种基于子问题思想的策略。
贪心算法求解步骤
- 分解，将原问题求解过程划分为连续的若干个决策阶段
- 决策，在每一个阶段依据贪心策略进行贪心决策，得到局部的最优解，并缩小待求解问题的规模
- 合并，将各个阶段的局部解合并为原问题的一个全局最优解
Greedy(C) { // C是问题的输入集合即候选集合
S = {}; // 初始解集合为空集
while (not Solution(S)) { // 集合S没有构成问题的一个可行解
x = Select(C); // 在候选集合C中做贪心决策
S = S + {x};
C = C - {Collection(x)}; // 减去一个与x关联的集合，缩小问题规模
}
return S;
}
- 候选集合 C 是构造问题的解 (包括最优解) 的对象集合
- 解集合 S 表示问题的解，它随着贪心选择的进行不断扩展，直到构成一个满足问题的完整解
- 选择函数 Select 是贪心策略的实现过程，这是贪心法的关键，它指出哪个候 选对象最有希望构成问题的最优解，选择函数通常和目标函数有关
正确性证明 #
数学归纳法
- 证明目标
- ∀ 𝒏 𝒑(𝒏) 为真 / / n 的论域为正整数集合
- 证明框架
- 基础步骤: p(1) 为真
- 归纳步骤: 证明∀k(p(k) →p(k+1)) //对任意正整数 k, 给出 p(k)├ P(k+1) 的论证步骤
- 结论: 对任意正整数 n，p(n) 成立
交换论证法
交换论证法 (Exchange Argument ): 从任意一个最优解出发，经过不断用新的要素 (符合贪心准则) 替换解中的原有要素来改变这个解。通过有限步替换，把这个最优解改造成贪心算法的解。如果替换过程中的每一步能保证解的最优值不发生变化，则证明了贪心算法的解也是最优的。
具体步骤：
- 给出贪心算法解 A 的描述
- 假设 O 是一个最优算法解 (如果有多个则随机选)
- 找出 O 和 A 中的一个不同要素 (可以是一个元素在 O 不在 A 或者反之，或者是一个子序列的顺序 A 和 O 不一样)
- 交换 (Exchange)*上述不同的要素，然后论证 (Argue) 得到的新解 O 不比 O 差
- 论证类似的不同要素为有限个 (多项式量级)，然后交换有限次 (多项式量级) 可以消除所有的不同，同时保证了算法的质量不比 O 差
e.g.s #
活动安排问题 #
假设某社团某一天要组织𝑛个活动𝐸={1,2,⋯,𝑛} ，其中每个活动都要求使用同一礼堂，而且
在同一时间内只有一个活动能使用这个礼堂。每个活动𝑖都有一个要求使用礼堂的起始时间𝑠𝑖
和结束时间 𝑓 ，且有𝑠 < 𝑓 。如果选择了活动𝑖，则它在半开时间区间[𝑠 , 𝑓 ) 内占用资源。若区间[𝒔𝒊, 𝒇𝒊) 与区间[𝒔𝒋, 𝒇𝒋) 不相交，则称活动𝐢与活动𝐣是相容的。现在给定𝑛个活动的开始时 间和结束时间，请设计一个活动安排方案，使得安排的相容活动数目最多。
-
策略思考
- 策略一: 选择具有最早开始时间，而 且不与已安排的活动冲突的活动。
- 策略二: 选择具有最短使用时间，而且 不与已安排的活动冲突的活动。
- 策略三: 选择具有最早结束时间，而且不与已安排的活动冲突的活动。
-
算法思路
- 预处理 把所有的活动按照结束时间进行升序排列，有𝑓[1] ≤ 𝑓[2] ≤ ⋯ ≤ 𝑓[𝑛]
- 选择第一个活动 选择结束时间最早的活动 𝐸[1]，当前决策𝑠𝑒𝑙𝑒𝑐𝑡𝑒𝑑 = 1
- 贪心选择后续活动 依次扫描后续的每一个活动𝐸[𝑖]，如果𝐸[𝑖] 的开始时间晚于上一个 选择的活动 E[selected ] 的结束时间，则安排当前活动𝐸[𝑖]，令𝑠𝑒𝑙𝑒𝑐𝑡𝑒𝑑 = 𝑖; 否则放弃 𝐸[𝑖]。
int greedyEventSchedule(int n,int *timeStart,int *timeFinish) {
int i,j,selected,ans=0; //冒泡排序，使得活动按结束时间升序排列
for(i=0; i<n; i++)
for(j=0; j+1<n; j++) if(timeFinish[j]>timeFinish[j+1]) {
swap(timeFinish[j],timeFinish[j+1]);
swap(timeStart[j],timeStart[j+1]); //注意开始时间也需一致移动
}
ans = 1;
selected = 0; //选择第一个活动
for(i=1; i<n; i++)
if(timeStart[i]>= timeFinish[selected]) {
selected = i; //选择相容的最早结束活动
ans++;
}
return ans;
}
算法正确性证明
小数背包问题 #
问题描述:给定𝑛种物品和一个背包。物品𝑖的重量是𝑊𝑖，其价值为𝑉𝑖，背包的容量为C，应如何 选择装入背包的物品使得装入背包中物品的总价值最大? 这里，在选择物品𝑖装入背包时，可以选 择物品𝑖的一部分，而不一定要全部装入背包。
输入:多组测试数据。每组测试包括三行:第一行输入物品的总数𝑛(𝑛 < 1000)和背包的容量 𝐶(𝐶 < 1000)。第二行输入𝑛个整数，表示物品的重量。第三行输入物品的价值。 输出:输出装入背包的总价值，每组测试数据输出一行。
输入样例:
3 50
10 20 30 60 100 120
输出样例:
240
-
策略思考
- 策略一: 在不超出当前背包的剩余容量前提下，优先选择价值最大的物品，这样使得装 入价值增长最快。
- 策略二: 在不超出当前背包的剩余容量前提下，优先选择重量最轻的物品，这样使得背包 容量增长最慢。
- 策略三: 在不超出当前背包的剩余容量前提下，优先选择价值率 (价值除以重量) 最 大的物品，这样使得背包中单位重量价值增长最快。
-
算法思路
- 预处理，把物品按照价值率进行降序排列
- 选择第一个物品 根据贪心策略，首先选择价值率最大的物品，并记录该物 品装入的重量。
- 贪心选择后续活动 依次扫描每一个物品，在没有超出背包容量的条件下， 尽可能多地装入当前价值率最高的物品，并记录该物品装入的重量。
#include<stdio.h> #include<algorithm> using namespace std; #defineMaxItems 1000
struct item{
int weight;
int value;
bool operator <(const item& bb) const { //定义比较函数(小于号)
return value/(1.0*weight) > (1.0*bb.value)/bb.weight; //为什么乘以1.0?
}
}; //定义物品的结构体
double greedyKnapsack(int n,int capacity,item* itemSet) {
double ans = 0;
sort(itemSet,itemSet+n); //STL中的快速排序算法
for(int i=0; i<n; i++)
if(itemSet[i].weight <= capacity){
ans += itemSet[i].value;//选择单价最大的物品 capacity -= itemSet[i].weight;
capacity-=itemSet[i].weight;
} else {
ans += capacity*(itemSet[i].value*1.0)/itemSet[i].weight;//最后一个物品只能装部分
break;
}
return ans;
}
在这段代码中，乘以 1.0 主要是为了确保在进行除法运算时，使用浮点数而不是整数。在 C++ 中，如果两个整数进行除法运算，结果会被截断为整数部分，这可能导致不准确的比较结果。
通过乘以 1.0，将其中一个操作数转换为浮点数，整个表达式就会被当作浮点数运算，确保得到的结果是浮点数而不是整数。这样可以避免由于整数截断而导致的错误比较。
字符编码 #
一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。请设 计一个编码算法，把每一个字符转换为二进制编码。
不同的字符
二元前缀码 在一个字符集的编码表 (每一个编码都表示为 0-1 字符串) 中，如果任何一个字符编码 都不是其它字符编码的前缀，则该编码称为二元前缀码。
- 编码: 把字符转换为二元前缀码的过程
- 解码: 把二元前缀码 (0-1 符号串) 映射为字符的过程。从第一个字符开始依次读入每个字符 (0 或者 1)，如果发现读到的子串与某个代码相等，就将这个字串译作相应代码的字符。
二元前缀码的存储通常采用二叉树结构，令字符保存在叶节点，则该字符的前缀码对 应根到该叶节点的一条路径。规定每个节点通向左儿子的边记为 0，通向右儿子的边 记为 1，则根到叶节点的路径则可以转换为一个 0-1 串，映射为二元前缀码。
一个字符集可以构造多个二元前缀码。
哈夫曼编码
哈夫曼编码算法的贪心策略是: 给频率高的字符较短的代码; 频率低的字符较长的代码
把编码映射成二叉树，则其贪心策略可表述为: 把频率高的字符分配给靠近根结点 (较浅) 的叶结点，把频率低的字符放置在远离根结点 (较深) 的叶结点
自底向上构造二叉编码树，由森林不断合并得到一棵二叉树
- 算法思路
- 为了便于找到频次最低的字符，哈夫曼算法建立一个以𝐟为键值的优先队列 Q，假设 编码字符集中每一字符𝐜的频率是𝐟(𝐜)。哈夫曼编码算法以自底向上的方式构造最优 编码树 T。
- 每个字符构成一棵只包含一个结点的树，总共有ȁ𝐶ȁ棵构成一个森林。
- 合并频率最低的两棵树，并产生一棵新树，其频率为合并的 2 棵树的频率之和，并将新树插入优先队列 Q。
- 循环此过程，经过𝑛-1 次这样的合并后，优先队列中只剩下一棵树，即最优二叉编码树 T。
struct cmp {
bool operator () (const int &x,const int &y) {
return x > y;
}
}; //定义优先队列需要的比较函数
double haffmanCoding(int n, int* freq) {
int i, total = 0, sumFreq = 0, jointFreq;
priority_queue<int, vector<int>, cmp> heap; // 优先队列，最小值优先
for(int i=0;i<n;i++){
total += freq[i];
heap.push(freq[i]);
}
while (heap.size() > 1) { // 循环选择队列中频次最少的两个元素合并
jointFreq = 0; // 合并后结点的频次
for (i = 0; i < 2; i++) { // 删除频次最少的两元素
jointFreq += heap.top();
heap.pop();
}
sumFreq += jointFreq;
heap.push(jointFreq); // 优先队列中插入合并结点
}
return sumFreq / (1.0 * total); // 返回平均码长
}
- 正确性证明
- 交换论证法原理: 从任意一个最优解出发，经过不断用新的要素 (符合贪心准则) 替 换解中的原有要素来改造这个解。通过有限步替换，把这个最优解改变成贪心算法的 解。如果替换过程中的每一步能保证解的最优值不发生变化，则证明了贪心算法的解 也是最优的。
- 基础步: 给定任意一个最优解，根据贪心准则对最优解进行改造，也就是把第一步 贪心选择的对象替换最优解中的特定要素，然后证明替换后的新解也是最优解
- 递归步: 证明上述交换过程可以循环进行。也就是说，依次替换最优解的其他要素， 直到新解的每个分量都符合贪心准则，并且证明新解也是最优的。
- 证明方法一般是: 最优子结构性质 + 基础步结论
- 设一个任意一个，假设谈心算法得到的解不是最优解（本题中是和普通情况一样）
- 每一步进行贪心调整，若结果发现是最优解，证明假设不成立，则能够证明谈心算法的正确性
单源最短路径问题 #
给定带权有向图G = (V, E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称 为源。现在要计算从源到所有其它各顶点的最短路径长度，假设从源可以到达任何一个顶点。 这里路径的长度是指路径上各边权之和。这个问题通常称为单源最短路径问题。
从源到任意顶点的最短路径具有类似于最优子结构性质的特征: 即最短路径的子 路径也是源到相应顶点的最短路径。
- 汇集所有顶点的最短路径就可以得到一棵最短路径树。在最短路径树中，从 源到任意顶点的路径就是图 G 中从源到该顶点的最短路径。
- 求解单源最短路径问题就可以转换为构造图 G 的一棵最短路径树𝐓。
Dijkstra 算法
Dijkstra 算法的贪心策略是选择集合𝐕 − 𝐒中受限路径长度最短的顶点，并把相应顶点加 入 𝑆 中，相应地最短路径树 𝑇 也增加一条边。
- 算法思路
- 设计合适的数据结构:
- 带权邻接矩阵 linkMatrix，记录输入有向图的权值
- 数组 lowLR 记录从源到其它顶点的最短受限路径长度
- 数组 preV 记录最短路径中的前驱顶点，假设 preV[x] = u，则在 x 的最短路径中，u 是 x 的前驱顶点
- 初始化: 把源加入集合 S 中，即 S = {v}，对于 V-S 中的所有顶点 x，设置
lowLR[x] =linkMatrix[v][x]，preV[x] = v(如果有边相连)
- 贪心选择: 在集合 V-S 中依照贪心策略寻找 lowLR[x] 最小的顶点 t ，即
lowLR[t]=min{lowLR[x] x 属于 (V −S)}
- 更新过程: 将顶点 t 加入 S 中，同时更新集合 V-S，以及集合中顶点的最短受限路径:
lowLR[x] = lowLR[t]+ linkMatrix[t][x]st. lowLR[x] > lowLR[t]+ linkMatrix[t][x]
- 设计合适的数据结构:
#include <iostream>
#define INF 0x03F3F3F3F
#define MaxV 100
int preV[MaxV]; // 最短路径树中的前驱结点信息表
int visited[MaxV]; // 结点是否加入S的标记表，0 是未加入，1 为已加入
void Dijkstra(int linkMatrix[][MaxV], int lowLR[MaxV], int numV, int beginV) {
int i, j, min, newCost;
memset(visited, 0, sizeof(visited)); // 初始化，所有节点未加入
visited[beginV] = 1;
// 开始节点 beginV加入列表中
for (int i = 0; i < numV; i++) {
lowLR[i] = linkMatrix[beginV][i];
preV[i] = beginV;
}
// 准备正式开始Dijkstra算法流程
lowLR[beginV] = 0;
preV[beginV] = -1;
int selectV = beginV;
for (int i = 0; i < numV; i++) {
for (int j = 0; j < numV; j++) {
newCost = lowLR[selectV] + linkMatrix[selectV][j];
if (visited[j] == 0 && newCost < lowLR[j]) {
lowLR[j] = newCost;
preV[j] = selectV;
}
}
min = INF;
// 贪心选择最短路径
for (int j = 0; j < numV; j++) {
if (visited[j] == 0 && lowLR[j] < min) {
min = lowLR[j];
selectV = j;
}
}
visited[selectV] = 1;
}
}
正确性证明
最小生成树问题 #
问题描述:设𝐺 =(𝑉,𝐸)是无向连通带权图。E中每条边(𝑣,𝑤)的权为𝐶(𝑣,𝑤)。如果𝐺的子图𝐺’是 一棵包含𝐺的所有顶点的树，则称𝐺’为𝐺的生成树。生成树上各边权的总和称为该生成树的耗费。 在G的所有生成树中，耗费最小的生成树称为G的最小生成树。请设计算法计算G的最小生成树的 权重总和。
图的生成树
定义: 如果连通图 G 的一个子图是一棵包含 G 的所有顶点的树，则该子图称为 G 的生 成树 (Spanning Tree)。
- 生成树是连通图的包含图中的所有顶点的 极小连通子图
- 图的生成树不惟一，从不同的顶点出发进行遍历，可以得到不同的生成树
- 常用的生成树算法有 DFS 生成树、BFS 生成树、PRIM 最小生成树和 Kruskal 最小生成树算法
最小生成树
定义: 对于连通的带权图 G=(V, E)，其生成树也是带权的，生成树 T=(V, TE) 各 边的权值总和称为该树的权 W(T)， TE 表示 T 的边集，𝐶(𝑢,𝑣) 表示边 (u,v) 的权重。 权最小的生成树称为 G 的最小生成树 (Minimum Spanning Tree, MST)。
- 最小生成树性质
- 生成树有 |V| 个顶点，|V|-1 条边
- 生成树中增加一条边则得到一个回路，回路中删除任何一条边又得到一棵生成树
- 设𝐺 = (𝑉, 𝐸) 是连通带权图，U 是 V 的真子集。如果 (𝑢, 𝑣) ∈ 𝐸，其中𝑢 ∈ 𝑈, 𝑣 ∈ (𝑉 − 𝑈) ，称之为 跨边，且在所有这样的边中，(𝒖, 𝒗) 的权𝑪(𝒖, 𝒗) 最小，那么一定存在𝐺的一 棵最小生成树，它包含边 (𝑢, 𝑣)。
Prim 算法
-
针对图中的顶点设计贪心策略，逐步 添加顶点/边构造最小生成树
-
策略: 选择最短跨边
-
策略思考
- 给定无向带权图 G=<V, E>，逐步构造最小生成树:MST = (U, TE)，其中 U⊆V, TE⊆E。图 G 中的顶点集合 V 划分为两部分: 集合 U 和 V-U，其中 U 是已加入 MST 中 的顶点集合，而 V-U 是 MST 之外的顶点集合。
- 初始化:U={x}，其中 x 为集合 V 中的任一结点 (起始点)，TE={};
- 循环直到 U=V:
- 贪心选择:𝒊 ∈ U, j ∈ V − U，且边 (i, j) 是连接 U 和 V-U 的所有边中的最短 边
- 把顶点 j 加入集合 U ➢ 边 (i, j) 加入集合 TE
-
算法思路
- 设计合适的数据结构:
- 带权邻接矩阵 linkMatrix，记录输入有向图的权值
- 数组 lowCost 最短跨边，
lowCost[ j] 表示满足𝑗 ∈ 𝑉 − 𝑈, 𝑖 ∈ 𝑈的所有边 (𝑖, 𝑗) 中的最小值 - 数组 closest 记录上述最短边 (𝑖, 𝑗) 中的顶点标号 i ，它们满足
𝑙𝑜𝑤𝐶𝑜𝑠𝑡[𝑗] = 𝐶(𝑗, 𝑐𝑙𝑜𝑠𝑒𝑠𝑡[𝑗]) 。
- 初始化: 把顶点 1 加入 U 中，得 U = {1}，𝑇𝐸 = { }，
- 并初始化数组 closest 和 lowCost
- 贪心选择: 在集合𝑉 − 𝑈中寻找使得 lowCost 最小的顶点 t，
- 将 t 加入集合 U，边 (t, cloest[t]) 加入集合 TE
- 更新过程: 对 𝑉 − 𝑈 中的所有顶点 𝑘，按下述规则更新数组 closest 和 lowCost:
if (linkMatrix[t][k] < lowCost[k])lowCost[k] = linkMatrix[t][k];closest[k] = t
- 设计合适的数据结构:
#include <iostream>
#define INF 0x03F3F3F3F
#define MaxV 1000
int prim(int linkMatrix[][MaxV], int numV) {
int visited[MaxV] = {0};
int lowCost[MaxV], closet[MaxV];
int i, k;
int min, costMST = 0;
visited[0] = 1;
closet[0] = -1;
for (int i = 0; i < numV; i++) {
lowCost[i] = linkMatrix[0][i];
closet[i] = 0;
}
for (int i = 0; i < numV - 1; i++) {
min = INF;
int selectV = 0;
for (int k = 0; k < numV; k++) {
if (!visited[k] && lowCost[k] < min) {
min = lowCost[k];
selectV = k;
}
}
costMST += min;
visited[selectV] = 1;
for (int k = 1; k < numV; k++) {
if (!visited[k] && linkMatrix[selectV][k] < lowCost[k]) {
lowCost[k] = linkMatrix[selectV][k];
closet[k] = selectV;
}
}
}
return costMST;
}
正确性证明
并查集 #
并查集 (Disjoint set 或者 Union-find set) 是一种树型的数据结构，常用于处理一些不相交集 合 (Disjoint Sets) 的合并及查询问题。它包含两种基本操作:
-
查询 (Find): 查询某个元素在哪个集合里
-
合并 (Union): 合并两个集合
-
每个集合选定一个固定的元素作为该集合的代表， 称为代表元素，代表元素则用于标识整个集合
-
每一个集合用树表示，树中的每一个节点保存着 到其父节点的引用，每个集合的代表元素即是集 合的根节点。
-
双亲表示法: 用数组 father[] 存储整个并查集
查询
合并
并查集优化策略一——路径压缩
路径压缩是一种在执行“查询”时扁平化树结构的方法，为后续查询操作加速。
- 路径上的每个节点都直接连接到根上;
- 递归地访问当前结点到树根的路径，改变每一个结点的引用到根节点。
并查集优化策略二——按秩合并
按秩合并即总是将更浅的树连接至更深的树上，避免增加合并树的秩
- “秩”表示集合对应树的深度，单个元素的树的秩定义为 0;
- 当两棵秩同为𝑟的树联合时，它们的秩变为𝑟 + 1;
- 为了方便比较，把集合秩的相反数存储在根节点 father[root] 。
Kruskal 算法 #
给定无向带权图𝐺=(𝑉,𝐸)，𝑉={1,2,…,𝑛}。设最小生成树𝑀𝑆𝑇 = (𝑉, 𝑇𝐸)，该树的 初始状态为只有𝐧个顶点而无边的非连通图𝑇 = (𝑉, {} )， Kruskal 算法将这𝑛个顶点看成 是𝑛个孤立的连通分支;
贪心选择: 在边集𝐸中选择权值最小的边 (𝑖, 𝑗)，如果将边 (𝑖, 𝑗) 加入 TE 中不产生回路，则 将边 (𝑖, 𝑗) 加入 TE，即用边 (𝑖, 𝑗) 将 T 中的两个连通分支合并成一个联通分支; 否则舍弃它。 循环此过程，直至所有顶点都在一个联通分支。
Kruskal 算法俗称避环法，该算法的实现关键是在加入边时避免出现环路 用并查集来实现连通分支查找和合并的相关操作
- 算法步骤
- 初始化: 把图 G 中的所有边按照权值从小到大排序，MST 的边集 TE 初始化为空集。 每一个顶点初始化为一个孤立的连通分支，对应并查集中的一个子集合。
- 在 E 中寻找权值最小的边 (𝑖,𝑗)。
- 如果顶点𝑖和𝑗位于两个不同的集合
- 则将边 (𝑖, 𝑗) 加入边集 TE
- 并把顶点𝑖和𝑗所在的两个子集合并成一个子集
- 将边 (𝑖, 𝑗) 从 E 中删除
- 如果连通分支的数目大于 1，则转步骤 2; 否则，算法结束。
int kruskal(node juSet[MaxV], int numV, edge edgeSet[MaxE], int numE) {
qsort(edgeSet, numE, sizeof(struct edge), cmp);
for (int i = 0; i < numE; i++) {
fatherX = Find_Set(edgeSet[i].x);
fatherY = Find_Set(edgeSet[i].y);
if (fatherX == faterY) {
totalCost += edgeSet[i].w;
cntW++;
}
if (cntE == numV - 1) {
return totalCost;
}
}
return totalCost;
}
- 算法正确性证明
- 给出贪心算法解 A 的描述
- 假设 O 是一个最优算法解 (如果有多个则随机选)
- 找出 O 和 A 中的一个不同要素 (可以是一个元素在 O 不在 A 或者反之，或者是一个子序列的顺序 A 和 O 不一样)
- 交换 (Exchange) 上述不同的要素，然后论证 (Argue) 得到的新解 O* 不比 O 差
- 论证类似的不同要素为有限个 (多项式量级)，然后交换有限次 (多项式量级) 可以消除所有的不同，同时保证了算法的质量不比 O 差
小结 #
贪心算法的正确性证明
- 数学归纳法
- 针对贪心选择的步骤 (k) 进行归纳，比如活动安排问题，Dijkstra 算法，Prim 算法。
- 交换论证法
- 从原问题最优解开始，用贪心策略对最优解进行改造 (或者交换最优解与贪心解的不同要素)，有限步后把最 优解改造为贪心解，而且最优性保持不变。比如哈夫曼编 码，Kruskal 算法。