(Ew);//可能含最优解
(Ew);//取下一扩展结点
解答:
斜线标识的部分完成的功能为:
提前更新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的最长公共子序列。
故此时C[i][j]=0。
其它情况下,由最优子结构性质可建立递归关系如下:
在程序中,b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。
(1)请填写程序中的空格,以使函数LCSLength完成计算最优值的功能。
(2)函数LCS实现根据b的内容打印出Xi和Yj的最长公共子序列。
请填写程序中的空格,以使函数LCS完成构造最长公共子序列的功能(请将b[i][j]的取值与
(1)中您填写的取值对应,否则视为错误)。
8.对下面的递归算法,写出调用f(4)的执行结果。
voidf(intk)
{if(k>0)
{printf("%d\n",k);
f(k-1);
f(k-1);
}
}
一、填空题(20分)
1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算,此外,算法还应具有以下五个重要特性:
_________,________,________,__________,__________。
2.算法的复杂性有_____________和___________之分,衡量一个算法好坏的标准是______________________。
3.某一问题可用动态规划算法求解的显着特征是____________________________________。
4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X和Y的一个最长公共子序列_____________________________。
5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含___________。
6.动态规划算法的基本思想是将待求解问题分解成若干____________,先求解___________,然后从这些____________的解得到原问题的解。
7.以深度优先方式系统搜索问题解的算法称为_____________。
背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。
9.动态规划算法的两个基本要素是___________和___________。
10.二分搜索算法是利用_______________实现的算法。
二、综合题(50分)
1.写出设计动态规划算法的主要步骤。
2.流水作业调度问题的johnson算法的思想。
3.若n=4,在机器M1和M2上加工作业i所需的时间分别为ai和bi,且(a1,a2,a3,a4)=(4,5,12,10),(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案,并计算最优值。
4.使用回溯法解0/1背包问题:
n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量组成,要求用一棵完全二叉树表示其解空间(从根出发,左1右0),并画出其解空间树,计算其最优值及最优解。
5.设S={X1,X2,···,Xn}是严格递增的有序集,利用二叉树的结点来存储S中的元素,在表示S的二叉搜索树中搜索一个元素X,返回的结果有两种情形,
(1)在二叉搜索树的内结点中找到X=Xi,其概率为bi。
(2)在二叉搜索树的叶结点中确定X∈(Xi,Xi+1),其概率为ai。
在表示S的二叉搜索树T中,设存储元素Xi的结点深度为Ci;叶结点(Xi,Xi+1)的结点深度为di,则二叉搜索树T的平均路长p为多少假设二叉搜索树T[i][j]={Xi,Xi+1,···,Xj}最优值为m[i][j],W[i][j]=ai-1+bi+···+bj+aj,则m[i][j](1<=i<=j<=n)递归关系表达式为什么
6.描述0-1背包问题。
三、简答题(30分)
1.流水作业调度中,已知有n个作业,机器M1和M2上加工作业i所需的时间分别为ai和bi,请写出流水作业调度问题的johnson法则中对ai和bi的排序算法。
(函数名可写为sort(s,n))
2.最优二叉搜索树问题的动态规划算法(设函数名binarysearchtree))
答案:
一、填空
1.确定性有穷性可行性0个或多个输入一个或多个输出
2.时间复杂性空间复杂性时间复杂度高低
3.该问题具有最优子结构性质
4.{BABCD}或{CABCD}或{CADCD}
5.一个(最优)解
6.子问题子问题子问题
7.回溯法
8.o(n*2n)o(min{nc,2n})
9.最优子结构重叠子问题
10.动态规划法
二、综合题
1.①问题具有最优子结构性质;②构造最优值的递归关系表达式;③最优值的算法描述;④构造最优解;
2.①令N1={i|ai=bi};②将N1中作业按ai的非减序排序得到N1’,将N2中作业按bi的非增序排序得到N2’;③N1’中作业接N2’中作业就构成了满足Johnson法则的最优调度。
3.步骤为:
N1={1,3},N2={2,4};
N1’={1,3},N2’={4,2};
最优值为:
38
4.解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),
(1,1,0),(1,1,1)}。
解空间树为:
该问题的最优值为:
16最优解为:
(1,1,0)
5.二叉树T的平均路长P=
+
m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]}(1<=i<=j<=n,m[i][i-1]=0)
m[i][j]=0(i>j)
6.已知一个背包的容量为C,有n件物品,物品i的重量为Wi,价值为Vi,求应如何选择装入背包中的物品,使得装入背包中物品的总价值最大。
三、简答题
1.
voidsort(flowjopes[],intn)
{
inti,k,j,l;
for(i=1;i<=n-1;i++)ag!
=0)k++;
if(k>n)break;ag==0)
if(s[k].a>s[j].a)k=j;
swap(s[i].index,s[k].index);
swap(s[i].tag,s[k].tag);
}
}
l=i;
swap(s[i].index,s[k].index);ag,s[k].tag);
}
}
2.
voidbinarysearchtree(inta[],intb[],intn,int**m,int**s,int**w)
{
inti,j,k,t,l;
for(i=1;i<=n+1;i++)
{
w[i][i-1]=a[i-1];
m[i][i-1]=0;
}
for(l=0;l<=n-1;l++)
Init-single-source(G,s)
2.S=Φ
3.Q=V[G]
Q<>Φ
dou=min(Q)
S=S∪{u}
foreachvertex3
do4
四、算法理解题(本题10分)
根据优先队列式分支限界法,求下图中从v1点到v9点的单源最短路径,请画出求得最优解的解空间树。
要求中间被舍弃的结点用×标记,获得中间解的结点用单圆圈○框起,最优解用双圆圈◎框起。
五、算法理解题(本题5分)
设有n=2k个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表:
①每个选手必须与其他n-1名选手比赛各一次;
②每个选手一天至多只能赛一次;
③循环赛要在最短时间内完成。
(1)如果n=2k,循环赛最少需要进行几天;
(2)当n=23=8时,请画出循环赛日程表。
六、算法设计题(本题15分)
分别用贪心算法、动态规划法、回溯法设计0-1背包问题。
要求:
说明所使用的算法策略;写出算法实现的主要步骤;分析算法的时间。
七、算法设计题(本题10分)
通过键盘输入一个高精度的正整数n(n的有效位数≤240),去掉其中任意s个数字后,剩下的数字按原左右次序将组成一个新的正整数。
编程对给定的n和s,寻找一种方案,使得剩下的数字组成的新数最小。
【样例输入】
178543
S=4
【样例输出】
13
一、填空题(本题15分,每小题1分)
1.规则一系列运算
2.随机存取机RAM(RandomAccessMachine);随机存取存储程序机RASP(RandomAccessStoredProgramMachine);图灵机(TuringMachine)
3.算法效率
4.时间、空间、时间复杂度、空间复杂度
5.2n
6.最好局部最优选择
7.贪心选择最优子结构
二、简答题(本题25分,每小题5分)
1、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同;对这k个子问题分别求解。
如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。
2、“最优化原理”用数学化的语言来描述:
假设为了解决某一优化问题,需要依次作出n个决策D1,D2,…,Dn,如若这个决策序列是最优的,对于任何一个整数k,13、某个问题的最优解包含着其子问题的最优解。
这种性质称为最优子结构性质。
4、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索,解为叶子结点。
搜索过程中,每到达一个结点时,则判断该结点为根的子树是否含有问题的解,如果可以确定该子树中不含有问题的解,则放弃对该子树的搜索,退回到上层父结点,继续下一步深度优先搜索过程。
在回溯法中,并不是先构造出整棵状态空间树,再进行搜索,而是在搜索过程,逐步构造出状态空间树,即边搜索,边构造。
5、P(Polynomial问题):
也即是多项式复杂程度的问题。
NP就是Non-deterministicPolynomial的问题,也即是多项式复杂程度的非确定性问题。
NPC(NPComplete)问题,这种问题只有把解域里面的所有可能都穷举了之后才能得出答案,这样的问题是NP里面最难的问题,这种问题就是NPC问题。
三、算法填空(本题20分,每小题5分)
1、n后问题回溯算法
(1)!
M[j]&&!
L[i+j]&&!
R[i-j+N]
(2)M[j]=L[i+j]=R[i-j+N]=1;
(3)try(i+1,M,L,R,A)
(4)A[i][j]=0
(5)M[j]=L[i+j]=R[i-j+N]=0
2、数塔问题。
(1)c<=r
(2)t[r][c