11. 用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为的方格阵列，扩展每个结点需o(1)的时间，l为最短布线路径的长度，则算法共耗时 ( o(mn) )构造相应的最短距离需要（o(l)）时间。
12. 用回溯法解图的m着色问题时，使用下面的函数ok检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（o（mn））。
13. 旅行售货员问题的解空间树是（排列树）。
二、 证明题。
1. 一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。
再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用t(n)表示该分治法解规模为|p|=n的问题所需的计算时间，则有：
通过迭代法求得t（n）的显式表达式为：
试证明t（n）的显式表达式的正确性。
2. 举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。
证明：举例如：p=,w=,c=4时，由于7/3最大，若按题目要求的方法，只能取第一个，收益是7。而此实例的最大的收益应该是8，取第2，3 个。
3. 求证：o(f(n))+o(g(n)) o(max) 。
证明：对于任意f1(n) o(f(n)) 存在正常数c1和自然数n1，使得对所有nn1，有f1(n) c1f(n) 。
类似地，对于任意g1(n) o(g(n)) 存在正常数c2和自然数n2，使得对所有nn2，有g1(n) c2g(n) 。
令c3=max， n3 =max，h(n)= max 。
则对所有的 n n3，有。
f1(n) +g1(n) c1f(n) +c2g(n)
c3f(n) +c3g(n)
c3(f(n) +g(n))
c32 max
2c3h(n) =o(max) .
4. 求证最优装载问题具有贪心选择性质。
最优装载问题：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为wi。
最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 设集装箱已依其重量从小到大排序，(x1,x2,…,xn)是最优装载问题的一个最优解。又设。
如果给定的最优装载问题有解，则有。）
证明：三、 解答题。
1. 机器调度问题。
问题描述：现在有n件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为si，完成时间为fi，si问题实例：
若任务占用的时间范围是，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法）
画出工作在对应的机器上的分配情况。
2. 已知非齐次递归方程： ，其中，b、c是常数，g(n)是n的某一个函数。则f(n)的非递归表达式为：。
现有hanoi塔问题的递归方程为： ，求h(n)的非递归表达式。
解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n递推到1，有：
3. 单源最短路径的求解。
问题的描述：给定带权有向图（如下图所示）g =(v,e)，其中每条边的权是非负实数。另外，还给定v中的一个顶点，称为源。
现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
解法：现采用dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。
4. 请写出用回溯法解装载问题的函数。
装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。
如果有，找出一种装载方案。
解：void backtrack (int i)
if (cw + r > bestw)
r +=w[i];
5. 用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。
解答：斜线标识的部分完成的功能为：提前更新bestw值；
这样做可以尽早的进行对右子树的剪枝。具体为：算法maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。
因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0 故ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。
为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。
7. 最长公共子序列问题：给定2个序列x=和y=，找出x和y的最长公共子序列。
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列xi和yj的最长公共子序列的长度。其中， xi=；yj=。
当i=0或j=0时，空序列是xi和yj的最长公共子序列。故此时c[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：
在程序中，b[i][j]记录c[i][j]的值是由哪一个子问题的解得到的。
1） 请填写程序中的空格，以使函数lcslength完成计算最优值的功能。
2） 函数lcs实现根据b的内容打印出xi和yj的最长公共子序列。请填写程序中的空格，以使函数lcs完成构造最长公共子序列的功能（请将b[i][j]的取值与（1）中您填写的取值对应，否则视为错误）。
算法设计与分析复习
12 动态规划算法基本思想 自底向上 全局最优 讲带求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是 适用于动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。最优子结构性质 问题的最优解包含了其子问题的最优解 子问题重叠性质 在用递归算法自顶...
算法设计与分析复习
分治法求全排列。算法描述。分治法求解问题分为三个步骤 分解 将问题分为若干个子问题。解决 递归地求解每个子问题。合并 将每个子问题的解合并成为整个问题的解。现在我们需要求具有n个元素的数组a的全排列。例如 大小为3的数组a a,b,c 为方便起见，我把引号全都省略了，其实应该是a a b c 下同 ...
算法分析与设计复习
一 迪杰斯特拉算法。1 对下图中的有向图，应用dijkstra优化算法计算从源顶点0到其它顶点间最短路径。2 利用优化的dijkstra算法求解以节点1为源节点到其他各个节点。的的最短路径。用贪心法求解，写出具体步骤 二 多波段图问题。1 用动态规划法求下图中从源点0到终点8的最短路径，写出具体步骤...