贪心选择律 贪心选择律之证明 Let M=(S, I] be a weighted matroid, and S If no such x exists, then the only independent is sorted into monotonically decreasing subset of s is the empty set. Hence we ar order by weight Let b be an optimal solution, then it is not empty. Let x be the first independent element in S assume x is not in B(if it is in B then the if such x exists If x exists then there exists an optimal Claim: There is no elements in B whose weigh s bigger than w(x). To see this, any element y in solution a such that x is an element of a B can construct an independent subset y), with 【最大的独立元素一定在某一个最优解 清华大学們学院宋恒 消华大学软件学院宋作 切粘技术 扩展引理 Construct an A such that A is optimal and contains X: using cut and paste, or the Let M=(S, 1] be any matroid, if x is an exchange property of M, we can grow element of s that is an extension of A=x by adding elements from B till to A some independent subset A of S, then x has the same size with B is also an extension of empty set. B and a only have one different element W(Bw(A)=w(y-W(x)≤0 The proof is simple. Really? Claim: A is optimal too 清华大学学院未恒 清华大学软件学院宋 淘汰无情 最优子结构定理 If x is not an extension of empty set, then it is not an extension of any independent Let x be the first element of s chosen by greedy for the weighted matroid M=(s, 1), the subset a of s remaining problem of finding a maximum-weight ndependent subset containing x reduces to finding a maximum-weight independent subset of the weighted M=(S,1), where ·S= dy in:{xy}nl} =[B subset of S-x]: B U(x) in 1) and The weight function to W is the weight function of M restrict to w 清华大学轼字院宋恒 消华大学软件学院宋8 清华大学软件学院宋斌恒 43 贪心选择律 •Let M={S, l } be a weighted matroid,and S is sorted into monotonically decreasing order by weight; • Let x be the first independent element in S if such x exists; • If x exists then there exists an optimal solution A such that x is an element of A • 【最大的独立元素一定在某一个最优解 中】 清华大学软件学院宋斌恒 44 贪心选择律之证明 • If no such x exists, then the only independent subset of S is the empty set. Hence we are done. Else, • Let B be an optimal solution,then it is not empty, assume x is not in B (if it is in B then the property is true), • Claim: There is no elements in B whose weight is bigger than w(x). To see this, any element y in B can construct an independent subset {y}, with assumption we get the claim 清华大学软件学院宋斌恒 45 切粘技术 •Construct an A such that A is optimal and contains x: using cut and paste, or the exchange property of M, we can grow A={x} by adding elements from B till to A has the same size with B •B and A only have one different element: •w(B)-w(A)=w(y)-w(x)£0 •Claim: A is optimal too! 清华大学软件学院宋斌恒 46 扩展引理 Let M={S, l } be any matroid, if x is an element of S that is an extension of some independent subset A of S, then x is also an extension of empty set. The proof is simple. Really? 清华大学软件学院宋斌恒 47 淘汰无情！ •If x is not an extension of empty set, then it is not an extension of any independent subset A of S. 清华大学软件学院宋斌恒 48 最优子结构定理 • Let x be the first element of S chosen by greedy for the weighted matroid M= (S, l ), the remaining problem of finding a maximum-weight independent subset containing x reduces to finding a maximum-weight independent subset of the weighted M’= (S’, l ’), where • S’={y in S: {x,y} in l } • l ’={B subset of S-{x}: B U {x} in l } and • The weight function to W’is the weight function of M restrict to W’