Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4779319
  • 博文数量: 921
  • 博客积分: 19333
  • 博客等级: 上将
  • 技术积分: 11216
  • 用 户 组: 普通用户
  • 注册时间: 2007-03-27 14:33
文章分类

全部博文(921)

文章存档

2020年(2)

2019年(1)

2017年(1)

2016年(3)

2015年(10)

2014年(17)

2013年(49)

2012年(291)

2011年(266)

2010年(95)

2009年(54)

2008年(132)

分类:

2008-09-18 11:05:28

《算法分析与设计》

1.考虑 而不是xi∈{0,1}的连续背包问题。一种可行的贪婪策略是:按价值密度非递减的顺序检查物品,若剩余容量能容下正在考察的物品,将其装入;否则,往背包内装如此物品的一部分。
(a) 对于n=3,w=[100,10,10],p=[20,15,15],以及c=105,上述装入法获得结果是什么?
(b)证明这种贪婪算法总能获得最优解。
(c) 用伪代码描述此算法。

2.1)证明当且仅当二分图没有覆盖时,下述算法找不到覆盖。
m=0; //当前覆盖的大小
对于A中的所有i,New[i]=Degree[i]
对于B中的所有i,Cov[i]=false
while(对于A中的某些i,New[i]>0) {
设v是具有最大的New[i]的顶点;C[m++]=v;
for(所有邻接于v的顶点j) {
         If(!Cov[j]) {
Cov[j] = true;
          对于所有邻接于j的顶点,使其New[k]减1
}}}
if (有些顶点未被覆盖) 失败
else 找到一个覆盖2)给出一个具有覆盖的二分图,使得上述算法找不到最小覆盖。

3.对于二分图覆盖问题设计另一种贪婪启发算法,贪婪准则是:如果B中某一个顶
点被A中一个顶点覆盖,选择A中这个顶点;否则,从A中选择一个顶点,使得它所
覆盖的未被覆盖的顶点数目最多。给出这种贪婪算法的伪代码。

4.有n个硬币,其中1个是假币,且假币较轻。请用分而治之方法设计一个找出假币的算法。
用伪代码描述你的算法;
用C程序描述你的算法;
分析你的算法的时间复杂性。

5.如果上题中的条件“假币较轻”改为“假币和真币”的重量不同。请用分而治之方法设计一个找出假币的算法,用C程序实现你的算法。
用分而治之算法计算3456*5678;
2)假设两个大整数都是n=2k位,请用伪代码描述两个大整数乘积的分而治之算法。

7.设计一个分而治之算法来计算二叉树中分支结点的个数。请用伪代码描述你的算法。请分析算法的时间复杂度。

8.货物装箱问题:设有一艘货船装货箱。共有n=6件货箱,它们的重量如下表示:[w1,..., w6] = [100, 200, 50, 90, 50, 20],船的限载重量是c=300。试用贪婪算法装船,要求货箱装得最多。贪婪准则:从剩下的货箱中选择重量最小的货箱。
请给出问题的解;
对一般的n,重量为w=[w1,..., wn],船的限载重量是c>0,要求船的货箱装得最多,请用伪代码描述你的算法;
考虑有两条船的情况,即有两条船,船的限载重量是分别是c1和c2;共n件货箱,重量为w=[w1,..., wn],试用贪婪算法装船,要求两条船的货箱装得最多。请描述你的算法,该算法总能产生最优解吗?请说明你的理由。

9.  1)在8(1)的条件下,10. 如果货箱具有价值,11. [p1,..., p6] = [20, 50, 25, 15, 20, 10]。试设计一个装船的贪婪算法,12. 要求装船的货箱的价值最大。
2)对一般的n,价值p=[p1,..., pn],重量为w=[w1,..., wn],船的限载重量是c>0,请用伪代码描述你设计的贪婪装船算法,要求装船的货箱的价值最大。
二、习题(15、16、17章)
定义0/1/2背包问题为: 。限制条件为: ,且 ,f(i , y)表示剩余容量为y,剩余物品为:i,i+1,…,n时的最优解的值。
1) 推出f(i , y)的递推表达式(类似于15-1和5-2式);
2) 请设计求解f(i , y)的算法,3) 并用伪代码描述你的算法;
4) 分析你的算法的复5) 杂性。
6) 设W=[10,20,15,30,10],7) P=[6,10,15,18,5],c=78,8) 请用你的算法求解。

设G为有n个顶点的有向无环图,G中各顶点的编号为1到n,且当为G中的一条边时有i < j。设w(i,j)为边的长度,请设计动态规划算法,计算图G中最长路径。并分析算法的时间复杂性。1)、对5个矩阵连乘积 运用动态规划方法确定计算的次序,使得乘法计算量最小。其中矩阵的维数分别为10*100, 100*5, 5*50,50*20,20*60;
2)对n个矩阵连乘积,用伪代码描述你的算法。

对0/1背包问题:n=4,w=[20,25,15,35],p=[40,49,25,60],c=62。
1)、画出0/1背包问题的解空间树;
2)、对该树运用回溯算法,写出依回溯算法遍历节点的顺序表及节点。确定回溯算法未遍历的节点。

5.旅行商问题:给出一个n个顶点网络(有向或无向),要求找出一个包含所有n个顶点的具有最小耗费的环路。任何一个包含所有n个顶点的环路被称作一个旅行。在旅行商问题中,要设法找到一条最小耗费的旅行。
1)对图示的例,画出旅行商问题的解空间树;
2)对该树运用回溯算法,写出依回溯算法遍历节点的顺序表及节点。确定回溯算法未遍历的节点。

子集和问题:对于集合S={1,2,5,6,8},求子集,要求该子集的元素之和d=9。
a) 画出子集和问题的解空间树;
b) 对该树运用回溯算法,c) 写出依回溯算法遍历节点的顺序表及节点。确定回溯算法未遍历的节点;
d) 如果S中有n个元素,e) 指f) 定d,g) 用伪代码写出求解子集和问题的回溯算法。

7.对0/1背包问题:n=4,w=[20,25,15,35],p=[40,49,25,60],c=62。
1)、画出0/1背包问题的解空间树;
2)、描述用FIFO分枝定界法解决上述问题的过程;
3)、描述用最大收益分枝定界法解决上述问题的过程。
4)、对一般的n,用伪代码描述0/1背包问题的最大收益分枝定界法。

8.对子集和问题:对于集合S={1,2,5,6,8},求子集,要求该子集的元素之和d=9。
1)、画出子集和问题的解空间树;
2)、描述用FIFO分枝定界法解决上述问题的过程;
3)、如果S中有n个元素,指定d,用伪代码描述求解子集和问题的FIFO分枝定界法。

9.  旅行商问题:给出一个n个顶点网络(有向或无向),要求找出一个包含所有n个顶点的具有最小耗费的环路。任何一个包含所有n个顶点的环路被称作一个旅行。在旅行商问题中,要设法找到一条最小耗费的旅行。
1)对图示的例,画出旅行商问题的解空间树。
2)描述用FIFO分枝定界法解决上述问题的过程;
3)对有n个顶点的网络,用伪代码描述求解旅行商问题的FIFO分枝定界法。

阅读(3131) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~