发布时间 : 星期四 文章《算法分析与设计》期末考试复习题纲(完整版)更新完毕开始阅读
例3：最大团问题，要会画解空间树。 class Clique {
friend int MaxClique(int **,int [],int); public:
void Print(); //输出最优解 private:
void Backtrack(int i);
int **a; //图G的邻接矩阵，下标从1开始 int n; //图G的顶点数 int *x; //当前解 int *bestx; //当前最优解 int cn; //当前团的顶点数 int bestn; //当前最大团的顶点数 };
void Clique::Backtrack(int i) { if(i>n)
{ for(int j=1;j<=n;j++) bestx[j]=x[j]; bestn=cn; return;} //判断第i个顶点是否与已选顶点都有边相连 int OK=1;
for(int j=1;j { OK=0; break; } //只要与当前团中一个顶点无边相连，则中止 if(OK) //进入左子树 { x[i]=1; cn++; Backtrack(i+1); x[i]=0; cn--; } if(cn+n-i>bestn) //如有可能在右子树中找到更大的团，则进入右子树 { x[i]=0; Backtrack(i+1); } } 计算时间：O(n2) n 四、 简答题 1. 请简述使用动态规划算法解题的基本步骤。P44 动态规划的设计分为以下4个步骤： (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。 2. 简述动态规划方法与分治法的异同。P44 相同点：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,然后从这些子问题的解得到原问题的解。 不同点：分治法的子问题互相独立且与原问题相同。与分治法不同的是，适合于动态规划求解的问题，经分解得到的子问题往往不是互相独立的。也就是各个子问题包含公共的子子问题。 3. 试比较Prim算法与Kruskal算法的异同。105-P107 相同点：Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法都可以看作是应用贪心算法构造最小生成树的例子。利用了最小生成树性质。 不同点： Prim(普里姆)算法：在这个过程中选取到的所有边恰好构成G的一棵最小生成树T，T中包含G的n-1条边，且不形成回路。 Kruskal(克鲁斯卡尔)算法：是构造最小生成树的另一个常用算法。该算法不是通过扩充连通子集来进行贪心选择。而是通过选择具有最小权的边的集合来进行贪心选择。在选择的同时可以进行连通操作以便形成生成树。 4. 请简述分支限界法的搜索策略。P161 课件第6章(1)第6页 (1)分支限界法以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 (2)每一个活结点只有一次机会成为扩展结点。 (3)活结点一旦成为扩展结点，就一次性产生其所有儿子结点。 (4)儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 (5)从活结点表中取 下一结点 成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 5. 试比较分支限界法与回溯法的异同。P161 课件第6章(1)第5页 不同点： (1)求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 (2)搜索方式：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 五、算法应用题 1. 用动态规划求解凸多边形最优三角剖分问题。 三角剖分的结构及其相关问题P61 (1)语法树与完全加括号方式 一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。 例如，完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))所相应的语法树如图 (a)所示。 (2)语法树与凸多边形三角剖分 凸多边形P={v0,v1,…vn-1}的三角剖分也可以用语法树表示。 如图：根结点是边v0v 6(可以任选)。其他边则是语法树的叶子节点。 v0v 6是三角形v0v3v 6的一条边。 2、三角剖分与矩阵连乘P61 (1)一般来说，凸多边形的三角剖分和有n-1个叶节点的语法树存在一一对应关系。 (2)N个矩阵连乘的完全加括号和有n个叶节点的语法树也存在一一对应关系 。 (3)所以，n个矩阵连乘的完全加括号和有n+1个节点的凸多边形的三角剖分也存在一一对应关系。 (4)矩阵连乘积中A1 A2 …An中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，i (5)矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的特殊情况。 课后习题（第3章小结**） 对于如下矩阵链 P={10,100,5,50,30,20,60,45,50}，请按照构造其最优完全加括号方式，并列出相应的语法树和最优三角剖分图。