近似算法课件.pptVIP

近似算法 经简单修改可得到近似度为2的算法 Proof 对于某一物品而言，或者装入或者不装入，所以背包问题又称为0/1背包问题。n个物品相当于一个具有n位的二进制数，共有2n个装入方案。可从2n个方案中找出最佳值，故穷举法的时间复杂性为Θ(2n)。若采用动态规划法，可在Θ(Cn)时间内得到最优解。 A Pseudopolynomial Algorithm 当i0且j0，V[i,j]是下面二个量的最大值： V[i-1,j]：从物品子集Ui-1中取出若干物品装入体积为j的背包中所形成的价值最大值（不装入物品ui）。 V[i-1,j-si]+vi：从物品子集Ui-1中取出若干物品装入容量为j-si的背包中所形成的价值最大值。在此基础上，再加上物品ui的价值vi，显然j≥si （装入物品ui）。 设Ui是物品集U的子集，它由U的前i项{u1,u2,...ui}构成。从Ui取出若干个物品装入体积为j的背包中，所形成的物品最大价值用V[i,j]表示，其中0≤i≤n、0≤j≤C。所以解值为V[n,C] 。 V[0,j]=0 直观意义为背包中无任何物品 V[i,0]=0 直观意义为背包的容量为0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 u0(0,0） 3 3 3 3 3 3 3 3 0 0 7 7 7 7 7 4 4 3 0 0 12 9 9 8 7 5 4 3 0 0 12 11 10 8 7 5 4 3 0 0 u1(2,3） u2(3,4） u3(4,5） u4(5,7） ui(si,vi) 物品 体积 物品集合： U={u1,u2,u3,u4} 物品体积集合： S={s1,s2,s3,s4}={2,3,4,5} 物品价值集合： V={v1,v2,v3,v4}={3,4,5,7} 背包体积： C=9 0 1 2 3 4 Knapsack 输入：背包容量C、物品体积集合 S = {s1,s2,...,sn}、物品价值集合V = {v1,v2,...,vn} 输出：可装入背包物品的最大总价值 （定义一个 二维数组V[0..n,0..C]用于计算和存放V[i,j]的值） 1. for i←0 to n V[i,0]←0 //背包容量为0 2. for j←0 to C V[0,j]←0 //背包未装入任何物品 3. for i←1 to n 4. for j←1 to C 5. if si j then //物品ui的体积si超过容量j，不装入。 6. V[i,j]←V[i-1,j] //取Ui-1的计算结果 7. else //物品ui的体积si不超过容量j，可装入。 8. V[i,j]←max(V[i-1,j],V[i-1,j-si]+vi) 9. end if 10. end for 11. end for 12. return V[n,C] //返回最大总价值 由于计算表的每一项需要Θ(1)时间，所以算法的时间复杂性恰好是表的大小Θ(nC)。 只要对算法Knapsack作简单的修改，就可输出装在背包中的物品。 由于计算当前行时仅需要上一行的值，因此只要对算法稍作修改，可以使算法的空间复杂性为Θ(C)。 类似可以设计时间复杂性为Θ(nW)的算法，其中W是所有物品的价值和。 思考题 输入：背包容量C、物品体积集合 S={s1,s2,...,sn}、物品价值集合V ={v1,v2,...,vn}, (其中每种物品的个数无限制) 输出：可装入背包物品的最大总价值 多项式近似方案 此近似算法运行时间为O(knk+1)，相似比不超过 1+1/k. 完全多项式近似方案(Page 444) * (Approximation Algorithms) 现在我们只考虑最优化问题。一些困难的组合优化问题没有有效的解决方案，在这种情况下，对于其中的一些问题代之以设计近似算法，我们要保证它是近似于最优解的一个“合理”的解。 每个近似解都有一个性能界，它保证任一个实例的近似解与精确解不会相差太多。大多数近似算法的一个显著特点是它们非常快，这是因为它们绝大多数是贪心启发式的算法。 然而要找一个有效的近似算法也并不乐观，甚至存在一些困难问题，似乎连“合理”的近似算法都可能不存在，除非NP=P。 组合优化问题Π是一个最大（或最小）化问题。它 由三部分组成： (1) 一个实例的集合DΠ； (2) 对每个实例 I ∈DΠ，存在I的一个候选解的有限 集合SΠ(I)； (3) 对DΠ中的一个实例I的每个候选解σ∈SΠ(I)