2013《计算机算法设计与分析》习题及答案

四、证明题

1.举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。

证明：举例如：p={7,4,4},w={3,2,2},c=8时，由于7/3最大，若按题目要求的方法，只能取第一个，解为{1,0,0}，入包重量是7，价值为3。而此实例的最大价值应该是4，取第2，3 个，最优解为{0,1,1}。

2.旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。证明TSP问题满足最优性原理

证明：设s, s1, s2, …, sp, s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径，显然s1, s2, …, sp, s一定构成一条从s1到s的最短路径。 如若不然，设s1, r1, r2, …, rq, s是一条从s1到s的最短路径且经过n-1个不同城市，则s, s1, r1, r2, …, rq, s将是一条从s出发的路径长度最短的简单回路且比s, s1, s2, …, sp, s要短，从而导致矛盾。所以，TSP问题满足最优性原理。 五、问(解)答题

1. 试述分治法的基本思想

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

2. 设计动态规划算法有哪些主要步骤 设计动态规划算法的主要步骤为：

（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。

3. 分治法与动态规划法的异同 分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。

4.比较分支限界法与回溯法的异同

分支限界法与回溯法的相同点是：都是一种在问题的解空间树T中搜索问题解的算法。不同点：（1）求解目标不同；（2）搜索方式不同；（3）对扩展结点的扩展方式不同； （4）存储空间的要求不同。

5.写出回溯法搜索子集树的算法 用回溯法搜索子集树的算法为： void backtrack (int t) { if (t>n) output(x); else

for (int i=0;i<=1;i++) { x[t]=i;

9

if (constraint(t)&&bound(t)) backtrack(t+1); }

}

6. 分治法所能解决的问题一般具有哪些特征 分治法所能解决的问题一般具有的几个特征是：

（1）该问题的规模缩小到一定的程度就可以容易地解决；

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质; （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 7. 分支限界法设计算法有哪些步骤 用分支限界法设计算法的步骤是：

(1)针对所给问题，定义问题的解空间（对解进行编码）；分 (2)确定易于搜索的解空间结构（按树或图组织解） ；

(3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

8. 常见的两种分支限界法的算法框架是什么 常见的两种分支限界法的算法框架

（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

9. 回溯法中常见哪两类典型的解空间树？分析各自的使用场合及时间复杂度。 回溯法中常见的两类典型的解空间树是子集树和排列树。

当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称

nn

为子集树。这类子集树通常有2个叶结点，遍历子集树需O(2)计算时间 。

当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。

10. 分支限界法的搜索策略是什么？ 分支限界法的搜索策略是：

在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。

11.使用动态规划法求解TSP问题。

各个城市间的距离可以用代价矩阵来表示。

带权图的代价矩阵

假设n个顶点用0～n-1的数字编号，首先生成1～n-1个元素的子集存放在数组V[2n-1]中，设数组d[n][2n-1]存放迭代结果，其中d[i][j]表示从顶点i经过子集V[j]中的顶点一次且仅一次，最后回到出发点0的最短路径长度。

填表方法：自底向上，逐步求值。利用前一步求出的值计算出后一步的值填入表中，每

10

一步结束后选择最小值作为子问题的最优值，最后一步为原问题的最优解。

完成以下表格的填写 j {} i 0 1 2 3 5 6 3 第1步 9 12 {1} 8 11 第2步 {2} {3} 6 5 {1,2} 14 {1,3} 10 第3步 {2,3} 7 {1,2,3} 10 第4步 最短路径为：0→1→2→3→0，最短路径长度为：10 填表过程如下：

第1步：填写第1列，

d(1, {})=c10=5 (1→0)； d(2, {})=c20=6 (2→0)； d(3, {})=c30=3 (3→0) 第2步：

d(1, {2})= c12+d(2, {})=2+6=8(1→2) d(1, {3})= c13+d(3, {})=3+3=6(1→3) d(2, {1})= c21+d(1, {})=4+5=9(2→1) d(2, {3})= c23+d(3, {})=2+3=5(2→3) d(3, {1})= c31+d(1, {})=7+5=12(3→1) d(3, {2})= c32+d(2, {})=5+6=11(3→2) 第3步：

d(1, {2, 3})=min{c12+d(2, {3}), c13+ d(3, {2})}=min{2+5, 3+11}=7(1→2) d(2, {1, 3})=min{c21+d(1, {3}), c23+ d(3, {1})}=min{4+6, 2+12}=10(2→1) d(3, {1, 2})=min{c31+d(1, {2}), c32+ d(2, {1})}=min{7+8, 5+9}=14(3→2) 第4步：

d(0, {1, 2, 3})=min{c01+ d(1, { 2, 3}), c02+ d(2, {1, 3}), c03+ d(3, {1, 2})} =min{3+7, 6+10, 7+14}=10(0→1) 六、算法设计题

1. 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。 写出二分搜索的算法，并分析其时间复杂度。

template

int BinarySearch(Type a[], const Type& x, int n)

{//在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-1 Int left=0; int right=n-1; While (left<=right)

{int middle=(left+right)/2;

if (x==a[middle]) return middle; if (x>a[middle]) left=middle+1; else right=middle-1; }

Return -1;

}

时间复杂性为O(logn)

11

2. 利用分治算法写出合并排序的算法，并分析其时间复杂度 void MergeSort(Type a[], int left, int right) {

if (left

merge(a, b, left, i, right); //合并到数组b copy(a, b, left, right); //复制回数组a } }

算法在最坏情况下的时间复杂度为O(nlogn)。 3.N皇后回溯法

bool Queen::Place(int k) { //检查x[k]位置是否合法 for (int j=1;j

if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true;

}

void Queen::Backtrack(int t) {

if (t>n) sum++;

else for (int i=1;i<=n;i++) {x[t]=i;

if ( 约束函数 ) Backtrack(t+1); }

}

4.最大团问题

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 < i; j++)

if (x[j] && a[i][j] == 0) // i与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); }

12