加权拟阵 加权拟阵的优化问题 Weight function: W: S)R* and Problem of maximum weighted W(A)=ZA W()for any A contains in S independent subset in a weighted matre ?What does this function means in a graph? is a typical problem of matroid and it can e solved by a greedy algorithm.【要求权 函数必须是正的】 清华大学們学院宋恒 清华大学软件学院宋 变种问题 问题实例:图的最小支撑树 There are also another type of problem Spanning tree:无向连通图的最大无圈子 called the problem of "minimum weight for 图,叫支撑树 the maximum size independent subset " in minimum spanning tree problem:求路径 a weighted matroid, it can be changed to 最短的支撑树。 the problem of the first type【没有正权限 制】.【如何做】 以上问题是一个变种问题 清华大学学院未恒 清华大学软件学院宋 The greedy algorithm Analysis of the complexit Greedy ( M, w) Ordering the elements 1.A∈ empty set 2. Sort S[M] into monotonically decreasing To decide the whether A U x is in I[M] order by weight w(x) O(n Ig n n f(n)) 3. For each x in S[M 1. If A U l[M]then AEAU(x] 4. Return A 清华大学轼字院宋恒 消华大学软件学院宋7 清华大学软件学院宋斌恒 37 加权拟阵 •Weight function: w: S‡R+ and •w(A) = åxÎA w(x) for any A contains in S •?What does this function means in a graph? 清华大学软件学院宋斌恒 38 加权拟阵的优化问题 •Problem of maximum weighted independent subset in a weighted matroid is a typical problem of matroid and it can be solved by a greedy algorithm.【要求权 函数必须是正的】 清华大学软件学院宋斌恒 39 变种问题 •There are also another type of problem called the problem of “minimum weight for the maximum size independent subset”in a weighted matroid, it can be changed to the problem of the first type【没有正权限 制】.【如何做】 清华大学软件学院宋斌恒 40 问题实例：图的最小支撑树 •Spanning tree:无向连通图的最大无圈子 图，叫支撑树。 •minimum spanning tree problem：求路径 最短的支撑树。 •以上问题是一个变种问题 清华大学软件学院宋斌恒 41 The greedy algorithm • Greedy(M,w) 1. Aflempty set 2. Sort S[M] into monotonically decreasing order by weight w(x) 3. For each x in S[M] 1. If A U {x} Î l [M] then AflA U {x} 4. Return A 清华大学软件学院宋斌恒 42 Analysis of the complexity •Ordering the elements. •To decide the whether A U {x} is in l [M] •O(n lg n + n f(n))