Java教程

贪心算法的证明

本文主要是介绍贪心算法的证明,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

由于考试算法中用到贪心时需要先证明其正确性才能使用,所以本人学习了一下贪心算法的证明方法并作此笔记。

首先,在网上找到的贪心策略证明有:

考察一个问题的最优解,证明可修改该最优解,使得其从贪心选择开始,然后用数学归纳法证明每一步都可以通过贪心选择得到最优解

1,假定首选元素不是贪心选择所要的元素,证明将首元素替换成贪心选择所需元素,依然得到最优解;

2,数学归纳法证明每一步均可通过贪心选择得到最优解

 

本人对此的理解就是当前你有一个最优解,然后我们将这个最优解分为两块,前边和后边都是对应集合的最优解,我们最后边的最优解,从下一步选择开始使用贪心选择对其中的元素进行替换,之后仍然是最优解,这就证明了贪心的正确性。

注:要特别注意,贪心是求得一个最优解,而不是求得唯一的最优解。

(1)如果bm = bi,择仍然为最优解

(2)如果bm != bi,则需要证明去除bi,加入bm仍然构成最优解即可。

 

下边我们来用贪心的一个经典例子,活动安排来讲解此问题。

1.首先,我们有一个最优解A,对这个最优解进行讨论

2.对这里边的第一个活动,若他是结束时间最早的活动,符合贪心,若不是,可以将第一个活动改为结束最早的活动(一定可以替换),所以当k = 1时,贪心正确。

3.推广到k > 1,对A的子集,我们已经选择可k个活动,构成Ak,下边我们进行第 k+1 个活动的选择,(注意,我们选择的前提是与Ak相容,贪心算法时选择的也是相容的最早结束的活动),原本我们的最优解扣去Ak后剩余B,对第k+1个活动的选取,我们选取结束最早的且相容的活动bm,若bm在B中,显然贪心成立,若bm不在b中,我们取出B中结束最早的活动bi,将bm加入其中,仍然不改变最优解的性质,贪心算法得到证明。

 

注:贪心算法证明的要义  1.选择一个普通的最优解  2.用贪心选择来替换其中的某一步选择时最优解性质不变,数学归纳证明其正确性。

这篇关于贪心算法的证明的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!