算法设计与分析试题

《算法设计与分析试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Ø贪心算法总体思想顾名思义，贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路径问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。Ø棋盘（骨牌）覆盖问题算法思想一个2k×2k（k为非负整数）个方格组成的特殊棋盘中，有一个方格为特殊方格。用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方

2、格，任何2个L型骨牌不得重叠覆盖。4种L型骨牌核心算法思想：分治思想在2×2个方格组成的棋盘中用到的L型骨牌有(4-1)/3个。从分治的思想易得到需将问题微型化，于是我们将棋盘平均分成四个相似的棋盘。若特殊方格恰在图示的第一块区域，为了符合分治思想我们需要将其他三部分转化成同样具有特殊方格的棋盘，依次递归直到棋盘为1×1的规模即可解决问题。Ø符号三角形问题算法思想第1行有n个符号。两个同号下是“＋”，两个异号下是“－”。对于给定n，计算有多少个不同符号三角形，使其所含的“＋”和“－”的个数相同。u回溯法是一种通用性解法，可以将回溯法看作是带优化的穷举法。

3、u回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。u在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。减枝：＋(－)个数超过n*(n+1)/4；n*(n+1)/2为奇数，对于符号三角形问题，用n元组x[1：n]表示符号三角形的第一行的n个符号。当x[i]=1时，表示符号三角形的第一行的

4、第i个符号为“+”号；当x[i]=0时，表示符号三角形的第一行的第i个符号为“-”号；1≤i≤n。由于x[i]是二值的，所以在用回溯法解符号三角形问题时，可以用一棵完全二叉树来表示其解空间。在符号三角形的第一行的前i个符号x[1：i]确定后，就确定了一个由i*（i+1）/2个符号组成的符号三角形。下一步确定了x[i+1]的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为x[1：i+1]所相应的符号三角形。最终由x[1：n]所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*（n+1）/4。因此在回溯搜索过程中可用当前符号三角形所包含

5、的“+”号个数与“-”号个数均不超过n*（n+1）/4作为可行性约束，用于剪去不满足约束的子树。对于给定的n，当n*（n+1）/2为奇数时，显然不存在所包含的“+”号个数与“-”号个数相同的符号三角形。Ø用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。证明：最长公共子序列问题的动态规划算法的递归结构为：ØØØ动态规划与分治法相同之处是也将原问题分解为若干子问题，再递归求解；不同之处是所分解的子问题彼此并不独立，而是互有重叠。a)最长公共子序列的结构若用穷举搜索法，耗时太长，算

6、法需要指数时间。易证最长公共子序列问题也有最优子结构性质设序列X=和Y=的一个最长公共子序列Z=，则：i.若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；ii.若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列；iii.若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。其中Xm-1=，Yn-1=，Zk-1=。最长公共子序列问题具有最优子结构性质。b

7、)子问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X

8、和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即