贪心算法

郝文姣

贪心算法最早由J.C.Warnsdorff于1823年提出，是指在对问题求解时，总是做出当前最优选择，即局部最优解。贪心算法有两个基本要素：即贪心选择和最优子结构。它是最接近人类日常思维方式的一种解题策略，本质上是一种改进了的分级处理方法。虽不保证所求解是最佳选择，但可为所求问题确定可行范围，它采用自顶向下的方式，以迭代方法做出选择，相比其他算法更具速度优势。

贪心算法是一种重要的算法设计策略而且具有高效性，因其不从整体最优考虑，只在局部最优中进行选择，即当前看来最好的选择。贪心算法具有良好的爬坡能力，可较快求出满足计算精度要求的近似最优解。相比动态规划法更加简单和直观。

贪心算法在科学计算和工程中的应用越来越广泛，例如在三角部分的指纹匹配这一高科技领域已经取得重大进展。未来，在排课系统、贪心聚类算法以及在遥感图像分类和压缩中的應用也会更加成熟。只要符合贪心策略，就可利用贪心算法求解。

贪心算法对许多问题不能总是产生最优解，但可以解决最短路径问题、最小生成树问题、哈夫曼编码等问题。随着问题规模和复杂度的不断提升，单一算法在其收敛性和求解速度等方面已经表现出局限性。此外，贪心算法的高效性也只适用于少量实例。