最优子结构条件
证明每次的局部最优解必须在全局最优解序列中，否则不可能到达全局最优局部最优选择策略的选择很重要
最优化原理，证明该问题具有拟阵结构则贪心算法对该问题的求解是最优解
定理：设 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)具有拟阵结构： S是一个有限非空集合独立集的子集属于独立集，即 B ∈ I , A ⊆ B ⇒ A ∈ I B \in \mathfrak{I}, A \subseteq B \Rightarrow A \in \mathfrak{I} B∈I,A⊆B⇒A∈I大独立集中存在一个元素并到小独立集中，小独立集仍为独立集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
如果觉得《贪心算法的最优解条件》对你有帮助，请点赞、收藏，并留下你的观点哦！
