2017《算法设计与分析》A卷自做答案

---

选择题

1.C

如果可满足性约化为一个问题L，则称L是NP-难度的。如果L是NP难度的且L属于NP,则称问题L是NP完全的

从计算时间上可以把算法分成两类，多项式时间算法和指数时间算法。

2.B

3.D

4.B

宽度优先无限界 D检索 深度优先无限界 深度优先 宽度优先有限界 分支-限界 深度优先有限界 回溯法

5.C

简答题

${\sum}_{i=1}^{16}LESS(i)+X=12+1+1+8+2+10+6+4+4+5+1+1+2+1+1=59$

是奇数，所以不能到达目标状态。

当$n=2^k$时
$T(n)=4T(n/2)+n=4(4T(n/4)+n/2+n)=...=2^k(T(n/2^k))+(2^k-1)*n=O(n^2)$
3.

答：不一定，可能会出现成本估计函数c^(Y)>C(Z)但是C(Y)<C(Z)的情况，需要使用LC1函数选取成本估值函数作为成本函数的下界，这样才能找到最小成本函数。（请看慕课LC解锁特性）

证明题

1.若存在两个正常数c和$n_0$，对于所有的$n \geq n_0$，有$|f(n)| \geq c|g(n)|$，则记做$f(n)=\Omega((g(n)))$，称g(n)为f(n)的渐近下限。

证明：设置$h1(x)=\Omega{(f(n))}、h2(x)=\Omega{(g(n))}$,则有$|f(n)| \geq c1|h1(n)|$、$|g(n)| \geq c2|h2(n)|$，$min(f(n),g(n))\geq{c1|h1(n)|+c2|h2(n)|\geq{(c1+c2)min(|h1(n)|,|h2(n)|)}}$

得证

http://www.doc88.com/p-9734963937737.html

前往此处寻找同样题目

计算题

(1)

首先计算pi/wi的值

（p1/w1,p2/w2,p3/w3.p4/w4)=(5,5/2,2,2)

已经不需要排序

2+4+6<15且2+4+6+9>15

因此X=（1，1，1，1/3）

(2)
$S_0=\{(0,0)\} \\S^1_1=\{(10,2)\} S^1=\{(0,0),(10,2)\} \\S^2_1=\{(10,4),(20,6)\} S^2=\{(0,0),(10,2),(20,6)\} \\S^3_1=\{(12,6),(22,8),(32,12)\} S^3=\{(0,0),(10,2),(20,6),(22,8),(32,12)\} \\S^4_1=\{(18,9),(28,11),(38,15),(40,17),(50,21)\} \\S^4=\{(0,0),(10,2),(20,6),(28,11),(38,15)\} \\(38,15)不属于S^3，所以一定来自S^3_1，所以（20，6）属于S^3，x_4=1$

$（20，6）属于S^2，所以x_3=0 \\(20,6)不属于S^1，所以x_2=1,(10,2)属于S^1 \\综上可以得解X=（1，1，0，1）$

(1)

$状态空间树节点总数=1+6+6*5+6*5*4+6*5*4*3+6*5*4*3*2+6*5*4*3*2*1=1+6+6*5+120+360+720+720=1957$

(2)
$不受限结点数=1+6+6*3+6*3*2+6*3*2*2+6*3*2*2*1=205$
(3)
$比例=205/1957*100\%=10.48\%$

3.[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VKMVMNwu-1596007499452)(C:\Users\HP\Documents\Tencent Files\1102460059\FileRecv\MobileFile\IMG_3251(20200727-151138)].JPG)

(1)
$COST(12)=7 D(12)=15 COST(13)=3 D(13)=15 COST(14)=8 D(14)=15 \\COST(9)=MIN\{C(9,12)+COST(12),C(9,13)+COST(13),C(9,14)+COST(14)\}=MIN\{9+7,7+3,4+8\}=10 \\D(9)=13 \\COST(10)=MIN\{C(10,12)+COST(12),C(10,13)+COST(13)\}=MIN\{5+7,21+3\}=12 D(10)=12 \\COST(11)=MIN\{C(11,12)+COST(12),C(11,13)+COST(13),C(11,14)+COST(14)\}=MIN\{1+7,17+3,9+8\}=8 \\D(11)=12$

$COST(6)=MIN\{C(6,9)+COST(9),C(6,10)+COST(10),C(6,11)+COST(11)\}=MIN\{8+10,6+12,8+4\}=12 \\D(6)=11 \\COST(7)=MIN\{C(7,9)+COST(9),C(7,11)+COST(11)\}=MIN\{1+10,15+12\}=11 D(7)=9 \\COST(8)=MIN\{C(8,9)+COST(9),C(8,10)+COST(10),C(8,11)+COST(11)\}=MIN\{7+10,8+12,1+8\}=9 \\D(8)=11$

$COST(2)=MIN\{C(2,6)+COST(6),C(2,7)+COST(7)\}=MIN\{3+12,4+9\}=13 D(2)=7 \\COST(3)=MIN\{C(3,6)+COST(6),C(3,8)+COST(8)\}=MIN\{12+12,1+9\}=10 D(3)=8 \\COST(4)=MIN\{C(4,6)+COST(6),C(4,7)+COST(7),C(4,8)+COST(8)\}=MIN\{1+12,7+9,9+9\}=13 \\D(4)=8 \\COST(5)=MIN\{C(5,7)+COST(7),C(5,8)+COST(8)\}=MIN\{6+9,11+9\}=15 D(5)=8$

$COST(1)=MIN\{9+13,4+10,3+13,8+15\}=14 \\D(1)=3$

可得最小成本是14

（2）

D(1)=3 D(3)=8 D(8)=11 D(11)=12 D(12)=15

所以路径为1->3->8->11->12->15

设计算法

(1)算法思路，设置一个循环，left>right的时候停止

设置变量p1=right+$\lfloor(right-left)/3\rfloor$=$\lfloor(right+2left)/3\rfloor$

p2=right-$\lfloor(right-left)/3\rfloor$=$\lfloor(2right+left)/3\rfloor$

如果要找的数m=A[p1]或者m=A[p2]则返回坐标，否则缩小区域到三分之一

(2)

procedure ThriSearch(A,n,m,j)
integer left=1
integer right=n
integer p1,p2
while(left<=right)
p1=（right+2left）/3
p2=(2right+left)/3
case:m=A(p1):j=p1;return:m=A(p2)j=p2;return:m<A(p1)right=p1-1:m>A(p2)left=p2+1:else low=p1+1 high=p2-1
endcase
repeat
j=0
end ThriSearch

(3)

解:可以得到以下关系
$T(n)=1//当只有一个元素 \\T(n)=2//当有两个元素 \\T(n)=T(n/3)+2//当有两个以上元素 \\设置n=3^k \\T(n)=T(n/9)+2+2=T(n/3^k)+2k=c+2log_3n=O(log_3(n))$

设置

算法策略：

使用dfs 通过递推关系式g(i,S)=min{cij+g(j,s-{j})}得出答案

procedure TSP(integer num,integer i)
global integer shuzu(1...n,1...n)//这里存储了图中各节点之间的距离
global boolean po(1...n)//这里存储的是集合中是否包含该结点，先被初始化为true,po(1)设置成false
integer ans=MAX_VALUE
integer jiedian(100)
jiedian(1)=i
if num=0 return shuzu(i,1)//当集合为空，返回节点到1的值
for x=2 to n by +1
if(po(x)==true)
ans=min(ans,shuzu(i,x)+TSP(num-1,x))
把导致距离最小的节点加入jiedian数组
repeat
return jiedian数组和ans

import java.util.Arrays;
import java.util.Scanner;
public class Demo {public static boolean[] use;public static int n;public static int[][] shuzu;public static void main(String argv[]) {Scanner scan=new Scanner(System.in);n=scan.nextInt();use=new boolean[n];  shuzu=new int[n][n];for(int i=0;i<n;i++){shuzu[i]=new int[n];for(int j=0;j<n;j++){shuzu[i][j]=scan.nextInt();}}scan.close();Arrays.fill(use, true);//System.out.print(Integer.MAX_VALUE);use[0]=false;//首先禁止起点被访问了System.out.print(doit(n-1,0)); }public static int doit(int num,int nowi)//num是当前集合的长度,nowi是出发的起点{if(num==0) {//System.out.print(shuzu[nowi][0]);return  shuzu[nowi][0];}int ans=Integer.MAX_VALUE;for(int i=1;i<n;i++){if(use[i]==true){use[i]=false;ans=Math.min(ans,shuzu[nowi][i]+doit(num-1,i));use[i]=true;}}return ans;}
}

时间空间复杂度

时间复杂度$O(n^22^n)$

空间复杂度$O(n2^n)$