Skip to main content

贪心算法

贪心算法主要是在问题求解的试合，总是会做目前看来最好的选择，不考虑整体上的最优，考虑局部的最优，所以贪心算法一般情况下得到的是局部最优解，排除有概率得到最优解。

贪心算法是基于多部决策的分治法，用于求解最优化问题，思想就是每一步都会做当前看来最好的决策，即局部最优的决策。

算法思路​

  1. 建立数学模型来描述问题
  2. 把要求解的问题分解成多个子问题，大问题分解成小问题
  3. 对每个子问题进行求解，得到的子问题是局部最优解
  4. 把子问题的局部最优解合并得到原问题的解

算法正确性证明​

证明正确性实际上就是要说明为什么算法能够得到正确的解。 贪心算法的最优解条件: 证明每次的局部最优解必须在全局最优解序列中，否则不可能到达全局最优 与最优性矛盾本质上就是得不到最优解，或者和原来的最优解产生矛盾

归纳论证​

叙述一个描述正确性的命题对算法步数归纳或者对问题规模归纳

  • 算法步数进行归纳

归纳基础: 证明存在最优解 归纳步骤: 假设算法按照前k步选择哦度导致最优解，证明第k+1步选择也有最优解

caution

注意: 算法本身是一个已知条件，默认是可以随时拿来使用的，只要算法继续进行，那么就是满足条件的

  1. 一般来说都是比较解序列的长度看看是否超过了目标要求，如果超过了说明不是最优解
  1. 先求解算法第1步的时候的情况的最优解，即k=1
  2. 列出算法第k步时最优解成立的情况
  3. 当进行到第k+1步时，证明k+1步得到的也是最优解，在算法第k步的基础上进行证明，再用反证说明k+1步的情况和k的情况的最优性产生矛盾。
  • 问题规模进行归纳
  1. 当n=1或2时(根据实际问题确定)，该算法是否成立，一般都成立
  2. 假设当输入规模为n时，算法都是成立的，处理n+1的情况
  3. 当输入规模为n+1时，假设题目的某个条件成立(在输入规模为n的基础上)，利用这个条件得到一个最优解，再用反证说明n+1的情况和n的情况的最优性产生矛盾。

交换论证​

在保证最优性不变的前提下，从一个最优解进行逐步替换，最终得到贪心法的解。也就是交换顺序之后解的性质不变

直接使用算法本身能够得到最优解作为命题进行证明时或者算法是针对数组中元素的位置进行操作时，可以使用交换论证。

一般来说会先假设存在一个最优解A，假设当前得到的一个解B，假设A≠BA\not ={B}，根据解来得到相应的推导式，一般来说会让其他元素跟最优解相等，只有最后一个元素跟最优解不等(具体是大于小于看问题要求的最优解，假设成得到最优的情况)，构造一个新的最优解，之前的最优解经过多次替换之后能够得到新的最优解，就说明交换论证成功。

步骤:

先说明如何得到最优解，然后如果是在一个解序列里面使用交换论证来证明，则需要假设一个最优解的解序列中存在一对逆序，交换具有逆序的相邻元素之后能够得到新解，比较这两个解的差别，发现新解也是最优解，那么就说明通过交换去除所有的逆序之后就可以使得f变为贪心算法的解。

  • 本质上来讲，交换论证的方法是通过证明一个解序列通过若干次交换之后能够得到最优解。
  • 在不改变最优性的条件下，转变成为没有逆序的解
  • 实际上就是证明交换之后仍然保持最优性