欢迎阅读
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
(3). 继续向下搜索生成结点F，得到可行解(1,1,1,0,0)，得到价值为86，更新bestp=86(如图第3步) 第3步 第5步 第8步
欢迎阅读
(4). 回溯：沿E回溯到左孩子D，生成相应右孩子G，得到部分解( 1,1,0,1 ),此时b=93.1 b>bestp,可以生成右子树（第4步在第5步的基础上没有H和I的图形）
(5). 继续生成结点H,I，得到可行解( 1,1,0,1,0 ),价值为88，更新bestp=88(如图第5步)
(6). 回溯H生成J，得到部分解( 1,1,0,0 ),估计部分解b=92>88（第6步在第8步的基础上没有K和L的图形）
(7). 继续生成结点K，得到可行解( 1,1,0,0, 1 ),价值为92，更新bestp=92（第7步在第8步的基础上没有L的图形）
(8). K是左孩子，生成其对应的右孩子L，得到可行解( 1,1,0,0,0) (如图第8步)
(9). 回溯,沿结点L向上回溯到结点B,生成结点M,得到部分解 (1,0), 估计部分解b=90<92,回溯（第9步在第10步的基础上没有N的图形） (10). 向上继续回溯生成结点N，得到部分解(0)，此时得到的b=74+10*(46/27) =91.03<92,回溯，此时已回到根结点，结束。最优解( 1,1,0,0, 1 ),价值为92. (如图第10步) 练习
n=8, M=110， W=( 1, 11,21,23,33,43,45,55 ) P=(11,21,31,33,43,53,55,65 ) 用回溯法求此0-1背包问题的最优解。 最优装载问题 P119 课件第P37- P54页 假定n= 4，w= [ 8 , 6 , 2 , 3 ]，c1 = c2 =12. 试根据改进后的最优装载算法找出最优装载量及相应的最优装载方案。 要求：
a) 列出问题的解空间。 b) 构造解空间树。 c) 根据递归回溯算法求出最优解和最优值。 六、
算法设计题 使用贪心算法求解。 题型一： 开会问题： 某公司的会议很多，以至于全公司唯一的会议室不够用。现在给出这段时期的会议时间表，要求你适当删除一些会议，使得剩余的会议在时间上互不冲突，要求删除的会议数最少。 解题算法:
template
void GS (int n, Type s[], Type f[], bool A[]) {
A[1]=false; int j=1;
欢迎阅读
int sum=0;
for (int i=2;i<=n;i++) {
if (s[i]>=f[j]) { A[i]=false; j=i; } else {A[i]=true; sum++;} } } 题型二： 试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，写出该算法。先看看几个n比较小的例子，看能否从中找出规律： 算法分析： ? 猜想一下是不是将n拆成尽量多的数乘积最大？（拆出的数中最小为2）。 ? 为了使因数个数尽可能多，我们用n减2、3…i，直到n
? 先对两组马按速度排序。
? 如果田忌(A)最快的马比齐王(B)最快的马快,直接赢; ? 如果A最快的马比B慢,用A最慢的马拼B最快的马; ? 如果A最慢的马比B最慢的马快,直接拼掉;
欢迎阅读
? 如果A最慢的马比B最慢的马慢,用A最慢的马拼B最快的马; ? 如果A和B最快和最慢的马都速度相同,用A最慢的马拼B最快的马 算法分析:
相关推荐：
loading