当前位置:文档之家› 背包问题的算法设计策略对比与分析实施报告

背包问题的算法设计策略对比与分析实施报告

背包问题的算法设计策略对比与分析实施报告
背包问题的算法设计策略对比与分析实施报告

算法设计与分析大作业

0-1背包问题的算法设计策略对比与分析

0 引言

对于计算机科学来说,算法的概念是至关重要的。在一个大型软件系统的开发中,设计出有效的算法将起到决定性的作用。通俗的讲,算法是解决问题的一种方法。也因此,《算法分析与设计》成为计算科学的核心问题之一,也是计算机科学与技术专业本科及研究生的一门重要的专业基础课。算法分析与设计是计算机软件开发人员必修课,软件的效率和稳定性取决于软件中所采用的算法;对于一般程序员和计算机专业学生,学习算法设计与分析课程,可以开阔编程思路,编写出优质程序。通过老师的解析,培养我们怎样分析算法的“好”于“坏”,怎样设计算法,并以广泛用于计算机科学中的算法为例,对种类不同难度的算法设计进行系统的介绍与比较。本课程将培养学生严格的设计与分析算法的思维方式,改变随意拼凑算法的习惯。本课程要求具备离散数学、程序设计语言、数据结构等先行课课程的知识。

1 算法复杂性分析的方法介绍

算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上,所需的资源越多,该算法的复杂性越高;反之,所需资源越少,该算法的复杂性越低。对计算机资源,最重要的是时间与空间(即存储器)资源。因此,算法的复杂性有时间复杂性T(n)与空间复杂性S(n)之分。

算法复杂性是算法运行所需要的计算机资源的量,这个量应集中反映算法的效率,并从运行该算法的实际计算机中抽象出来,换句话说,这个量应该只依赖要解决的问题规模‘算法的输入和算法本身的函数。用C表示复杂性,N,I和A表示问题的规模、算法的输入和算法本身规模,则有如下表达式:

C=F(N,I,A) T=F(N,I,A) S=F(N,I,A)

其中F(N,I,A)是一个三元函数。通常A隐含在复杂性函数名当中,因此表达式中一般不写A。

即:C=F(N,I) T=F(N,I) S=F(N,I)

算法复杂性中时间与空间复杂性算法相似,所以以下算法复杂性主要以时间复杂性为例:

算法的时间复杂性一般分为三种情况:最坏情况、最好情况和平均情况。下面描述算法复杂性时都是用的简化的复杂性算法分析,引入了渐近意义的记号O,Ω,θ,和o。

O表示渐近上界Ω表示渐近下界:

θ表示同阶即:f(n)= O(g(n))且 f(n)= Ω(g(n))

2 常见的算法分析设计策略介绍

2.1 递归与分治策略

分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。

由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。

分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

递归算法举例:

Fibonacci 数列

无穷数列1,1,2,3,5,8,13,21,34,55,……,称为Fibonacci 数列。它可以递归地

定义为:

第n 个Fibonacci 数可递归地计算如下: int fibonacci (int n) {

if (n <= 1) return 1;

return fibonacci (n-1)+fibonacci (n-2); }

从上看出:

递归算法的有点为:

结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。

缺点为:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 分治算法:

一个分治法将规模为n 的问题分成k 个规模为n /m 的子问题去解。设分解阀值n0=1,且adhoc 解规模为1的问题耗费1个单位时间。再设将原问题分解为k 个子问题以及用merge 将k 个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n 的问题所需的计算时间,则有:

通过迭代法求得方程的解: 算法举例:

二分搜索技术:给定已按升序排好序的n 个元素a[0:n-1]

,现要在这n 个元素中找出一特定元素x 。

据此容易设计出二。搜索算法:

template

int BinarySearch(Type a[], const Type& x, int l, int r) {

while (r >= l){ int m = (l+r)/2;

if (x == a[m]) return m;

if (x < a[m]) r = m-1; else l = m+1; }

return -1;

}

110)2()1(11)

(>==??

?

?

?

-+-=n n n n F n F n F 1

1)()/()1()(>=??

?

+=n n n f m n kT O n T ∑-=+

=1

log 0log )

/()(n m j j

j k m m n f k

n n T

算法复杂度分析:

每执行一次算法的while 循环, 待搜索数组的大小减少一半。因此,在最坏情况下,while 循环被执行了O(logn) 次。循环体内运算需要O(1) 时间,因此整个算法在最坏情况下的计算时间复杂性为O(logn)。

快速排序法:

在快速排序中,记录的比较和交换是从两端向中间进行的,关键字较大的记录一次就能交换到后面单元,关键字较小的记录一次就能交换到前面单元,记录每次移动的距离较大,因而总的比较和移动次数较少。

void QuickSort (Type a[], int p, int r) {

if (p

int q=Partition(a,p,r);

QuickSort (a,p,q-1); //对左半段排序 QuickSort (a,q+1,r); //对右半段排序 } }

复杂性分析:

最坏时间复杂度:O(n2) 平均时间复杂度:O(nlogn) 辅助空间:O(n)或O(logn)

2.2 动态规划

动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。 方法步骤:

1)找出最优解的性质,并刻划其结构特征。

2)递归地定义最优值。

3)以自底向上的方式计算出最优值。

4)根据计算最优值时得到的信息,构造最优解。 举例:矩阵连成问题 基本要素:

1) 最优子结构 2) 重叠子问题 3) 备忘录方法

将矩阵连乘积 简记为A[i:j] ,这里i ≤j

考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak 和Ak+1之间将矩阵链断开,i ≤k

)...)(...(211j k k k i i A A A A A A +++

算法如下:

void MatrixChain(int *p,int n,int **m,int **s)

{

for (int i = 1; i <= n; i++) m[i][i] = 0;

for (int r = 2; r <= n; r++)

for (int i = 1; i <= n - r+1; i++) {

int j=i+r-1;

m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];

s[i][j] = i;

for (int k = i+1; k < j; k++) {

int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}

}

}

}

算法复杂度分析:

算法matrixChain的主要计算量取决于算法中对r,i和k的3重循环。循环体内的计算量为O(1),而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。

2.3 贪心算法

顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。

如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。

可用贪心算法解决的问题的性质:

1)贪心选择性质

2)最优子结构性质

举例:最优装载问题

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。

算法描述

最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略,可产生最优装载问题的最优解。具体算法描述如下。

template

void Loading(int x[], Type w[], Type c, int n)

{

int *t = new int [n+1];

Sort(w, t, n);

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

for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; c -= w[t[i]];} }

最优装载问题满足贪心算法的两个基本性质,可以用贪心算法实现。

2.4 回溯法

回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。

回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过

对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优

先策略搜索。

为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点,以减少问题的计算量。具有限

界函数的深度优先生成法称为回溯法。

回溯法的基本思想:

(1)针对所给问题,定义问题的解空间;

(2)确定易于搜索的解空间结构;

(3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索

举例分析:符号三角形问题:

下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”,2是“-”。

+ + -+ -+ +

+ ----+

-+ + + -

-+ + -

-+ -

--

+

解法:解向量:用n元组x[1:n]表示符号三角形的第一行。

可行性约束函数:当前符号三角形所包含的“+”个数与“-”个数均不超过n*(n+1)/4

无解的判断:n*(n+1)/2为奇数

void Triangle::Backtrack(int t)

{

if ((count>half)||(t*(t-1)/2-count>half)) return;

if (t>n) sum++;

else

for (int i=0;i<2;i++) {

p[1][t]=i;

count+=i;

for (int j=2;j<=t;j++) {

p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];

count+=p[j][t-j+1];

}

Backtrack(t+1);

for (int j=2;j<=t;j++)

count-=p[j][t-j+1];

count-=i;

}

}

复杂度分析

计算可行性约束需要O(n)时间,在最坏情况下有 O(2n)个结点需要计算可行性约束,故解符号三角形问题的回溯算法所需的计算时间为 O(n2n)。

2.5 分支限界法

分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。

在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。

此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

常见的两种分支限界法:

(1)队列式(FIFO)分支限界法

按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。

(2)优先队列式分支限界法

按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

举例:0-1背包问题

算法思想:

首先,要对输入数据进行预处理,将各物品依其单位重量价值从大到小进行排列。

在下面描述的优先队列分支限界法中,节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。

算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点,则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点,仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。

部分算法如下:

while (i != n+1) {// 非叶结点

// 检查当前扩展结点的左儿子结点

Typew wt = cw + w[i];

if (wt <= c) {// 左儿子结点为可行结点

if (cp+p[i] > bestp) bestp = cp+p[i];

AddLiveNode(up, cp+p[i], cw+w[i], true, i+1);}

up = Bound(i+1);

// 检查当前扩展结点的右儿子结点

if (up >= bestp) // 右子树可能含最优解

AddLiveNode(up, cp, cw, false, i+1);

// 取下一个扩展节点(略)

}

3 结合0-1背包问题详述动态规划、贪心算法、回溯法、分支限界法解决问题的过程

0-1背包问题 : 给定n 种物品和一背包。物品i 的重量是wi ,其价值为vi ,背包的容量为C 。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 动态规划算法: 设所给0-1背包问题的子问题

的最优值为m(i ,j),即m(i ,j)是背包容量为j ,可选择物品为i ,i+1,…,n

时0-1背包问题的最优值。由0-1背包问题的最优子结构性质,可以建立计算m(i ,j)的递归式如下。

算法复杂度分析:

从m(i ,j)的递归式容易看出,算法需要O(nc)计算时间。当背包容量c 很大时,算法需要的计算时间较多。例如,当c>2n 时,算法需要Ω(n2n)计算时间。 改进算法:

由m(i,j)的递归式容易证明,在一般情况下,对每一个确定的i(1≤i ≤n),函数m(i,j)是关于变量j 的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下,函数m(i,j)由其全部跳跃点唯一确定。对每一个确定的i(1≤i ≤n),用一个表p[i]存储函数m(i ,j)的全部跳跃点。表p[i]可依计算m(i ,j)的递归式递归地由表p[i+1]计算,初始时p[n+1]={(0,0)}。

函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi 作max 运算得到的。因此,函数m(i,j)的全部跳跃点包含于函数m(i+1,j)的跳跃点集p[i+1]与函数m(i+1,j-wi)+vi 的跳跃点集q[i+1]的并集中。易知,(s,t)∈q[i+1]当且仅当wi ≤s ≤c 且(s-wi,t-vi)∈p[i+1]。因此,容易由p[i+1]确定跳跃点集q[i+1]如下q[i+1]=p[i+1]⊕(wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))∈p[i+1]}

另一方面,设(a ,b)和(c ,d)是p[i+1]?q[i+1]中的2个跳跃点,则当c ≥a 且d

由此可见,在递归地由表p[i+1]计算表p[i]时,可先由p[i+1]计算出q[i+1],然后合并表p[i+1]和表q[i+1],并清除其中的受控跳跃点得到表p[i]。

∑=n i

k k

k x

v max ?????

≤≤∈≤∑=n

k i x j x w k n i k k k },1,0{i

i i i w j w j j i m v w j i m j i m j i m <≤≥?

?

?++-++=0),1(}

),1(),,1(max{),(n n n w

j w j v

j n m <≤≥??

?=00),(

改进后复杂性分析:

上述算法的主要计算量在于计算跳跃点集p[i](1≤i ≤n)。由于q[i+1]=p[i+1]⊕(wi ,vi),故计算q[i+1]需要O(|p[i+1]|)计算时间。合并p[i+1]和q[i+1]并清除受控跳跃点也需要O(|p[i+1]|)计算时间。从跳跃点集p[i]的定义可以看出,p[i]中的跳跃点相应于xi,…,xn 的0/1赋值。因此,p[i]中跳跃点个数不超过2n-i+1。由此可见,算法计算跳跃点集p[i]所花费的计算时间为

从而,改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1≤i ≤n)是整数时,|p[i]|≤c+1,(1≤i ≤n)。在这种情况下,改进后算法的计算时间复杂性为O(min{nc,2n})。 贪心算法:

在选择装入背包的物品时,对每种物品i 只有2种选择,即装入背包或不装入背包。不能将物品i 装入背包多次,也不能只装入部分的物品i 。贪心算法的两条性质,可以放入物品的部分,使它适合背包问题。不适合0-1背包问题,所以不能用贪心算法计算。 回溯法:

回溯法的三个条件: 解空间:子集树

可行性约束函数:

上界函数:

template Typep Knap::Bound (int i) {// 计算上界

Typew cleft = c - cw; // 剩余容量 Typep b = cp;

// 以物品单位重量价值递减序装入物品 while (i <= n && w[i] <= cleft) { cleft -= w[i]; b += p[i]; i++; }

// 装满背包

if (i <= n) b += p[i]/w[i] * cleft;

11c

x

w n i i i ≤∑=

return b;

}

分支界限法:

如上第二部分2.5所述。

4 对比分析以上四种算法策略

四种算法中都用到了最优子结构这一概念,判断用何种算法,取决于具体问题的具体分析,看是否适用本身,能达到最优算法。动态规划算法与分治算法相似。用于贪心算法的有活动安排问题,最优装载问题,哈夫曼编码问题,单源最短路径问题。对于回溯法,通过约束找到满足条件的所有解,特点为能进就进,不能进就退回来,与递归类似。分支法与回溯法类似,但解的目标是通过约束找到满足条件的一个解,或找到在某种意义下的最优解。回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

5 课程总结

通过本课程的学习,加强了我的思维能力,增强了思考问题的深度,也了解到,在编写程序时,算法对于一个程序的重要性,以前只知道程序就是代码,现在知道,代码并不是最重要的部分,好的算法可以说是一个程序成功的关键,也是功能好坏的体现,好的算法可以提高程序的效率,在一定程度上可以说是没有算法,就谈不上编写程序,通俗的说,算法在是一种解决问题的方法,是从事计算机行业人员的必备能力。

参考文献

[1] 王晓东.计算机算法设计与分析.电子工业出版社

[2] 余祥宣,崔国华,邹海明.计算机算法基础[M].武汉:华中科技大学出版社,2003.

[3] 吕国英,任瑞征,钱宇华.算法设计与分析:清华大学出版社.

[4] 《算法设计与分析》 (第二版)霍红卫编著,西安电子科技大学出版社.

单纯的课本内容,并不能满足学生的需要,通过补充,达到内容的完善

教育之通病是教用脑的人不用手,不教用手的人用脑,所以一无所能。教育革命的对策是手脑联盟,结果是手与脑的力量都可以大到不可思议。

算法设计实验_贪心算法背包问题

《算法分析与设计》 课程实验 专业年级:信息与计算科学 学生学号: 学生姓名: 实验题目:用贪婪法求解背包问题 指导老师: 实验时间:20xx年xx月x日 一、实验内容 用贪婪法求解背包问题 要求:用非递归实现 二、实验步骤 2.1、理解算法思想和问题要求; 2.2、写出每个操作的算法 非递归算法: greedbag() { int N; int c;

int[] w; int[] v; Scanner scan=new Scanner(System.in); System.out.print("输入背包的容量:"); c=scan.nextInt(); System.out.print("输入物品的数量:"); N=scan.nextInt(); System.out.print("分别输入物品的价值:"); v=new int[N]; for(int i=0;i

算法设计与分析考试题及答案

算法设计与分析考试题 及答案 Company number:【WTUT-WT88Y-W8BBGB-BWYTT-19998】

一、填空题(20分) 1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算,此外,算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分,衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD } 5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含一个(最优)解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ,先求解_子问题 ,然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质;②构造最优值的递归关系表达式; ③最优值的算法描述;④构造最优解; 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i };②将N 1中作业按a i 的非减序排序得到N 1’,将N 2中作业按b i 的非增序排序得到N 2’;③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4,在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ,且 (a 1,a 2,a 3,a 4)=(4,5,12,10),(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案,并计算最优值。 步骤为:N1={1,3},N2={2,4}; N 1’={1,3}, N 2’={4,2}; 最优值为:38 4. 使用回溯法解0/1背包问题:n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量组成,要求用一棵完全二叉树表示其解空间(从根出发,左1右0),并画出其解空间树,计算其最优值及最优解。 解空间为{(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. 设S={X 1,X 2,···,X n }是严格递增的有序集,利用二叉树的结点来存储S 中的元素,在表示S 的二叉搜索树中搜索一个元素X ,返回的结果有两种情形,(1)在二叉搜索树的内结点中找到X=X i ,其概率为b i 。(2)在二叉搜索树的叶结点中确定X ∈(X i ,X i+1),其概率为a i 。在表示S 的二叉搜索树T 中,设存储元素X i 的结点深度为C i ;叶结点(X i ,X i+1)的结点深度为d i ,则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]={X i ,X i+1,···,X j }最优值为m[i][j],W[i][j]= a i-1+b i +···+b j +a j ,则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj

中科院陈玉福计算机算法设计与分析期末简答题答案

1. 贪心算法和动态规划算法有什么共同点和区别?它们都有那些优势和劣势? 共通点:动态规划和贪心算法都是一种递推算法,均有局部最优解来推导全局最优解 区别:贪心算法中,作出的每步贪心决策都无法改变,每一步的最优解一定包含上一步的 最优解,而上一部之前的最优解则不作保留。 动态优化算法,全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质,对每一个子问题只计算一次,将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长,因此,动态规划算法通常只需要多项式时间,从而获得较高的解题效率。但它需要计算之前所有情况花费,更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解,不一定是全局最优解。 2. 试比较回溯法与分枝限界算法,分别谈谈这两个算法比较适合的问题? 二者都是在解空间树里搜索问题的可靠解或最优解,但是搜索的方式不同,回溯法采用深 度优先的方式,直到达到问题的一个可行解,或经判断沿此路径不会达到问题的可行解或最优解时,停止向前搜索,并沿原路返回到该路径上最后一个还可扩展的节点,然后,从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式,它将活节点存放在一个特殊的表中,其策略是,在扩展节点处,首先生成其所有的儿子节点,将那些导致不可行解或导致非最优解的儿子节点舍弃,其余儿子节点加入活节点表中,然后,从活节点中取出一个节点作为当前扩展节点,重复上述节点中扩展过程。可以看出,回溯法一般用于求问题的一个可行解,而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理?采用动态规划算法必须满足的条件是什么?动态规划算法是通过什 么问题的什么特性提高效率的? 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质,子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质,对每一个子问题只计算一次,将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长,因此,动态规划算法通常只需要多项式时间,从而获得较高的解题效率 4. 什么是多项式时间算法? 若存在一个常数C,使得对于所有n>=0,都有|f(n)| <= C*|g(n)|,则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法,这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法,时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法,则称该问题为多项式时间可解问题,并 将这类问题的集合记为P,因此多项式时间可解问题就称为P类问题。。

算法设计与分析实验报告贪心算法

算法设计与分析实验报告 贪心算法 班级:2013156 学号:201315614 姓名:张春阳哈夫曼编码 代码 #include float small1,small2; int flag1,flag2,count; typedefstructHuffmanTree { float weight; intlchild,rchild,parent; }huffman; huffmanhuffmantree[100]; void CreatHuffmanTree(intn,int m) { inti; void select(); printf("请输入%d个节点的权值:",n); for(i=0;i

printf("\n"); for(i=0;i

01背包问题不同算法设计、分析与对比报告

实验三01背包问题不同算法设计、分析与对比一.问题描述 给定n种物品和一背包。物品i的重量是w i ,其价值为v i ,背包的容量为c。 问题:应如何选择装入背包中的物品,使得装入背包中物品的总价值最大。 说明:在选择装入背包的物品时,对每种物品i只有两个选择,装入背包或不装入背包,也不能将物品装入背包多次。 二.实验内容与要求 实验内容: 1.分析该问题适合采用哪些算法求解(包括近似解)。 ^ 动态规划、贪心、回溯和分支限界算法。 2.分别给出不同算法求解该问题的思想与算法设计,并进行算法复杂性分析。 动态规划: 递推方程: m(i,j) = max{m(i-1,j),m(i-1,j-wi)+vi} j >= wi; m(i-1,j) j < wi; 时间复杂度为O(n). 贪心法: ^ 算法思想:贪心原则为单位价值最大且重量最小,不超过背包最大承重量为约束条件。也就是说,存在单位重量价值相等的两个包,则选取重量较小的那个背包。但是,贪心法当在只有在解决物品可以分割的背包问题时是正确的。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。 用贪心法设计算法的特点是一步一步地进行,根据某个优化测度(可能是目标函数,也可能不是目标函数),每一步上都要保证能获得局部最优解。每一步只考虑一个数据,它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中, 直到把所有数据枚举完,或者不能再添加为止。 回溯法:

回溯法:为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点,以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。 对于有n种可选物品的0/1背包问题,其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。 时间复杂度为:O(2n) 空间复杂度为:O(n) : 分支限界算法: 首先,要对输入数据进行预处理,将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中,节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点,则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点,仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。 3.设计并实现所设计的算法。 4.对比不同算法求解该问题的优劣。 这动态规划算法和贪心算法是用来分别解决不同类型的背包问题的,当一件背包物品可以分割的时候,使用贪心算法,按物品的单位体积的价值排序,从大到小取即可。当一件背包物品不可分割的时候,(因为不可分割,所以就算按物品的单位体积的价值大的先取也不一定是最优解)此时使用贪心是不对的,应使用动态规划。 5.需要提交不同算法的实现代码和总结报告。 动态规划方法: public class Knapsack {

算法设计与分析考试题及答案

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.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。

算法设计与分析试卷(2010)

算法设计与分析试卷(A 卷) 一、 选择题 ( 选择1-4个正确的答案, 每题2分,共20分) (1)计算机算法的正确描述是: B 、D A .一个算法是求特定问题的运算序列。 B .算法是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型的问题的运算序列。 C .算法是一个对任一有效输入能够停机的图灵机。 D .一个算法,它是满足5 个特性的程序,这5个特性是:有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 (2)影响程序执行时间的因素有哪些? C 、D A .算法设计的策略 B .问题的规模 C .编译程序产生的机器代码质量 D .计算机执行指令的速度 (3)用数量级形式表示的算法执行时间称为算法的 A A .时间复杂度 B .空间复杂度 C .处理器复杂度 D .通信复杂度 (4)时间复杂性为多项式界的算法有: A .快速排序算法 B .n-后问题 C .计算π值 D .prim 算法 (5)对于并行算法与串行算法的关系,正确的理解是: A .高效的串行算法不一定是能导出高效的并行算法 B .高效的串行算法不一定隐含并行性 C .串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 (6)衡量近似算法性能的重要标准有: A A .算法复杂度 B .问题复杂度 C .解的最优近似度 D .算法的策略 (7)分治法的适用条件是,所解决的问题一般具有这些特征: ABCD A .该问题的规模缩小到一定的程度就可以容易地解决; B .该问题可以分解为若干个规模较小的相同问题; C .利用该问题分解出的子问题的解可以合并为该问题的解 D .该问题所分解出的各个子问题是相互独立的。 (8)具有最优子结构的算法有: A .概率算法 B .回溯法 C .分支限界法 D .动态规划法 (9)下列哪些问题是典型的NP 完全问题: A .排序问题 B .n-后问题 C .m-着色问题 D .旅行商问题 (10)适于递归实现的算法有: C A .并行算法 B .近似算法 C .分治法 D .回溯法 二、算法分析题(每小题5分,共10分) (11)用展开法求解递推关系: (12)分析当输入数据已经有序时快速排序算法的不足,提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

算法设计与分析课程设计报告样本

课程设计报告 课程设计名称: 算法设计与分析 系 : 三系 学生姓名: 吴阳 班级: 12软件(2)班 学号: 0311232 成绩: 指导教师: 秦川 开课时间: 年一学期 一、问题描述 1.普通背包问题

给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 能够选择物品i的一部分, 而不一定要全部装入背包, 1≤i≤n。 2.0/1背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 对于每种物品i只有两种选择, 即装入背包或者不装入背包, 不能将物品装入背包多次, 也不能只装入部分的物品i。 3.棋盘覆盖问题 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其它的不同称为特殊方格, 想要求利用四种L型骨牌( 每个骨牌可覆盖三个方格) 不相互重叠覆盖的将除了特殊方格外的其它方格覆盖。 二、问题分析

1.普通背包问题 对于背包问题, 若它的一个最优解包含物品j, 则从该最优解中拿出所含的物品j的那部分重量W, 剩余的将是n-1个原重物品1, 2, ······, j-1, j+1, ·····, n以及重为Wi-W的物品j 中可装入容量为C-W的背包且具有最大价值的物品。 2.0/1背包问题 如果当前背包中的物品的总容量是cw, 前面的k-1件物品都已经决定好是否要放入包中, 那么第k件物品是否放入包中取决于不等式 cw + wk <= M (其中, wk为第k件物品的容量, M为背包的容量)( 此即约束条件) 然后我们再寻找限界函数, 这个问题比较麻烦, 我们能够回忆一下背包问题的贪心算法, 即物品按照物品的价值/物品的体积来从大到小排列, 然后最优解为( 1, 1, 1......., 1, t, 0, 0, ......) , 其中0<=t<=1; 因此, 我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下), 我们能够考虑我们能够达到的最大的价值, 即我们能够经过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。经过该条件, 能够减去很多的枝条, 大大节省运行时间。 3.棋盘覆盖问题 每次都对分割后的四个小方块进行判断, 判断特殊方格是否

算法设计背包问题

算法实验报告 ---背包问题 实验目的 1.掌握动态规划算法的基本思想,包括最优子结构性质和基于表格的最优 值计算方法。 2.熟练掌握分阶段的和递推的最优子结构分析方法。 3.学会利用动态规划算法解决实际问题。 问题描述: 给定n种物品和一个背包。物品i的重量是wi,体积是bi,其价值为vi, 背包的容量为c,容积为d。问应如何选择装入背包中的物品,使得装入背包中 物品的总价值最大? 在选择装入背包的物品时,对每种物品只有两个选择:装入 或不装入,且不能重复装入。输入数据的第一行分别为:背包的容量c,背包的 容积d,物品的个数n。接下来的n行表示n个物品的重量、体积和价值。输出 为最大的总价值。 问题分析: 标准0-1背包问题,MaxV表示前i个物品装入容量为j的背包中时所能产生的最大价值,结构体objec表示每一个可装入物品,其中w表示物品的重量,v表示物品的价值。如果某物品超过了背包的容量,则该物品一定不能放入背包,问题就变成了剩余i-1个物品装入容量为j的背包中所能产生的最大价值;如果该物品能装入背包,问题就变成i-1个物品装入容量为j-objec[i].w的背包所能产生的最大价值加上物品i的价值objec[i].v. 复杂性分析 时间复杂度,最好情况下为0,最坏情况下为:(abc) 源程序 #include #include #include #include #include int V [200][200][200]; int max(int a,int b) {

算法设计与分析试卷(2010)

内部资料,转载请注明出处,谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 ( 选择1-4个正确的答案, 每题2分,共20分) (1)计算机算法的正确描述是: A .一个算法是求特定问题的运算序列。 B .算法是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型的问题的运算序列。 C .算法是一个对任一有效输入能够停机的图灵机。 D .一个算法,它是满足5 个特性的程序,这5个特性是:有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 (2)影响程序执行时间的因素有哪些? A .算法设计的策略 B .问题的规模 C .编译程序产生的机器代码质量 D .计算机执行指令的速度 (3)用数量级形式表示的算法执行时间称为算法的 A .时间复杂度 B .空间复杂度 C .处理器复杂度 D .通信复杂度 (4)时间复杂性为多项式界的算法有: A .快速排序算法 B .n-后问题 C .计算π值 D .prim 算法 (5)对于并行算法与串行算法的关系,正确的理解是: A .高效的串行算法不一定是能导出高效的并行算法 B .高效的串行算法不一定隐含并行性 C .串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 (6)衡量近似算法性能的重要标准有: A .算法复杂度 B .问题复杂度 C .解的最优近似度 D .算法的策略 (7)分治法的适用条件是,所解决的问题一般具有这些特征: A .该问题的规模缩小到一定的程度就可以容易地解决; B .该问题可以分解为若干个规模较小的相同问题; C .利用该问题分解出的子问题的解可以合并为该问题的解 D .该问题所分解出的各个子问题是相互独立的。 (8)具有最优子结构的算法有: A .概率算法 B .回溯法 C .分支限界法 D .动态规划法 (9)下列哪些问题是典型的NP 完全问题: A .排序问题 B .n-后问题 C .m-着色问题 D .旅行商问题 (10)适于递归实现的算法有: A .并行算法 B .近似算法 C .分治法 D .回溯法 二、算法分析题(每小题5分,共10分) (11)用展开法求解递推关系: (12)分析当输入数据已经有序时快速排序算法的不足,提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

计算机算法设计与分析期末考试复习题

1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是( B )。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是( A )。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6.下列算法中通常以自底向上的方式求解最优解的是( B )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是(C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是(D )。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是( A )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是( B )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11.下面不是分支界限法搜索方式的是( D )。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12.下列算法中通常以深度优先方式系统搜索问题解的是( D )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的( B )。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14.广度优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15.背包问题的贪心算法所需的计算时间为( B )。

0-1背包问题_算法设计C++

南京信息工程大学实验(实习) 报告 实验(实习)名称 0—1背包实验(实习)日期得分指导教师 专业软件工程年级 11 班次姓名学号 一:实验目的 通过运用回溯法的深度优先搜索解决0-1背包问题,掌握运用回溯法解题。二:算法思想 回溯法的基本思想是按深度优先策略,从根节点出发搜索解空间树,算法搜索至解空间的任一点时,先判断该结点是否包含问题的解,如果肯定不包含,则跳过以该结点为根的子树的搜索,逐层向其祖先结点回溯,否则,进入该子树,继续按深度优先进行搜索。 三:算法实现 #include template class Knap{ friend Typep Knapsack(Typep*,Typew*,Typew,int); private:Typep Bound(int i); void Backtrack(int i); Typew c; int n; Typew *w; Typep *p; Typew cw; Typep cp; Typep bestp; }; template Typep Knap

return b; } template void Knap::Backtrack(int i) { if(i>n){ bestp=cp; return;} if(cw+w[i]<=c){cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i];} if(Bound(i+1)>bestp) Backtrack(i+1); } class Object{ friend int Knapsack(int *,int *,int,int,); public: int operator<=(Object a)const {return(d>=a.d);} private: int ID; float d; }; template{ Typep W=0; Typep P=0; Object*Q=new Object[n]; for(int i=1;i<=n;i++){ Q[i-1].ID=i; Q[i-1].d=1.0*p[i]/w[i]; P+=p[i]; W+=w[i]; } if(W<=c)return P; sort(Q,n); KnapK; K.p=new Typep[n+1]; K.w=new Typew[n+1]; for(int i=1;i<=n;i++){ K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; } K.cp=0; K.cw=0; K.c=c; K.n=n;

算法设计与分析试卷及答案

湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:120分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分,共计30 分) 1、用O、Ω与θ表示函数f与g之间得关系______________________________。 2、算法得时间复杂性为,则算法得时间复杂性得阶为__________________________。 3、快速排序算法得性能取决于______________________________。 4、算法就是_______________________________________________________。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是_________________________。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是_____情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越___________,结果就越有价值。。 8、____________________________就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指____________________________________________________________________________________________________________________。 10、回溯法在问题得解空间树中,按______________策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计30分) 1、试述回溯法得基本思想及用回溯法解题得步骤。 2、有8个作业{1,2,…,8}要在由2台机器M1与M2组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M1与M2加工作业i所需得时间分别为: M110 2 8 12 6 9414

算法设计与分析课程设计报告

压缩软件课程设计书 一、问题描述: 建立一个文本文件,统计该文件中各字符频率,对各字符进行Huffman编码,将该文件至翻译成Huffman编码文件,再将Huffman编码文件翻译成原文件。 二、算法分析及思路: 对于该问题,我们做如下分析: (1)首先得构造出哈弗曼树,我们用函数HuffmanTree(int w[],int s[],int n)设计;(2)在构建哈弗曼树的基础上,进一步实现哈弗曼编码问题,我们用函数Huffmancode(char wen[])设计; (3)实现哈弗曼编码后再进一步实现哈弗曼译码问题,我们用函数Huffmandecode()设计; (4)其中编码问题中,得进一步统计出各个字符在文件中的频率,并进行一些必要的标记,我们用函数runhuffman(char wen[])设计; (5)在译码过程中,还有必要的一步是比较原文件与译码后的文件是否相同,我们用函数compare(char wen[])设计; (6)其中的文件输入我们用到类”fstream.h”中的输入输出流,并在运行的文件夹中建立一个文件名为逍遥游的文本文件,且在逍遥游文件中输入需要编码的数据。 三、主要解决的设计问题: 1.写一个对txt文件压缩和解压的程序,使用动态编码。 2.使用Huffman编码压缩和解压时,Huffman树的存储可以直接存储树结构,也可以存储所有字符的频度或权值,然后读取时建立Huffman树; 3.使用Huffman编码压缩和解压时,注意定义压缩码的结束标记,可以使用一个特殊的字符作为结束标记,也可以在压缩码之前存储其比特长度;如果使用一个特殊字符作为结束标记,则其频度为1,需要在建立Huffman树时把它看作一个独立的字符进行建树。 4.使用Huffman编码压缩和解压时,在一个缓冲区里面收集压缩码比特流,每当收集的比特数满8时,可以把这8比特通过位操作合并成一个字节写入文件(当然也可以收集满一定数目的字节后再写入文件)。写入文件的最小信息单位为字节。 四、程序设计的流程图:

算法设计与分析期末试题答案解析

1、用计算机求解问题的步骤: 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义:算法是指在解决问题时,按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性: 有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。 确定性:算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性:一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入:一个算法有零个或多个输入,这些输入取自于某个特定对象的集合。 输出:一个算法有一个或多个输出,这些输出同输入有着某些特定关系的量。 算法设计的质量指标: 正确性:算法应满足具体问题的需求; 可读性:算法应该好读,以有利于读者对程序的理解;

健壮性:算法应具有容错处理,当输入为非法数据时,算法应对其作出反应,而不是产生莫名其妙的输出结果。 效率与存储量需求:效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想:迭代法也称“辗转法”,是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤:1、确定迭代模型。根据问题描述,分析得出前一个(或几个)值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式,存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程,这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一

算法设计与分析课程报告

算法设计与分析课程报告 第一章 算法问题求解基础 1、算法的概念:算法是指解决问题的一种方法或过程,是由若干条指令组成的有穷序列。 2、算法的特性 ① 有穷性:一个算法必须保证执行有限步之后结束; ② 确切性:算法的每一步骤必须有确切的定义; ③ 输入: 一个算法有 0 个或多个输入, 法 本身定除了初始条件; ④ 输出: 一个算法有一个或多个输出, 是毫无意义的; ⑤可行性:算法原则上能够精确地运行, 而且人们用笔和纸做有限次运算后即可完成 3、算法与程序的关系: 区别:程序可以不一定满足可终止性。但算法必须在有限时间内结束; 程序可以没有输出 ,而算法则必须有输出; 算法是面向问题求解的过程描述,程序则是算法的实现。 联系:程序是算法用某种程序设计语言的具体实现; 程序可以不满足算法的有限性性质。 4、算法描述方式:自然语言,流程图,伪代码,高级语言。 第二章 算法分析基础 1、算法复杂性分析: 算法复杂性的高低体现运行该算法所需计算机资源(时间,空间)的多少。 算法复杂性度量: 期望反映算法本身性能,与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准(硬件性能、代码质量影响) 般是针对问题选择基本运算和基本存储单位,用算法针对基本运算与基本存储单 以刻画运算对象的初始情况, 所谓 0 个输入是指算 以反映对输入数据加工后的结果。 没有输出的算法

位的开销作为标准。算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I,A)。 第五章分治法 1、递归算法:直接或间接地调用自身的算法。 用函数自身给出定义的函数称为递归函数。 注:边界条件与递归方程是递归函数的二个要素。 实例:①阶乘函数; ② Fibonacci 数列;③ Ackerman 函数; ④排列问题; ⑤整数划分问题; ⑥ Hanoi 塔问题 优缺点:①优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便。 ②缺点:递归算法的运行效率低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 2、分治法的设计思想:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。(将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解) 分治法所能解决的问题一般具有以下几个特征: ①该问题的规模缩小到一定的程度就可以容易地解决; ②该问题可以分为若干个规模更小的相同问题,即该问题具有最有子结构性质; ③利用该问题分解出的子问题的解可以合并为该问题的解; ④该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。 第六章贪心法 1、贪心算法的思想:

算法设计与分析试卷及答案.doc

湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型:开卷 试卷类型: C 卷 考试时量: 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题(每小题 3 分,共计 30 分) 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ,则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中, 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限,这个下限的阶越 ___________,结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。

算法设计与分析实验报告

本科实验报告 课程名称:算法设计与分析 实验项目:递归与分治算法 实验地点:计算机系实验楼110 专业班级:物联网1601 学号:2016002105 学生姓名:俞梦真 指导教师:郝晓丽 2018年05月04 日

实验一递归与分治算法 1.1 实验目的与要求 1.进一步熟悉C/C++语言的集成开发环境; 2.通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治(Divide-and-Conquer)的思想:一个规模为n的复杂问题的求解,可以划分成若干个规模小于n的子问题,再将子问题的解合并成原问题的解。 需要注意的是,分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同,可用相同的求解方法。最后,当子问题规模足够小时,可以直接求解,然后逆求原问题的解。 1.4 实验题目 1.上机题目:格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素,每个元素都是长度为n的串,相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码(分治、减治、变治皆可)。 对于给定的正整数n,格雷码为满足如下条件的一个编码序列。 (1)序列由2n个编码组成,每个编码都是长度为n的二进制位串。 (2)序列中无相同的编码。 (3)序列中位置相邻的两个编码恰有一位不同。 2.设计思想: 根据格雷码的性质,找到他的规律,可发现,1位是0 1。两位是00 01 11 10。三位是000 001 011

010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0,N-2为倒转再前面再加1。 3.代码设计:

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

计算机算法设计与分析习 题及答案 Prepared on 24 November 2020

《计算机算法设计与分析》习题及答案 一.选择题 1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是(A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是( A )。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5.下列算法中通常以自底向上的方式求解最优解的是(B )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是( C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是( D )。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是(A )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9.下面不是分支界限法搜索方式的是(D )。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先

10.下列算法中通常以深度优先方式系统搜索问题解的是(D )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。( B ) A、分治法 B、动态规划法 C、贪心法 D、回溯法 12.哈夫曼编码的贪心算法所需的计算时间为(B )。 A、O(n2n) B、O(nlogn) C、O(2n) D、O(n) 13.分支限界法解最大团问题时,活结点表的组织形式是(B )。 A、最小堆 B、最大堆 C、栈 D、数组 14.最长公共子序列算法利用的算法是(B)。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15.实现棋盘覆盖算法利用的算法是(A )。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是(C )。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素( D ) A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略(B ) A.递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. (D)是贪心算法与动态规划算法的共同点。

相关主题
文本预览
相关文档 最新文档