贪心算法正确性证明

文章目录

• 1. 活动选择问题
• • 1.1命题
  • 1.2 证明
  • • 1.2.1 归纳基础
    • 1.2.2 归纳步骤
• 2. Huffman算法
• • 2.1 命题
  • 2.2 证明
  • • 2.2.1 引理一
    • 2.2.2 引理二
    • 2.2.3 归纳基础
    • 2.2.4 归纳步骤
• 算法
• • 3.1命题
  • • 3.1.1 算法思想
    • 3.1.2 我们要证明正确性的命题： 
  • 3.2 证明
  • • 3.2.1 归纳基础
    • 3.2.2 归纳步骤

为了方便观看，本文章会把命题放在每一个证明步骤中

1. 活动选择问题

1.1命题

1.2 证明

令S = {1,2，…，n}是活动集，且f₁ <= … <= f_n
也就是说，S这个活动集是按照活动结束时间排好序的

1.2.1 归纳基础

命题

• 证明：k = 1的时候，命题成立

  • 即证明：k = 1的时候，证明存在最优解包含待选活动集合中的第一个活动，即结束时间最早的那个活动

• 最重要的一点！！！该归纳基础不是直接证明我们选的第一个活动就是最优解的第一个活动，而是要证明，排好序的活动中（按结束时间排好序的活动中）第一个活动（结束时间最早的活动）在最优解里面

• 因为最优解里面可能不含有结束时间最早的这个活动，所以要证明这个归纳基础

• 因为最优解可能不只一个，所以是存在最优解包含第一个活动

通过这个归纳基础，我们可以简单的认为，任何一个最优解best都包含待选集合中的第一个活动（如果不包含也可以将best中的第一个元素替换成待选集合中的第一个元素）（举个例子，现在有一个最优解为{i₂，i₄，i₇}，那么i₂可以用i₁来替换，集合{i₁，i₄，i₇}也一定是最优解）

证明：

• 如果最优解中的第一个活动不是S集合中的第一个活动，那么一定可以用S集合中的第一个元素替换掉最优解中的第一个元素

1.2.2 归纳步骤

命题

• 假设命题对k为真，证明对k+1也为真
  • 假设命题对k为真：假设算法到第k步，会有一个实际上的最优解A包含我们通过算法选择的i₁，i₂到i_k这些活动
  • 证明对k+1也为真：证明算法到第k+1步，会有一个实际上的最优解A包含我们通过算法选择的i₁，i₂到i_k，i_k+1这些活动

证明

1. 由命题对k为真知：

   • 最优解A包含i₁=1，i₂，…，i_k，那么除去前k步选的活动，最优解A中还应该有一些活动，为了方便引用，我们给最优解A中剩下的这些活动集合记作B集合，那么我们的最优解A也可以表示为A = {i₁,i₂,…,i_k}∪B （记住这个，下一段就要用到），B集合里的活动是从哪里挑的呢？我们把B集合的来源记作集合S’，那么S’中的集合中的元素至少是从i_k+1开始的（待选集合中的第一个元素就是i_k+1，这个要记住，后面要用到），我们可以表示为S’ = {i|i∈S,s_i>= f_k}
   • 我们还可以知道：集合B为S’的最优解
     证明集合B为S’的最优解：