贪心算法的最优解条件

贪心算法的最优解条件"/>

贪心算法的最优解条件

最优子结构条件

• 证明每次的局部最优解必须在全局最优解序列中，否则不可能到达全局最优
  局部最优选择策略的选择很重要

最优化原理，证明该问题具有拟阵结构则贪心算法对该问题的求解是最优解

• 定理：设 M = ( S , I ) M = (S,\mathfrak{I}) M=(S,I)是赋权w的拟阵，则贪心算法Greedy（M，w）返回的子集A是M的最优独立集
• 证明有序对 M = ( S , I ) M = (S,\mathfrak{I}) M=(S,I)具有拟阵结构：
  1. S是一个有限非空集合
  2. 独立集的子集属于独立集，即 B ∈ I , A ⊆ B ⇒ A ∈ I B \in \mathfrak{I}, A \subseteq B \Rightarrow A \in \mathfrak{I} B∈I,A⊆B⇒A∈I
  3. 大独立集中存在一个元素并到小独立集中，小独立集仍为独立集
     A , B ∈ I , ∣ A ∣ < ∣ B ∣ ⇒ ∃ x ∈ B / A , A sup ⁡ { x } ∈ I A,B \in \mathfrak{I},|A|<|B| \Rightarrow \exists x \in B/ A,A \sup \{x\} \in \mathfrak{I} A,B∈I,∣A∣<∣B∣⇒∃x∈B/A,Asup{x}∈I