算法设计与分析期末试题考试版.docx

算法设计与分析期末试题考试版.docx

《算法设计与分析期末试题考试版.docx》由会员分享，可在线阅读，更多相关《算法设计与分析期末试题考试版.docx（25页珍藏版）》请在冰点文库上搜索。

算法设计与分析期末试题考试版

1、用计算机求解问题的步骤：

1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制2、算法定义：

算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程3、算法的三要素1、操作2、控制结构3、数据结构

算法具有以下5个属性：

有穷性：

确定性：

可行性：

输入：

输出：

算法设计的质量指标：

正确性：

算法应满足具体问题的需求；

可读性：

算法应该好读，以有利于读者对程序的理解；

健壮性：

算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。

效率与存储量需求：

效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。

一般这两者与问题的规模有关。

和Y的一个最长公共子序列及X和Y的一个最长公共子序列。

这两个公共子序列中较长者即为X和n-1Y的一个最长公共子序列。

由此递归结构容功看到最长公共子序列问题具有于问题重叠性质。

例如，在计算X和Y的最长公共子序列时，可能要计算出X和Y及X和Y的最长公共子序列。

而这两个子问题都包含一个公共子问n-1«r1题，即计算X和Y的最长公共子序列。

n~1与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递但关系。

用c[i,j]记录序列X和Y的最长公共子序列的长度。

其中X=,Y=。

当i=0或j=0时，iji12ij12j

空序列是X和Y的最长公共子序列，故c[i,j]=O。

其他靖况下，由定理可建立递归关系如下：

*j0ifJ=0orJ=0,cp',j]=.（|/-I./-l|+Iif/,J>0and习=为，max（c（/.J-I）,c\i-L刀）ifi,j>0and丰”.

2.3、计算最优值直接利用上节节末的递归或，我们将很容易就能写出一个计算c[i,j]的递归算法，但其计鼻时间是随输入长度指数增长的。

由于在所考虑的子问题空间中，总共只有9（m*n）个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。

计鼻最长公共子序列长度的动态规划算法LCS_LENGTH（X,Y）以序列X=〈x,x,…，x>^Y=作为输入。

输出两个数组c[0..m,0..n]和b[1..m,1..n]o其中c[i,j]存储X与Y的最长公共。

ij

子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。

最后，X和Y的最长公共子序列的长度记录于c[m,n]中。

由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=和Y=12n12n的最长公共子序列。

首先从b[m,n]开始，沿肴其中的箭头所指的方向在数组b中搜索。

•当b[i,j]中遇到"Y"时（意味着xi=yi^LCS的一个元素）,表示X与Y的最长公共子序»j

列是由X与Y的最长公共子序列在尾部加上x得到的子序列；i-1j-1i

•当b[i,j]中遇到时，表示X与Y的最长公共子序列和X与Y的快长公共子序列相同：

iji-1j

•当b[i,j]中遇到时，表示X与Y的最长公共子序列和X与Y的最长公共子序列相同。

'>Ijt这种方法是按照反序来找LCS的每一个元素的。

由于每个数组单元的计算耗费0

（1）时间，算法LCS.LENGTH耗时0（mn）。

A

）0123456DBB

0

Q

Q

0

Q

0

（）

ft

TQ

T

0

tQ

\

1

—1

\

1

0

\

1

I

\

2

—2

A

0

T

1

r

1

X

2

—2

?

2

T

2

0

\

1

ti

t

2

T

2

\

3

—3

0

了

1

\

2

2

t

3

T

0

T

1

T

2

r

2

\

3

T

3

\

4

（1

\

1

?

3

\

4.

t

4

A人RC

BA流水线调度

1,在M1上加工时间短的任务优先，而在M2上加工时间短的任务

排在最后如果最小的时间是Tk1则将•任务k排在第一位，如果最小的任

务Tk2则排在最后一个。

最优二叉搜索树

对于有n个关键码的集合，其关键码有n!

种不同的排列，可构成的不同二c"又搜索树有”+1业棵。

（n个结点的不同二又树，卡塔兰数）。

如何评价这些二叉搜索树，可以用树的搜索效率来衡量。

例如：

标识符集{1,2,3}={do,if,stop}可能.的二分检索树为：

若P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05,求每棵树的平均比较次数（成本）。

p=1Xp1+2Xp2+3Xp3+1XqO+2Xq1+3X（q2+q3=）1a（n）X0.5+2X0.1+3X0.05+1XO.05+2X0.1+3X（0.05+0.05）=1.5P=1Xp1+2Xp3+3Xp2+1XqO+2Xq3+3X（q1+q2）=1b（n）X0.5+2X0.05+3XO.1+1XO.15+2X0.05+3X（0.1+0.05）=1.6

P=1Xp2+2X（p1+p3）+2X（qO+q1+q2+q3）=1Xc（n）0.1+2X（0.5+0.05）+2X（0.15+0.1+0.05+0.05）=1.9PXp3+2Xp1+3Xp2+1Xq3+2XqO+3X（q1+q2）=1d（n）X0.05+2X0.5+3X0.1+1XO.05+2X0.15+3X（0.1+

0.05）=2.15

P,、=1Xp3+2Xp2+3Xp1+1Xq3+2Xq2+3X（qO+e（n）q1）=1X0.05+2X0.1+3X0.5+1X0.05+2X0.153+X（0.15+0.1）=2.85

因此，上例中的最小平均路长为P,=1.5oa（n）可以得出结论：

结点在二叉搜索树中的层次越深，需要比较的次数就越多，因此要构造一棵最小二叉树，一般尽量把搜索概率较高的结点放在较高的层砍

p=®

*深度+

*路径长。

最优二叉搜索树:

在一个表示S的二叉树T中，设存储元素Xj的结点深度为c叶结点（x「Xj2的结点深度为d5nnP=£40+Cj）+时）•

f=ly=0

注：

在检索过程中，每进行一次比较，就进入下面一层，对于成功的检索，比较的次数就是所在的层数加1。

对于不成功的检索，被检索的关键码属于那个外部结点代表的可能关键码集合，比较次数就等于此外部结点的层数。

对于图的内结点而言，儡层需要比较操作次数为1,第1层需要比枝2次，第2层需要3次。

自顶向下分析卜].

键值：

U.,，外_1,“k，"称,1，…，°j

k-1=i：

左子树缩为单节点。

k+1=j：

右子树缩为单节点。

k

左子树为空树。

k>h右子树为空树•

左询（^5®找）右网（翩欲）

JA-lJ

概率:

Pi,Pk_l,Pk，Pk+l，…，Pj二恩噪外+2>，+£p『+2>四外）+SpH（%）｝

全部节占

7

全部节占

左子树平均CH右子树平均gl”]

I~ir=*+lZ-iH

递推II算式J

中,刀=恩想｛q，,a-1]+q#+1,』｝+£r1

C[iJ]^P[i];〃C次对角元

C[iJ]^P[i];〃C次对角元

1J1.7

0.81、4

OptinialBST（.4[1.../?

],P[1...h],C[l...//+1,0.../?

],2?

[1.../74-1,0...n]）

+〃C对角元最后一个元素汽for（d<—lsn-l）do//jjn入节点序歹U"■KBH

for（i<-lton-d）do〃范围」〜〃-14

J—i+d;〃范围：

2〜胛5|||||。

minval<—qc;，当前根k的最小平均比较次数

for（k<—/toj）do//找最优根if（C\i9k-l]^C\k+lJ]

基本操作立方型效率

minval。

％,菖]+平+j;即』可以限定在R[iJ]^kmitK〃记录最优根，此句教材上错为』R[i,j・i]和R[i+ij]5Z/；H<-P[/]；之间，效率降至

for（y<—/+1toj）dosum<—sum+P[s];平方型-

C[i9j]=mitnal+sum;return（C[l,n],&）；

回溯法简单概述回溯法思路的简单描述是：

把问题的解空间转化成了图或者树的

结构表示，然后使用深度优先授索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

基本思想类同于：

-图的深度优先授索・二叉树的后序遍历【分支限界法：

广度优先搜索思想类同于：

图的广度优先遍历

二又树的层序遍历】

一些概念问题的解向量：

回溯法希望一个问题的解能够表示成一个n元式（x1,x2,…，xn）的形式。

1显约束：

对分量xi的取值限定。

8隐约束：

为满足问题的解而对不同分量之间施加的约束。

4解空间：

对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个耕空间。

5扩展结点：

一个正在产生儿子的结点称为扩展结点活结点：

一个自身已生成但其儿子还没有全部生成的节点称做活结点?

死结点：

一个所有儿子已经产生的结点称做死结点深度优先的问题状态生成法：

如果对一个扩展结点R,一旦产生了它的一个儿子C,就把C当做新的扩展结点。

在完成对子树C（以C为根的子树）的穷尽授索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）

8宽度优先的问题状态生成法：

在一个扩展结点变成死结点之前，它一直是扩展结点0回溯法：

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

具有限界函数的深度优先生成法祢为回溯法基本思想：

按照深度优先策略，从根结点出发搜索解空间。

算法搜索至解空间的任一结点时总是先判断该结点是否问题的约束条件。

如果满足进入该子树，继续按深度优先的策略搜索。

否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。

其实回溯法就是对隐式图的深度优先搜索算法

回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。

剪枝函数包括两类：

1.使用约束函数，剪去不满足约束条件的路径；使用限界函数，剪去不能得到最优解的路径。

问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。

解空间树分为两种：

子集树和排列树。

两种在算法结构和思路上大体相同。

1.子集树

所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间成为子集树。

如0-1背包问题，从所给重量、价值不同的物品中挑选几个物品放入背包，使得在满足背包不超重的情况下，背包内物品价值最大。

它的解空间就是一个典型的子集树。

回溯法搜索子集树的算法范式如下：

viewplaincopy

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

voidbacktrack（intt）{

if（t>n）output（x）;

elsefor（inti=0;i〈=1;i++）{x[t]=i;if（constraint（t）&&bound（t））backtrack（t+1）;

2.排列树所给的问题是确定n个元素满足某种性质的排列时，相应的解空间就是排列树。

如旅行售货员问题，一个售货员把几个城市旅行一遍，要求走的路程最小。

它的解就是几个城市的排列，解空间就是排列树。

回溯法搜索排列树的算法范式如下：

vi«wpleincopy

1.

18px；">voidbacktrack

（intt）

2.

{

3.

if（t>n）output（x）;

4.

else

5.

for（inti=t;i<=n;i++）{

6.

swap（x[t],x[i]）;

7.

if（constraint（t）&&bound（t））

backtrack（t+1）;

8.

swap（x[t],x[i]）;

9.

I

基本步骤：

1、确定问题的解空间：

应用回溯法时，首先应明确定义问题的解的空间。

问题的解空间应至少包含问题的一个解。

2、确定结点的扩展规则3、搜索解空间：

从开始结点出发，以深度优先的方式搜索整个解空间。

分支限界法一、分支限界法与回溯法的区别与联系（D求解目标：

回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

（2）搜索方式的不同：

回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

算法设计与分析期末试题—考试版

二、分支限界法的基本思想

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

在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所需的解或活结点表为空时为止

⑴描述：

采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。

所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支

（即：

儿子结点）。

所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率。

（2）原理：

按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。

然后，从活结点表中取出一个结点作为当前扩展结点。

重复上述结点扩展过程，直至我到问题的解或判定无解为止。

（3）分支限界法与回溯法

1）求解目标：

回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足劫束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

复杂性的渐近性态设T（N）是算法A的复杂性函数，使得当NT8时有：

（T（N）-T'（N））/T（N）T0那么，我们就说T'（N）是T（N）当NT8时的渐近性态，或叫T'（N）为算法A当NT8的渐近复杂性而与T（N）相区别。

4K/IJUJIUJ，殉心心JtAX歼Jo

近似算法的基本思想是用近似最优解代替最优解，以换取算法设计上的简化和时间复杂性的降低。

近似算法是这样一个过程：

虽然它可能找不到一个最优解，但它总会为待求解的问题提供-个解。

为了具有实用性，近似算法必须能够给出算法所产生的解与最优解之间的差别或者比例的一个界限，它保证任意一个实例的近似最优解与最优解之间相差的程度。

显然，这个差别越小，近似算法越具有实用性。

P=NP经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法分而治之法

1、基本思想将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治法所能解决的问题一般具有以下几个特征：

2）搜索方式的不同：

回溯法以深度优先的方式授索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

⑷常见的分支限界法

DFIFO分支限界法（队列式分支限界法）

基本思想：

按照队列先进先出（FIF0）原则选取下一个活结点为扩展结点。

搜索策略：

一开始，根结点是唯一的活结点，根结点入队。

从活结点队中取出根结点后，作为当前扩展结点。

对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。

再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。

2）LC（Ieastcost）分支限界法（优先队列式分支限界法）

基本思想：

为了加速搜索的进程，应采用有效地方式选择活结点进行扩展。

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

搜索策略：

对每一活结点计算一个优先级（某些信息的函数值），并根据这些优先级；从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

再从活结点表中下一个优先级别最高的结点为当前扩展结点，……，直到找到一个解或活结点队列为空为止。

2、单源最短路径问题问题描述

在下图所给的有向图G中，每一边都有一个非负边权。

要求图G的从源顶点s到目标顶点t之间的最短路径。

（2）解空间数——排列树

下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。

从根节点s到一个叶子的一条路径表示从结点s到结点t的一条路径，路径上边的权的和为路径长度。

其中，每一个结点旁边的数字表示该结点所对应的当前路长。

（3）算法思想

采用优先队列式分支限界法来解本问题：

用一极小堆来存储活结点表，其优先级是结点所对应的当前路长。

算法从图G的源顶点s和空优先队列开始。

结点s被扩展后，它的儿子结点被依次插入堆中。

此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。

如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。

这个结点的扩展过程一直继续到活结点优先队列为空时为止。

在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法育去以该姑点为根的子树。

在算法中，利用结点间的控制关系进行剪枝。

从源顶点s出发，2条不同路径到达图G的同一顶点。

由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。

动态规划思想：

石子合并问题描述：

在一个圆形操场的四周摆放着n堆石子。

现要将石子有次序地合并成一堆。

规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。

开始以为通过贪心算法可能很快解决问题，可是是行不通的。

首先我们可以把这么堆石子看成一列我们假如5堆的石子，其中石子数分别为7,6,5,7,100按照贪心法，合并的过程如下：

每次合弁得分第一次合并7657100=1123/26总得分=13+12+25+125=175

第二次合并7

11

7100=18

第三次合并18

7

100=25

第四次合并

25

100=125

总得分=11+18+25+125=179

另一种合并方案

每次合并得分

第一次合并76

5

7100

->13

第二次合并

13

57

100->12

第三次合并

13

12100

->25

第四次合并

25

100->125

显然利用贪心来做是错误的，贪心算法在子过程中得出的解只是局部最优，而不能保证使得全局的值最优。

如果N-1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的N-1次合并后的得分总和必然是最优的。

因此我们需要通过动态规划算法来求出最优解。

在此我们假设有n地石子，一字排开，合并相邻两堆的石子，每合并两堆石子得到一个分数，最终合并后总分数最少的。

我们设m（i,j）定义为第i堆石子到第j堆石子合并后的最少总分数。

a（i）为第i堆石子得石子数量。

当合并的石子堆为1堆时，很明显m（i,i）的分数为0;当合并的石子堆为2堆时,m（i,i+1）的分数为a（i）+a（i+1）;当合并的石子堆为3堆时，m（i,i+2）的分数为MIN（（m（i,i）+m（i+1,i+2）+sum（i,i+2））,（m（i,i+1）+m（i+2,i+2）+sum（i,i+2））;

当合并的石子堆为4堆时数字三角形1、题目大意：

有一个由非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，如图12

2101

43220从第一行的数开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来，如何走才能使得这个和尽量大、dp[i][j]=max（dp[i-1][j-1],dp[i-1][j]）+a[i][j];这是一个多阶段决策性的问题一〉最优路径上的每一个数字开始的向下的路径也是该

数字到最下层的最优路径，符合最优化原理，可以考虑用动态规划的方法实现。

汽车加油行驶问题给定一个N*N的方形网格，设其左上角为起点◎,坐标为（1,1）,X轴向右为正，Y轴向下为正，每个方格边长为1,如图所示。

一辆汽车从起点◎出发驶向右下角终点山，其坐标为（N,N）o在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。

汽车在行驶过程中应遵守如下规则：

（1）汽车只能沿网格边行驶，装满油后能行驶K条网格边。

出发时汽车已装满油，在起点与终点处不设油库。

（2）汽车经过一条网格边时，若其X坐标或Y坐标减小，则应付费用B,否则免付费用。

（3）汽车在行驶过程中遇油库则应加满油并付加油费用A。

（4）在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费用A）o

（5）⑴〜⑷中的各数N、K、A、B、C均为正整数，且满足约束：

2WNW100,2WKW10。

设计一个算法，求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。

区间覆盖数轴上有n个区间［ai,bi］,选择尽量少的区间覆盖一条指定线段［s,t］。

贪心策略：

把各区间按照a从小到大排序，从前向后遍历，然后每次选择从当前起点S开始的最长区间，并以这个区间的右端点为新的起点，继续选择，直到找不到区间履盖当前起点S或者S已经到达线段末端。

需要注意的是，如果某一区间边界大于s,t的边界，应把它们变成s或打因为超出的部分毫无意义，同时还会影