贪心算法的拟阵理论相关证明分析

本文对拟阵理论的最优子集贪心算法的安全性和正确性证明进行了分析

另外，本文讨论了拟阵理论和贪心算法的关系 

写作日期：2019.1.20，20日掌握算法导论day11

• 【定理证明的依据是什么？】
  • 导致《拟阵最优子集问题》具有最优子结构性质的本质原因是拟阵具有交换性，即拟阵的第三个性质。
•  【最优子结构证明分析】
  • 引理16.10的证明是错误的，其I撇假设：B∪x∈I 没有任何依据，这是一个非常强烈的假设，这个假设直接导致了最优子结构性质的成立。而我们的目的便是证明最优子结构性，因此我们应该去证明B∪x∈I 而不是去假设他成立。（我们利用交换性+下面这个假设能够推出这个结论）
  • 拟阵的交换性说明，拟阵并不一定满足集合的下面这个运算：
    • 如果x∈I，y∈I，那么x∪y属于I
    • 我不得不假设，子问题I撇的任意独立子集都∈（母问题的I）
• 【将最小生成树问题转化为拟阵的几点分析】
  • 首先要认识到我们的无向图G就是一个拟阵，这非常关键。
  • 其次拟阵仅仅是最小生成树这一贪心算法问题的数学描述，他并没有提供更加快捷的解法，仅仅是在数学上做到了对某一类特殊的贪心问题进行归纳。
  • 【为什么最小生成树问题可以转化为拟阵？】
    • 我们发现我们遇到的最小生成树问题竟然被拟阵理论奇妙地统一进来了，这就是一个问题。其本质原因是无向图的结构有一个性质天生就满足拟阵的遗传性和交换性，这个性质就是“无圈”

本文是对算法导论16.4节的分析，下面给出原文