算法与优化复习题补充.doc

1. 设X和Y都是n位二进制整数，若按普通乘法规则计算，要进行O(n2)步运算才能得到XY的乘积，若用分治法来计算，可有效地降低其复杂性。简述采用分治法求解XY乘积的基本过程。解：即为大整数的乘法（参照书上2.4节 P29）：2. 扩展Hanoi塔问题：设a,b,c,d是4个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n，现要求采用递归算法将塔座a上的这一叠圆盘移到塔座d上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c,d中任一塔座上。设计算法实现一种移动方案，并分析算法的时间复杂度。解：书2.1节例2.6 (P23)3. 比较分治法、动态规划法和贪心算法的使用条件。解：分治法和递归是紧密相联系的，分治法就是把大问题分解成小问题，然后大问题的解可以通过小问题的解得出来。小问题是相互独立的，可以递归解决。分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。如下问题使用分治法解决：计算逆序，找出平面上最近的点，等等经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。例如典型的Fibonacci数列的求解。两种动态规划算法：备忘录和迭代贪心法是自然的方法，也是最直观的方法，贪心法的当前选择依赖于已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择，但是该方法不能保证最后得出的解是最优的，需要反复选择策略，加以比较，有时候一些选择策略可以很巧妙的解决问题。贪心法主要有两种思想，即贪心算法领先和交换论证，用来证明所得的解是最优的，交换论证的思想为首先假设一个最优解和通过贪心法所得到的解，然后逐步修改最优解，但保持每步的最优性，最后使得最优解跟通过贪心法所得的解相同。 如下问题可用贪心法解决：区间调度，最小延迟调度，最短路径，最小生成树，聚类等等。4. 比较回溯法与分支限界法的区别。解：分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一些则不然。也许我们需要具体一些的分析到底何时使用分支限界而何时使用回溯呢？下表列出了回溯法和分支限界法的一些区别：方法对解空间树的搜索方式存储结点的常用数据结构结点存储特性常用应用回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解5. 概率算法分为哪几类？它们求得问题的解分别具有什么样的特点？解：1）数值概率算法：常用于数值问题的求解，得到的往往是近似解（1）解的精度随计算时间的增加而提高（2）在许多情况下，计算出问题的精确解是不可能或没必要2）蒙特卡罗算法：用于求解问题的准确解，可以求得问题的一个解，但该解未必正确（1）求得正确解的概率依赖于算法的计算时间，多次执行蒙特卡罗算法，可以提高获得正确解的概率（2）无法有效判定所得到的解是否肯定正确。3）拉斯维加斯算法：不会得到不正确的解（1）有时找不到问题的解（2）找到正确解的概率随算法计算时间的增加而提高（3）用同一拉斯维加斯算法反复对问题实例求解足够多次，可使求解失败的概率任意小。4）舍伍德算法：总能求解得到问题的一个解，而且所求得得解总是正确的。将确定性算法引入随机性改造成舍伍德算法，可消除或减少问题对于好坏实例间的差别。6. 给定非线性规划问题，验证下列两点是否为K-T点?解：参照群共享，最新刘伟整理的第3题。7. 简述无约束最优化问题的最优性条件。解：参照群共享，最新刘伟整理的第6题。8. 给定非线性规划问题，验证下列两点是否为K-T点?解：参照群共享，最新刘伟整理的第2题。9. 矩阵连乘问题可以采用动态规划法求得最少的数乘次数和最优的加括号方式，试证明该问题具有最优子结构性质。解;参照书3.1节，3.1矩阵连乘问题， 1.分析最优解的结构，在吹点牛B P63页。10. 设和都是线性函数，证明下面的约束问题是凸规划问题。解：参照群共享，最新刘伟整理的第1题。11. 背包问题可以采用贪心算法求得最优解，证明该问题满足贪心选择性质。解：参照群共享，旧的刘伟整理的第3题（后半段证明不要了）12. 以下为最小顶点覆盖问题的近似算法，其中cset用来存储顶点覆盖中的各顶点，初始为空，不断从边集e1中选取一边(u,v)，将边的端点加入cset中，并将e1中已被u和v覆盖的边删去，直至cset已覆盖所有边。证明该算法的性能比为2。VertexSet approxVertexCover (Graph g) cset=；e1=g.e； while (e1!=) 从e1中任取一条边(u,v)； cset=csetu,v； 从e1中删去与u和v相关联的所有边； return cset; 解：参照PPT第九章13. 二维0-1背包问题:给定n种物品和一背包。物品i的重量是wi，体积是bi，其价值为vi，背包的容量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。试设计一个解决此问题的动态规划算法，并分析算法的计算复杂性。解：参照群共享，旧的刘伟整理的第2题14. 旅行售货员问题：设G是有n个顶点的有向图,设计一带有上界函数的算法,提高原算法的效率.解：参照群共享，旧的刘伟整理的第14题15. 皇后控制问题:在一个n*n个方格组成的棋盘上的任一方格中放置一个皇后,该皇后可以控制所在的行,列以及对角线上的所有方格.对于给定的自然数n,在n*n个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格,且放置的皇后互不攻击.解：参照群共享，旧的刘伟整理的第15题16. 给定两个大整数u和v,它们分别有m和n位数字,且m=n.设计计算时间低于O(mn) 的算法.解：参照群共享，旧的刘伟整理的第1题17. 用DFP算法求解无约束最优化问题： 其中 取。解：参照群共享，最新的刘伟整理的第5题18. 用外点罚函数法求解约束最优化问题，取： 解：参照群共享，最新的刘伟整理的第7题19. 解顶点覆盖问题的一个启发式算法如下：每次选择具有最高度数的顶点，然后将与其相关联的所有边删去。举例说明该算法的性能比将大于2。解：参照群共享，旧版的刘伟整理的第6题20. 给定两个大整数u和v,它们分别有m和n位数字,且m=n.设计计算时间低于O(mn)