贪心法vs最优解 贪心法并不到达问题状态的全部空间 在某些问题中,无法取得最优解 问题状态空间 贪心策略所用空间
贪心法 vs. 最优解 ◼ 贪心法并不到达问题状态的全部空间 ◼ 在某些问题中，无法取得最优解 问题状态空间 贪心策略所用空间
贪心法框架 procedure GREEDY(A n) solution*(P ∥/初始化解集为空 fori←1 to n do //n次循环贪心选择 x← SELECT(A)/从A中选取某个元素到x if FEASIBLE( solution,x)//是否能够构成可行解 then solution← UNION( solution,x)//加入解 endif repeat return(solution)
贪心法框架 procedure GREEDY(A,n) solution←φ //初始化解集为空 for i←1 to n do //ｎ次循环贪心选择 x ← SELECT( A ) //从A中选取某个元素到x if FEASIBLE( solution, x) //是否能够构成可行解 then solution ← UNION( solution, x) //加入解 endif repeat return (solution)
贪心法适用范围 满足优化原则的组合优化问题 什么是组合优化问题 X有穷的变量集合 活动集合S={<sinf>|1≤i≤n} Y有穷的值集合 相容活动集A是{1,…,n}的子集 f(x)目标函数 max JAl G约束条件集合 s或s2f(1≤i<j<≤n) 个组合优化问题的解是对变量集X的一组赋值gX->Y 并直在满足G中约束条件的前提下使得目标函数f(x)取得最大 小)值
贪心法适用范围 ◼ 满足优化原则的组合优化问题 ◼ 什么是组合优化问题 ◼ X 有穷的变量集合 ◼ 活动集合S = {<si ,fi>|1≤i ≤n} ◼ Y 有穷的值集合 ◼ 相容活动集A 是{1,…,n}的子集 ◼ f(x) 目标函数 ◼ max |A| ◼ G 约束条件集合 ◼ si≥fj或sj ≥ fi (1 ≤ i<j< ≤ n) ◼ 一个组合优化问题的解是对变量集X的一组赋值 g: X->Y， 并且在满足G中约束条件的前提下使得目标函数f(x)取得最大 （小）值
贪心法适用范围 优化原则 个最优决策序列的任何子序列本身 定是相对于子序列的初始和结束状态的 最优的决策序列,即“最优子结构性质” 例:从北京经过广州到海南的最短距离,肯 定包括北京到广州的最短距离,以及广州到 海南的最短距离 活动选择问题
贪心法适用范围 ◼ 优化原则 ◼ 一个最优决策序列的任何子序列本身一 定是相对于子序列的初始和结束状态的 最优的决策序列，即“最优子结构性质” ◼ 例：从北京经过广州到海南的最短距离，肯 定包括北京到广州的最短距离，以及广州到 海南的最短距离 ◼ 活动选择问题
贪心法适用范围 贪心选择性质——正确性 ■所求问题的最优解,可以通过一系列的局 部最优解的选择,即贪心选择得到 ■满足贪心选择得到最优解,否则为近似解 般采用数学归纳法证明最优解 对选择步骤归纳 对问题规模归纳
贪心法适用范围 ◼ 贪心选择性质——正确性 ◼ 所求问题的最优解，可以通过一系列的局 部最优解的选择，即贪心选择得到 ◼ 满足贪心选择得到最优解，否则为近似解 ◼ 一般采用数学归纳法证明最优解 ◼ 对选择步骤归纳 ◼ 对问题规模归纳