2015武汉大学《算法设计与分析》期中试卷(2)

n ← length[p] - 1 for i ← 1 to n m[i, i] ← 0 end for

for l ← 2 to n for i ← 1 to n – (l – 1) j ← i + (l – 1) m[i, j] ← ∞ for k ← i to j - 1

q ← m[i, k] + m[k + 1, j] + p[i-1] p[k]p[j] if q < m[i, j]

then m[i, j] ← q, s[i, j] ← k end if end for end for end for return m and s ｝

-----------------------得分2分

PRINT-OPTIMAL (s, i, j) 1 if i = j 2 then print \A\i

3 else print \

4 PRINT-OPTIMAL (s, i, s[i, j]) 5 PRINT-OPTIMAL (s, s[i, j] + 1, j) 6 print \

-----------------------得分2分

空间复杂度为?(n2)。

-----------------------得分1分

六、最大团问题：给定无向图G=(V,E)，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。如果给定U?V，且对任意两个顶点u，v∈U有(u,v)∈E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。（总分20分）

（1）请设计一个回溯算法（伪代码即可）来求解最大团问题；（10分） （2）你设计的算法的解向量如何表示？时间复杂度是多少？（5分） （3）假设有如下下图所示的问题实例，

132

试采用你设计的算法，把求解最大团的搜索过程详细写出来。（5分）

45参考答案：注意,本题会有多种解法,参考答案仅仅是一种,改卷子时一定要看清楚。

（1） 假设解向量采用等长的二进制编码（x1,x2,?,xn），其中n为图

中顶点的个数，回溯算法的递归版本代码如下：

Input: An undirected graph G=(V,E). Output: A solution vector x[1,2,…,n]. 1. for k?1 to n 2.

y[k]=x[k]?-1

3. end for 4. mcl?-1 5. maxcl(1,0,n) 6. output y 7. output mcl Procedure maxcl (k,r,l) 1. x(k) = 0 2. if k=n then

3. if r>mcl then {mcl = r, y=x} endif 4. else if r+l >macl then maxcl(k+1,r,l-1) 5. endif 6. x(k) =1

7. if 节点k与前面取值为1的节点均有边相连 then 8. if k=n then

9. if r>mcl then {mcl = r, y=x} endif 10. else maxcl(k+1,r+1,l-1) 11. endif 7. end if

-----------------------得分10分

（2） 解向量采用等长的二进制编码（x1,x2,?,xn），其中n为图中顶

点的个数。

-----------------------得分2分 时间复杂度为O(n2n)。

-----------------------得分3分

（3）求解过程如下图所示（由于先选取x(k)=0的节点先生成，本实例造成的树太大，所以我们先生成x(k)=1的节点，不管那种做法，答案都算对），其中红色无字方框是不满足要求的中间节点，红色有字方框为被限界的中间节点，红色圆形为不满足要求的解，灰色圆形为满足要求的解。

(1,0,5)X(1)=1X(1)=0(2,1,4)X(2)=1X(2)=0(2,0,4)X(2)=1X(2)=0(3,1,3)X(3)=1X(3)=0(3,1,3)X(3)=1(3,0,3)X(3)=0(4,2,2)X(4)=1X(4)=0(4,1,2)(4,1,2)(5,3,1)X(5)=1X(5)=0mcl=3(5,1,1)

-----------------------得分5分