贪心算法的最优解条件"/>
贪心算法的最优解条件
最优子结构条件
- 证明每次的局部最优解必须在全局最优解序列中,否则不可能到达全局最优
局部最优选择策略的选择很重要
最优化原理,证明该问题具有拟阵结构则贪心算法对该问题的求解是最优解
- 定理:设 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
更多推荐
贪心算法的最优解条件
发布评论