Skip to content

贪心算法深入

理解贪心选择、证明技巧,以及贪心何时最优何时失败。

你将学到

  • 贪心选择性质
  • 交换论证证明
  • 拟阵理论与贪心最优性
  • 经典贪心问题:哈夫曼、活动选择

概念讲解

贪心算法深入

贪心算法在每步做出局部最优选择,期望达到全局最优解。它简单快速,但仅当问题具有贪心选择性质(局部最优是全局最优的一部分)和最优子结构时才有效。

交换论证

标准证明技巧是交换论证:假设最优解与贪心解不同,然后证明可以交换元素将最优解转为贪心解而不变差。这证明贪心解至少与任何最优解一样好。

贪心何时有效

贪心在具有拟阵结构的问题上可证明最优——这是一种数学框架,贪心算法总能找到最优解。最小生成树(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 等等。

查看术语表

动手做项目

通过引导式项目应用所学,含起始代码与解决方案。

查看项目

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误