算法设计与分析报告

湖北大学本科课程设计

题目批处理作业调度

姓名黄如嫣学号 2012221104230034 专业年级 2012级信息安全

指导教师马传香职称教授

目录

绪论 (4)

1 资料分析 (4)

1.1 分支界限算法 (4)

1.2 遗传算法 (4)

2 思路分析 (4)

2.1 分支界限算法分析 (4)

2.2 遗传算法分析 (5)

2.2.1 目标函数的建立 (6)

2.2.2 基本染色体的产生 (6)

2.2.3 选择初始种群 (6)

2.2.4 适应度函数 (6)

2.2.5 选择策略 (6)

2.2.6 变异 (6)

3 成果展示 (7)

3.1 分支界限算法截图 (7)

3.2 遗传算法截图 (7)

4 理论分析 (8)

4.1 分支界限算法 (8)

4.2 遗传算法 (9)

5 实验性能比较 (9)

5.1 遗传算法性能 (10)

5.2 分支界限算法性能 (10)

参考文献 (11)

附录 (12)

批处理作业调度

摘要

批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以批处理作业调度问题的解空间树是一颗排列数；和研究了遗传算法在车间作业调度问题中的应用,以遗传算法作为优化工具,给出了车间作业调度算法.最后给出了计算机仿真结果,并与启发式算法求得的结果作了比较,证明了该算法解的有效性和优越性。

【关键词】批处理作业调度分支界限算法车间作业调度问题遗传算法

绪论

给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。.

1.资料分析

1.1 分支界限算法

给定n个作业的集合J={J1,J2,…,Jn}。每一个作业Ji都有2项任务要分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。作业Ji需要机器j的处理时间为tji，i=1,2,…,n；j=1,2。对于一个确定的作业调度，设是Fji是作业i在机器j上完成处理的时间。则所有作业在机器2上完成处理的时间和f=∑F2i称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。批处理作业调度问题要求对于给定的n个作业，制定一个最佳作业调度，使其完成时间和达到最小。批处理作业调度问题的一个常见例子是在计算机系统中完成一批n个作业，每个作业都要完成计算，然后将计算结果打印输出这两项任务。计算任务由计算机的中央处理器完成，打印输出任务由打印机完成。因此在这种情况下，计算机的中央处理器是机器1，打印机是机器2。对于批处理作业调度问题，可以证明，存在一个最佳作业调度使得在机器1和机器2上作业已相同次序完成。

1.2 遗传算法

车间作业调度（简称 J s S )的启发式算法,是用某一调度优先级规则在当前可调度工序 (其紧前工序已完成且加工使用机床空闲)中选择一个工序进行加工,最终形成一个由所有被加工零件各工序组成的序列,即所谓调度结果。由于调度规则通常只针对特定问题和特定环境,它存在着难以克服的缺点,如计算规模不可能较大,寻优具有局部性等,而基于遗传算法的车间作业调度的基本思想是,预先排列出若干个由工序组成的序列,然后对这些序列进行遗传进化操作,从而达到优化调度结果性能指标的目的.由于遗传算法只利用适应性信息,它不要求目标函数可微、连通和凸性,因而它是一种高效率的随机搜索与优化的方法,具有搜索面广，算法速度快等优点。

2. 思路分析

2.1 分支界限算法分析

批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列数。

算法中用最小堆表示活结点优先队列。最小堆中元素类型是MinHeapNode。每一个MinHeapNode类型的结点包含域x，用来表示结点所相应的作业调度。S表示该结点已安排的作业是x[1:s]。f1表示当前已安排的作业在机器1上的最后完成时间；f2表示当前已安排的作业在机器2上的最后完成时间；sf2表示当前已安排的作业在机器2上的完成时间和；bb表示当前完成时间和的下界。函数int完成最小堆结点初始化；函数NewNode产生最小堆新结点。

算法将当前扩展结点E分为两种情形处理。

当E.s=n时，已排定n个作业，故当前扩展结点E是排列数中的一个叶节点。E.x表示相应于改结点的作业调度。E.fs2是相应于改叶节点的完成时间和。

当E.s

2.2 遗传算法分析

由遗传算法的运行机理可知,不论JSS染色体编码怎样设计,它必须能够直接或间接地表达JsS的一个可行解，如果J S S染色体编码直接代表JSS的可行解,称为直接编码; 如果JSS染色体编码需要进行一定的转换才能表示JSS的可行解,叫做间接编码.对于J SS问题,其可行解为所有被加工零件各工序组成的序列.我们采用直接编码的方式,这样消除了遗传算法应用于JSS受到成组技术的局限性.合理化等。

2.2.1 目标函数的建立

我们把优化调度结果转化如下目标函数的优化

其中C ( i)为全部m台机器中第i台机器的总加工时间,( TM J) 为总的完工时间。

2.2.2 基本染色体的产生

JS染色体编码是一个有序的编码串代表着工件的第几个工序在哪台机器上加工及加工时间，并且转换后jS S 编码与J Ss有效解应该一一对应保证s JS解的有效性,基于染色体编码的要求,我们采用单一编码方式。将所有工件的总的工序统一编号。

例如，对于n个工件m台机器,第i个工件的工序数为k`,k二max{ kl,k :,…,k。},这样的调度问题可以用如下方式表示:

2.2.3 选择初始种群

随机产生与群体规模一致的个数为kn的染色体串作为初始种群，其中每个染色体串用以上方式表示，保持各基因之间的相互独立。

2.2.4 适应度函数

适应度函数在子代的产生中起着重要的作用，由于是求问题的最小值，为了使遗传算法对适应度较高的个体有更多的生存机会，本文通过对目标函数到MJ)进行变换得到适应度函数F(MJ)，即取F(MJ)=a+夕T( M J )，a谓为常数，目标函数为；T(MJ)=ma x[C(l)，C(2),…,C (i),…,c (m)]。

2.2.5 选择策略

每代中的每一个个体，按照适应度的大小决定它能够复制到下一代的概率，通过复制，使得群体中的优秀个体数目不断增加整个优化过程朝着更优解的方向进行反映了优胜劣汰的原则，各个个体的选择概率和其适应度成正比例，另P(k )为个体k的选择概率，则

令s ( 0)=0，s ( k )=P( l )+P ( 2 )+…+P ( k ),k=l，2，…，nk，其中pop-size为群体规模,共产生 k n 个0一1 均匀分布的随机数，若s (k一l )<∮<：s ( k )，则选个体k为下一代的父代,其中∮:为0一1 的随机数,s =1,2,…,k n.

2.2.6 变异

复制和交叉只能在现有的基因型的排列和组合内寻找最优，而不能产生新的基因型，变异算子对每个个体的每一位按变异概率产生新的变化，产生新的基因型，扩大了寻优范围，从而有利于保证算法的全局最优性。

3 成果展示

3.1 分支界限算法截图

图3-1 分支界限算法截图

3.2 遗传算法截图

图3-2 车间作业调度的整体结构流程图

图3-2 成果截图

4.理论分析

4.1 分支界限算法

在作业调度问相应的排列空间树中，每一个节点E都对应于一个已安排的作业集

。以该节点为根的子树中所含叶节点的完成时间和可表示为：

设|M|=r，且L是以节点E为根的子树中的叶节点，相应的作业调度为{pk,k=1,2,……n}，

其中pk是第k个安排的作业。如果从节点E到叶节点L的路上，每一个作业pk在机器1

上完成处理后都能立即在机器2上开始处理，即从pr+1开始，机器1没有空闲时间，则对于该叶节点L有：

注：(n-k+1)t1pk,因为是完成时间和，所以，后续的(n-k+1)个作业完成时间和都得算上t1pk。

如果不能做到上面这一点，则s1只会增加，从而有：。类似地，如果从节点E 开始到节点L的路上，从作业pr+1开始，机器2没有空闲时间，则：

同理可知，s2是的下界。由此得到在节点E处相应子树中叶节点完成时间和的下界是：

注意到如果选择Pk，使t1pk在k>=r+1时依非减序排列，S1则取得极小值。同理如果选择Pk使t2pk依非减序排列，则S2取得极小值。

所以时间复杂度为O(n!)。

4.2 遗传算法

遗传算法（Genetic Algorithm）作为一种优化算法特别适合于对象模型难于建立、搜索空间非常庞大的复杂问题的优化求解。它和模糊控制技术一样，虽然在理论上还没有完善，但是在实践中已经得到了广泛的应用。遗传算法的基本思想是：模仿生物系统“适者生成"的原理，通过选择、复制、交叉、变异等简单操作的多次重复来达到去劣存优的目的，从而获得问题的优化结果。遗传算法的实现由两个部分组成，一是编码与解码，二是遗传操作。其中遗传操作又包括选择、复制、交叉、变异等步骤。所以时间复杂度为0(n^2)。

5 实验性能比较

5.1 遗传算法性能

遗传算法以决策变量的编码作为运算对象。分支界限算法直接利用决策变量的实际值本身进行优化运算，从而很方便的引入和应用遗传操作算子。遗传算法直接以目标函数值作为搜索信息。分支界限算法不只需要目标函数值还需要导数等其他信息。遗传算法同时进行解空间的多点搜索。分支界限算法从解空间的一个初始点开始搜索。遗传算法进行群体搜索，使群体不断进化。遗传算法采用概率搜索技术，其选择，交叉，变异等运算都是以概率的方式来进行的，增加了其搜索过程的灵活性。

5.2 分支界限算法性能

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。

6 心得体会

采用遗传算法可对一个理论上无法求尽的NP问题以较有效方法在较短时间内得到较精确解。但还不全面，只是一个简单模型，未考虑收敛性,适配值等，对参数设置与最优解关系研究还不够深入。还有理解不同算法的实质和比较差异，从而找到相对较优的算法。

参考文献

[1] 王凌编著．车间调度及遗传算法．北京：清华大学出版社，2003

[2] 熊锐编著. 车间生产调度问题的技术现状与发展趋势. 北京：清华大学学报，2000

[3] 李晓东编著.计算机算法设计与分析.北京：电子工业出版社,2012

[4] 王沫然编著.MATLAB6.0 与科学计算. 北京：电子工业出版社,2003

[5] 张可村，赵英良编著.数值计算的算法与分析. 北京：科学出版社,2003

附录

分支界限算法（c++）

#include

#include

using namespace std;

class MinHeapNode

{

friend class Flowshop;

public:

bool operator<(const MinHeapNode &a) const{return a.bb

private:

void Init(int);

void NewNode(MinHeapNode,int,int,int,int);

int s; //已安排作业数

int f1; //机器 1 上最后完成时间

int f2; //机器 2 上最后完成时间

int sf2; //当前机器 2 上的完成时间和

int bb; //当前完成时间和下界

int *x; //当前作业调度

};

void MinHeapNode::Init(int n)

{ //最小堆结点初始化

x=new int[n];

for(int i=0;i

x[i]=i;

s=0;

f1=0;

f2=0;

sf2=0;

bb=0;

}

void MinHeapNode::NewNode(MinHeapNode E,int Ef1,int Ef2,int Ebb,int n) { //最小堆新结点

x=new int[n];

for(int i=0;i

x[i]=E.x[i];

f1=Ef1;

f2=Ef2;

sf2=E.sf2+f2;

bb=Ebb;

s=E.s+1;

}

class Flowshop

{

friend int main();

public:

int BBFlow();

private:

Flowshop(int n); //构造函数

~Flowshop(); //析构函数

int Bound(MinHeapNode,int &,int &,bool **); void Sort();

int n;

int **M;

int **b;

int **a;

int *bestx;

int bestc;

bool **y;

};

Flowshop::Flowshop(int n)

{

//M=new int *[n];

b=new int *[n];

a=new int *[n];

y=new bool *[n];

bestx=new int [n];

bestc=10000;

for(int i=0;i

{

//M[i]=new int[2];

b[i]=new int[2];

a[i]=new int[2];

y[i]=new bool[2];

}

}

Flowshop::~Flowshop()

{

for(int i=0;i

{

delete []M[i];

delete []b[i];

delete []a[i];

delete []y[i];

}

delete bestx,M,b,a,y;

}

void Flowshop::Sort()

{ //对各作业在机器 1 和 2 上所需时间进行冒泡排序

int *c=new int[n];

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

{

for(int i=0;i

{

b[i][j]=M[i][j];

c[i]=i;

}

for(i=0;i

for(int k=n-1;k>i;k--)

if(b[k][j]

{

swap(b[k][j],b[k-1][j]);

swap(c[k],c[k-1]);

}

for(i=0;i

a[c[i]][j]=i;

}

delete []c;

}

int Flowshop::Bound(MinHeapNode E,int &f1,int &f2,bool **y) { //计算完成时间和下界

for(int k=0;k

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

y[k][j]=0;

for(k=0;k<=E.s;k++)

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

y[a[E.x[k]][j]][j]=1;

f1=E.f1+M[E.x[E.s]][0];

f2=((f1>E.f2)?f1:E.f2)+M[E.x[E.s]][1];

int sf2=E.sf2+f2;

int s1=0,s2=0,k1=n-E.s,k2=n-E.s,f3=f2;

//计算 s1 的值

for(int j=0;j

if(!y[j][0])

{

k1--;

if(k1==n-E.s-1)

f3=(f2>f1+b[j][0])?f2:f1+b[j][0];

s1+=f1+k1*b[j][0];

}

//计算 s2 的值

for(j=0;j

if(!y[j][1])

{

k2--;

s1+=b[j][1];

s2+=f3+k2*b[j][1];

}

//返回完成时间和下界

return sf2+((s1>s2)?s1:s2);

}

int Flowshop::BBFlow()

{

Sort();

priority_queue H; MinHeapNode E;

E.Init(n);

while(E.s<=n)

{

if(E.s==n)

{

if(E.sf2

{

bestc=E.sf2;

for(int i=0;i

bestx[i]=E.x[i];

}

delete []E.x;

}

else

{

for(int i=E.s;i

{

swap(E.x[E.s],E.x[i]);

int f1,f2;

int bb=Bound(E,f1,f2,y);

if(bb

{

MinHeapNode N;

N.NewNode(E,f1,f2,bb,n);

H.push(N);

}

swap(E.x[E.s],E.x[i]);

}

delete []E.x;

}

if(H.empty())

break;

else

{

E=H.top();

H.pop();

}

}

return bestc;

}

int main()

{

int n;

cout<<"输入作业数:";

cin>>n;

int **M=new int*[n];

for(int i=0;i

M[i]=new int[2];

for(i=0;i

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

{

cout<<"M["<

cin>>M[i][j];

}

Flowshop G(n);

G.M=M;

G.n=n;

int f=G.BBFlow();

cout<<"最佳调度方案:";

for(i=0;i

cout<

cout<

cout<<"最佳完成时间和:"<

return 0;

}

遗传算法（Matlab）

function [Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA(M,N,Pm,T,P) %-------------------------------------------------------------------------- % JSPGA.m

% 车间作业调度问题遗传算法

%--------------------------------------------------------------------------

% 输入参数列表

% M 遗传进化迭代次数

% N 种群规模(取偶数)

% Pm 变异概率

% T m×n的矩阵，存储m个工件n个工序的加工时间

% P 1×n的向量，n个工序中，每一个工序所具有的机床数目

% 输出参数列表

% Zp 最优的Makespan值

% Y1p 最优方案中，各工件各工序的开始时刻，可根据它绘出甘特图

% Y2p 最优方案中，各工件各工序的结束时刻，可根据它绘出甘特图

% Y3p 最优方案中，各工件各工序使用的机器编号

% Xp 最优决策变量的值，决策变量是一个实数编码的m×n矩阵

% LC1 收敛曲线1，各代最优个体适应值的记录

% LC2 收敛曲线2，各代群体平均适应值的记录

% 最后，程序还将绘出三副图片：两条收敛曲线图和甘特图（各工件的调度时序图）

%第一步：变量初始化

[m,n]=size(T);%m是总工件数，n是总工序数

Xp=zeros(m,n);%最优决策变量

LC1=zeros(1,M);%收敛曲线1

LC2=zeros(1,N);%收敛曲线2

%第二步：随机产生初始种群

farm=cell(1,N);%采用细胞结构存储种群

for k=1:N

X=zeros(m,n);

for j=1:n

for i=1:m

X(i,j)=1+(P(j)-eps)*rand;

end

end

end

counter=0;%设置迭代计数器

while counter

%第三步：交叉

newfarm=cell(1,N);%交叉产生的新种群存在其中

Ser=randperm(N);

for i=1:2:(N-1)

A=farm{Ser(i)};%父代个体

B=farm{Ser(i+1)};

Manner=unidrnd(2);%随机选择交叉方式

if Manner==1

cp=unidrnd(m-1);%随机选择交叉点

%双亲双子单点交叉

a=[A(1:cp,:);B((cp+1):m,:)];%子代个体

b=[B(1:cp,:);A((cp+1):m,:)];

else

cp=unidrnd(n-1);%随机选择交叉点

a=[A(:,1:cp),B(:,(cp+1):n)];%双亲双子单点交叉

b=[B(:,1:cp),A(:,(cp+1):n)];

end

newfarm{i}=a;%交叉后的子代存入newfarm

newfarm{i+1}=b;

end

%新旧种群合并

FARM=[farm,newfarm];

%第四步：选择复制

FITNESS=zeros(1,2*N);

fitness=zeros(1,N);

for i=1:(2*N)

X=FARM{i};

Z=COST(X,T,P,plotif);%调用计算费用的子函数

FITNESS(i)=Z;

end

%选择复制采取两两随机配对竞争的方式，具有保留最优个体的能力Ser=randperm(2*N);

for i=1:N

f1=FITNESS(Ser(2*i-1));

f2=FITNESS(Ser(2*i));

if f1<=f2

farm{i}=FARM{Ser(2*i-1)};

fitness(i)=FITNESS(Ser(2*i-1));

else

farm{i}=FARM{Ser(2*i)};

fitness(i)=FITNESS(Ser(2*i));

end

end

%记录最佳个体和收敛曲线

minfitness=min(fitness)

meanfitness=mean(fitness)

LC1(counter+1)=minfitness;%收敛曲线1，各代最优个体适应值的记录LC2(counter+1)=meanfitness;%收敛曲线2，各代群体平均适应值的记录pos=find(fitness==minfitness);

Xp=farm{pos(1)};

%第五步：变异

for i=1:N

if Pm>rand;%变异概率为Pm

X=farm{i};

I=unidrnd(m);

J=unidrnd(n);

X(I,J)=1+(P(J)-eps)*rand;

farm{i}=X;

end

end

farm{pos(1)}=Xp;

counter=counter+1

end

%输出结果并绘图

figure(1);

plotif=1;

X=Xp;

[Zp,Y1p,Y2p,Y3p]=COST(X,T,P,plotif); figure(2);

plot(LC1);

figure(3);

plot(LC2);

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

算法设计与分析考试题 及答案 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类问题。。

2005.6算法设计与分析课程期末试卷

华南农业大学期末考试试卷（A卷） 2004学年第二学期(2005.6)考试科目：算法设计与分析考试类型：（开卷）考试时间：120分钟 学号姓名年级专业 一、选择题（30分，每题2分） 1、一个算法应该包含如下几条性质，除了 A 。 （A）二义性（B）有限性（C）正确性（D）可终止性 2、解决一个问题通常有多种方法。若说一个算法“有效”是指 D 。 （A）这个算法能在一定的时间和空间资源限制内将问题解决 （B）这个算法能在人的反应时间内将问题解决 （C）这个算法比其他已知算法都更快地将问题解决 （D）A和C 3、当输入规模为n时，算法增长率最小的是 B 。 （A）5n （B）20log2n（C）2n2（D）3nlog3n 4、渐进算法分析是指 B 。 （A）算法在最佳情况、最差情况和平均情况下的代价 （B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析（C）数据结构所占用的空间 （D）在最小输入规模下算法的资源代价 5、当上下限表达式相等时，我们使用下列哪种表示法来描述算法代价？C （A）大O表示法（B）大Ω表示法 （C）Θ表示法（D）小o表示法 6、采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素。以下对顺序搜索法分析正确的是 B 。

（A）最佳情况、最差情况和平均情况下，顺序搜索法的渐进代价都相同 （B）最佳情况的渐进代价要好于最差情况和平均情况的渐进代价 （C）最佳情况和平均情况的渐进代价要好于最差情况的渐进代价 （D）最佳情况的渐进代价要好于平均情况的渐进代价，而平均情况的渐进代价要好于最差情况的渐进代价 7、递归通常用 C 来实现。 （A）有序的线性表（B）队列（C）栈（D）数组 8、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。C （A）问题规模相同，问题性质相同 （B）问题规模相同，问题性质不同 （C）问题规模不同，问题性质相同 （D）问题规模不同，问题性质不同 9、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n 个元素进行划分，如何选择划分基准？下面 D 答案解释最合理。 （A）随机选择一个元素作为划分基准 （B）取子序列的第一个元素作为划分基准 （C）用中位数的中位数方法寻找划分基准 （D）以上皆可行。但不同方法，算法复杂度上界可能不同 10、对于0－1背包问题和背包问题的解法，下面 C 答案解释正确。 （A）0－1背包问题和背包问题都可用贪心算法求解 （B）0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解 （C）0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解 （D）因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解 11、关于回溯搜索法的介绍，下面D是不正确描述。 （A）回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解（B）回溯法是一种既带系统性又带有跳跃性的搜索算法 （C）回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯 （D）回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径 改：树结构 回溯法，又被称为通用解题法，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间中按深度优先策略，从根结

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

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

算法设计与分析复习资料1

一 1.循环赛日程表问题的相关叙述。 2.算法运行时所需要占用的存储空间有？ 3.动态规划法的求解步骤 4.解空间树是排列树的问题有。 5.分治法的步骤 6.就会场安排问题，贪心法的最佳贪心策略 7.快速排序法基准元素的选取方法 8.满足满m叉树的问题有？ 9.分支限界法的解题步骤 10.事前分析法相关的影响因素有 11.用分治法求解的问题一般需要具备一些特征，主要有？ 二 1．给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。 2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n 元组。 3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。 4．一个正在生成孩子的结点称为扩展结点。 5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。 6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。 7．一个自身已生成但其孩子还没有全部生成的结点称为活结点 8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间 9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。 10．分支限界法采用的是宽度优先搜索。 11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法 12．一个所有孩子已经生成的结点称做死结点 13．在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。 三 1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。 2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采

算法设计与分析试卷(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 ）。

算法设计与分析课后部分习题答案

算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中

for(i=0;i=0;row--)//从上往下递归计算 for(int col=0;col<=row;col++) if(triangle[row+1][col]>triangle[row+1][col+1]) triangle[row][col]+=triangle[row+1][col]; else triangle[row][col]+=triangle[row+1][col+1]; out=fopen("output.txt","w"); fprintf(out,"%d",triangle[0][0]);//将最终结果输出到output.txt中 } 算法实现题4-9 汽车加油问题 问题描述： 一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产出一个最优解。编程任务： 对于给定的n和k个加油站位置，编程计算最少加油次数。数据输入： 由文件input.txt给出输入数据。第1行有2个正整数n和k ，表示汽车加满油后可行驶nkm，且旅途中有k个加油站。接下来的1行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第

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

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

算法设计与分析课程设计(完整版)

HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日

一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。

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

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

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

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

压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行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.1 (a)6 (b)5 (c)6 (d)6 1.4 算法执行了7+6+5+4+3+2+1=28次比较 1.5 (a)算法MODSELECTIONSORT执行的元素赋值的最少次数是0,元素已按非降序排列的时候达到最小值。

(b) 算法MODSELECTIONSORT 执行的元素赋值的最多次数是3(1)2 n n ,元素已按非升序排列的时候达到最小值。 1.7 由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次。 1.11

由上图可以得出比较次数为5+6+6+9=26次。 1.13 FTF,TTT,FTF,TFF,FTF 1.16 (a) 执行该算法，元素比较的最少次数是n-1。元素已按非降序排列时候达到最小值。 (b) 执行该算法，元素比较的最多次数是(1)2 n n -。元素已 按非升序排列时候达到最大值。 (c) 执行该算法，元素赋值的最少次数是0。元素已按非降序排列时候达到最小值。 (d) 执行该算法，元素赋值的最多次数是3(1)2 n n -。元素已 按非升序排列时候达到最大值。 (e)n 用O 符号和Ω符号表示算法BUBBLESORT 的运行时间：2()t O n =，()t n =Ω

(f)不可以用Θ符号来表示算法的运行时间：Θ是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列，因此不能用这一符号表示。 1.27 不能用p 关系来比较2n 和2100n 增长的阶。 ∵221 lim 0100100 n n n →∞=≠ 2n ∴不是2(100)o n 的，即不能用p 关系来比较2n 和2100n 增长 的阶。 1.32 (a)当n 为2的幂时，第六步执行的最大次数是： 12,2k k n j -==时， 1 1 [log ]log n n i i k n n n ====∑∑ (b)由(a)可以得到：当每一次循环j 都为2的幂时，第六步执行的次数最大， 则当33,22k k m n j ===（其中 32 k 取整）时， 1 1 [log(3 1)]log(1)n n k i i i m n n ===-=-∑∑ (c)用O 符号表示的算法的时间复杂性是(log )O n n 已证明n=2k 的情况，下面证明n=2k +1的情况： 因为有?? ? ???+=??????21222k k 所以n=2k +1时，第六步执行的最大次数仍是n log n 。

算法设计与分析试卷及答案.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. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。

算法设计与分析课程设计-实验指导书

算法设计与分析课程设计 实验指导书 上海第二工业大学 计算机与信息学院软件工程系

一、运动员比赛日程表 设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表： ●每个选手必须与其它n-1个选手各赛一次 ●每个选手一天只能赛一次 ●循环赛一共进行n-1天 1、运用分治策略，该问题的递归算法描述如下，根据算法编制程序并上机 通过。 输入：运动员人数n（假定n恰好为2的i次方） 输出：比赛日程表A[1..n,1..n] 1. for i←1 to n //设置运动员编号 2. A[i,1]←i 3. end for 4. Calendar(0,n) //位移为0，运动员人数为n。 过程Calendar(v, k) //v表示位移（v=起始行-1），k表示运动员人数。 1. if k=2 then //运动员人数为2个 2. A[v+2,2]←A[v+1,1] //处理右下角 3. A[v+1,2]←A[v+2,1]//处理右上角 4. else 5. Calendar(v,k/2) //假设已制定了v+1至v+k/2运动员循环赛日程表 6. Calendar(v+k/2,k/2) //假设已制定了v+k/2+1至v+k运动员循环赛日程表 7. comment：将2个k/2人组的解，组合成1个k人组的解。 8. for i←1 to k/2 9. for j←1 to k/2 10. A[v+i+k/2,j+k/2]←A[v+i,j] //沿对角线处理右下角 11. end for 12. end for 13. for i←k/2+1 to k 14. for j←1 to k/2 15. A[v+i-k/2,j+k/2]←A[v+i,j] //沿对角线处理右上角 16. end for 17. end for 18. end if 2、编制该问题的非递归算法，上机通过。 将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。

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

算法设计与分析 1、(1) 证明：O(f)+O(g)=O(f+g)（7分） (2) 求下列函数的渐近表达式：（6分） ① 3n 2+10n; ② 21+1/n; 2、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并简述理由。（15分） (1) ;5log )(;log )(2+==n n g n n f (2) ;)(;log )(2n n g n n f == (3) ;log )(;)(2n n g n n f == 3、试用分治法对数组A[n]实现快速排序。（13分） 4、试用动态规划算法实现最长公共子序列问题。（15分） 5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。（12分） 6、试用动态规划算法实现下列问题：设A 和B 是两个字符串。我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括： (1)删除一个字符。 (2)插入一个字符。 (3)将一个字符改为另一个字符。 将字符串A 变换为字符串B 所用的最少字符操作数称为字符串A 到B 的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符串A 和B ，计算出它们的编辑距离d(A,B)。

（16分） 7、试用回溯法解决下列整数变换问题：关于整数i 的变换f 和g 定义如下：??2/)(;3)(i i g i i f ==。对于给定的两个整数n 和m ，要求用最少的变换f 和g 变换次数将n 变为m 。（16分）

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

一、填空题（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.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；

②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai=bi}； ②将N1中作业按ai的非减序排序得到N1’，将N2中作业按bi的非增序排序得到N2’； ③N1’中作业接N2’中作业就构成了满足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个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N1’={1，3}， N2’={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)}。 解空间树为：