文档库

最新最全的文档下载
当前位置:文档库 > 0021算法笔记——【贪心算法】贪心算法与活动安排问题

0021算法笔记——【贪心算法】贪心算法与活动安排问题

0021算法笔记——【贪心算法】贪心算法与活动安排问题

1、贪心算法

(1)原理:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

(2)特性:贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。能够用贪心算法求解的问题一般具有两个重要特性:贪心选择性质和最优子结构性质。

1)贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局

部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为: