算法设计策略-算法设计与分析.ppt

第2部分 算法设计策略 最优化问题（optimization problems）是指这样一类问题，问题给定某些约束条件（constraint），满足这些约束条件的问题解称为可行解（feasible solution）。通常满足约束条件的解不是惟一的。为了衡量可行解的好坏，问题还给出了某个数值函数，称为目标函数（objective function），使目标函数取最大（或最小）值的可行解称为最优解（optimal solution）。 6.2.1? ?问题描述 6.2.2 贪心法求解 6.2.3? 算法正确性 证明： 设X=(x0, x1, …, xn-1)， 0≤xj ≤ 1 ,0≤i＜n是贪心背包算法所生成的贪心解。 ① 如果所有的xi都等于1,则显然X就是问题的最优解。否则， 设j是使xi≠1的最小下标。由算法的执行过程可知， 解的形式为： X=(1, …, 1,xj,0, …, 0) 即xi=1 0≤i＜j, 0≤xj ＜1,xi=0 j＜i≤n-1 假设Y是问题的最优解：Y=(y0, y1, …, yn-1) 且有： ● 若X ＝ Y，则X就是最优解。否则， ● X和Y至少在1个分量上存在不同。 设k是使得yk≠ xk的最小下标，则有yk＜ xk。可分以下情况说明： a) 若kj，则xk=1。因为yk≠ xk,从而有yk ＜ xk b) 若k=j，由于 ，且对1≤i＜j，有yi=xi=1,而对j＜i≤n,有xi＝0；故此时若yk＞xk，则将有 ，与Y是可行解相矛盾。而yk≠ xk,所以yk ＜ xk c) 若k＞j，则 ，不能成立 在Y中作以下调整：将yk 增加到 xk ，因为yk＜xk,为保持解的可行性，必须从(yk+1,…,yn-1)中减去同样多的量。设调整后的解为Z=(z0, z1, …,zk,zk+1, …, zn-1)，其中zi＝xi，0≤i≤k，且有： Z的效益值有： 由以上分析得， 若 ，则Y将不是最优解； 若 ，则或者Z=X，则X就是最优解； 或者Z≠X，则重复以上替代过程，或者证明Y不是最优解，或者把Y转换成X，从而证明X是最优解 最优装载 有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 1.算法描述 最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下: templateclass Type void Loading(int x[], Type w[], Type c, int n) { int *t = new int [n+1]; Sort(w, t, n); for (int i = 1; i = n; i++) x[i] = 0; for (int i = 1; i = n w[t[i]] = c; i++) {x[t[i]] = 1; c -= w[t[i]];} } 2.贪心选择性质 可以证明最优装载问题具有贪心选择性质。 3.最优子结构性质 最优装载问题具有最优子结构性质。 由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。 算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。 活动安排问题 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。 templateclass Type void GreedySelector(int n, Type s[], Type f[], bool A[]) { A[1]=true; int j=1; for (int i=2;i=n;i+