三、 证明题
1. 一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分
解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，
O(1)n?1?则有：T(n)??
?kT(n/m)?f(n)n?1通过迭代法求得T（n）的显式表达式为：T(n)?n试证明T（n）的显式表达式的正确性。
2. 举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。
证明：举例如：p={7,4,4},w={3,2,2},c=4时，由于7/3最大，若按题目要求的方法，只能取第一个，收益是7。而此实例的最大的收益应该是8，取第2，3 个。
3. 求证：O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 。
证明：对于任意f1(n)? O(f(n)) ，存在正常数c1和自然数n1，使得对所有n?n1，有f1(n)? c1f(n) 。
类似地，对于任意g1(n) ? O(g(n)) ，存在正常数c2和自然数n2，使得对所有n?n2，有g1(n) ?c2g(n) 。
令c3=max{c1, c2}， n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。 则对所有的 n ? n3，有
f1(n) +g1(n) ? c1f(n) + c2g(n) ? c3f(n) + c3g(n)
= c3(f(n) + g(n))
? c32 max{f(n),g(n)} = 2c3h(n) = O(max{f(n),g(n)}) .
logmk?logmn?1?j?0kjf(n/mj)
4. 求证最优装载问题具有贪心选择性质。
（最优装载问题：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 设集装箱已依其重量从小到大排序，(x1,x2,…,xn)是最优装载问题的一个最优解。又设k?min{i|xi?1} 。如果给定的最优装载问题有解，
1?i?n则有1?k?n。）
证明： 四、
解答题
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?1 3. 单源最短路径的求解。 问题的描述：给定带权有向图（如下图所示）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. 用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。 // 检查左儿子结点 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); // 取下一扩展结点
相关推荐：
loading