贪心算法深入
理解贪心选择、证明技巧,以及贪心何时最优何时失败。
你将学到
- 贪心选择性质
- 交换论证证明
- 拟阵理论与贪心最优性
- 经典贪心问题:哈夫曼、活动选择
概念讲解
贪心算法深入
贪心算法在每步做出局部最优选择,期望达到全局最优解。它简单快速,但仅当问题具有贪心选择性质(局部最优是全局最优的一部分)和最优子结构时才有效。
交换论证
标准证明技巧是交换论证:假设最优解与贪心解不同,然后证明可以交换元素将最优解转为贪心解而不变差。这证明贪心解至少与任何最优解一样好。
贪心何时有效
贪心在具有拟阵结构的问题上可证明最优——这是一种数学框架,贪心算法总能找到最优解。最小生成树(Kruskal)、哈夫曼编码和活动选择都具有拟阵结构。
贪心何时失败
0/1 背包问题是经典失败案例:按价值/重量比贪心会选取放不下的物品,错过最优组合。分数背包(可取物品分数)贪心有效。
经典示例
活动选择:按结束时间排序,贪心选取下一个兼容活动。哈夫曼编码:反复合并两个最低频率符号。Dijkstra:贪心扩展最近未访问节点。
示例代码
// Activity selection - greedy by earliest finish time
function activitySelection(acts) {
const sorted = acts.slice().sort((a, b) => a[1] - b[1]);
const selected = [sorted[0]];
for (let i = 1; i < sorted.length; i++) {
if (sorted[i][0] >= selected[selected.length-1][1]) selected.push(sorted[i]);
}
return selected;
}
// Huffman coding - greedy merge of least frequent
function huffmanCodes(freqs) {
const heap = freqs.map(([ch, f]) => ({ch, f, left: null, right: null}));
while (heap.length > 1) {
heap.sort((a, b) => a.f - b.f);
const a = heap.shift(), b = heap.shift();
heap.push({ch: null, f: a.f + b.f, left: a, right: b});
}
return heap[0];
}
const acts = [[1,4],[3,5],[0,6],[5,7],[3,9],[5,9],[6,10],[8,11],[8,12],[2,14],[12,16]];
console.log('Selected:', activitySelection(acts));
const tree = huffmanCodes([['a',45],['b',13],['c',12],['d',16],['e',9],['f',5]]);
console.log('Huffman root freq:', tree.f);
活动选择按结束时间排序并贪心选取兼容活动。哈夫曼通过反复合并两个最低频率节点构建树。
动手试一试
- Crontab Generator
调度是贪心问题领域——观察区间调度如何工作。
常见错误
错误写法
未证明就假设贪心总是最优。
正确做法
贪心仅对具有贪心选择性质的问题有效。在信任贪心解之前,总是证明最优性或用反例验证。
错误写法
按错误标准排序。
正确做法
排序键决定贪心选择。活动选择必须按结束时间排序,而非开始时间。错误键导致错误答案。
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。