13. 旅行售货员问题的解空间树是（排列树）。 二、
解答题
1. 机器调度问题。
问题描述：现在有n件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为si，完成时间为fi，si 问题实例：若任务占用的时间范围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法） 画出工作在对应的机器上的分配情况。 ?f(n)?bf(n?1)?g(n)2. 已知非齐次递归方程：? ，其中，b、c是常数， f(0)?c?g(n)是n的某一个函数。则f(n)的非递归表达式为：f(n)?cb??bn?ig(i)。 ni?1n?h(n)?2h(n?1)?1现有Hanoi塔问题的递归方程为：? ，求h(n)的非递归表 h(1)?1?达式。 解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n递推到1，有： h(n)?cbn?1??bn?1?ig(i)i?1n?1?2n?1?2n?2?...?22?2?1 ?2n?13. 单源最短路径的求解。问题的描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。 迭代 S {1} u - dist[2] dist[3] dist[4] dist[5] 10 maxint 30 100 初始 1 2 3 4 4. 请写出用回溯法解装载问题的函数。 装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船， 其中集装箱i的重量为wi，且 ?w?cii?1n1?c2。装载问题要求确定是否有一个合理 的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。 解：void backtrack (int i) {// 搜索第i层结点 if (i > n) // 到达叶结点 更新最优解bestx,bestw;return; r -= w[i]; if (cw + w[i] <= c) {// 搜索左子树 x[i] = 1; cw += w[i]; backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) { x[i] = 0; // 搜索右子树 backtrack(i + 1); } r += w[i]; } 5. 用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。 解答：斜线标识的部分完成的功能为：提前更新bestw值； 这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。 为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。 7. 最长公共子序列问题：给定2个序列X={x1,x2,?,xm}和Y={y1,y2,?,yn}，找出X和Y的最长公共子序列。 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中， Xi={x1,x2,?,xi}；Yj={y1,y2,?,yj}。当i=0或j=0时，空序列是Xi和Yj // 检查左儿子结点 Type wt = Ew + w[i]; // 左儿子结点的重量 if (wt <= c) { // 可行结点 if (wt > bestw) bestw = wt; // 加入活结点队列 if (i < n) Q.Add(wt); } // 检查右儿子结点 if (Ew + r > bestw && i < n) Q.Add(Ew); // 可能含最优解 Q.Delete(Ew); // 取下一扩展结点 的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立 ?0i?0,j?0?递归关系如下：c[i][j]??c[i?1][j?1]?1i,j?0;xi?yj ?max{c[i][j?1],c[i?1][j]}i,j?0;x?yij?在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。 （1） 请填写程序中的空格，以使函数LCSLength完成计算最优值的功能。 void LCSLength(int m，int n，char *x，char *y，int **c，int **b) { int i，j; for (i = 1; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;} else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } 2） 函数LCS实现根据b的内容打印出Xi和Yj的最长公共子序列。请填（写程序中的空格，以使函数LCS完成构造最长公共子序列的功能（请将b[i][j]的取值与（1）中您填写的取值对应，否则视为错误）。 8.对下面的递归算法，写出调用f(4)的执行结果。 void LCS(int i，int j，char *x，int **b) { if (i ==0 || j==0) return; if (b[i][j]== 1) { LCS(i-1，j-1，x，b); cout< } void f(int k) { if( k>0 ) { printf(\ f(k-1); f(k-1); } 一、简要回答下列问题 ： 1. 算法重要特性是什么？ 2. 算法分析的目的是什么？ 3. 算法的时间复杂性与问题的什么因素相关？ 4. 算法的渐进时间复杂性的含义？ 5. 最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 6. 简述二分检索（折半查找）算法的基本过程。 7. 背包问题的目标函数和贪心算法最优化量度相同吗？ 8. 采用回溯法求解的问题，其解如何表示？有什么规定？ 9. 回溯法的搜索特点是什么？ 10. n皇后问题回溯算法的判别函数place的基本流程是什么？ 11. 为什么用分治法设计的算法一般有递归调用？ 12. 为什么要分析最坏情况下的算法时间复杂性？ 13. 简述渐进时间复杂性上界的定义。 14. 二分检索算法最多的比较次数？ 15. 快速排序算法最坏情况下需要多少次比较运算？ 16. 贪心算法的基本思想？ 17. 回溯法的解（x1,x2,??xn）的隐约束一般指什么？ 18. 阐述归并排序的分治思路。 19. 快速排序的基本思想是什么。 20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？ 21. 什么是哈密顿环问题？ 22. 用回溯法求解哈密顿环，如何定义判定函数？ 23. 请写出prim算法的基本思想。 参考答案：1. 确定性、可实现性、输入、输出、有穷性 2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。 4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度： W(n) = max{ T(n，I) } , I∈Dn