算法设计与分析大作业答案Word格式文档下载.docx
- 文档编号:8208927
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:15
- 大小:449.67KB
算法设计与分析大作业答案Word格式文档下载.docx
《算法设计与分析大作业答案Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《算法设计与分析大作业答案Word格式文档下载.docx(15页珍藏版)》请在冰点文库上搜索。
clearall;
n=[1050100150200300400500100002000050000100000];
x=2;
fori=1:
12
a=rand(1,(n(i)+1));
%产生多项式,最高次幂为n(i)+1
tic;
p1(i)=polyval(a,x);
%直接代入法
t1(i)=toc;
p2(i)=0;
forj=1:
(n(i)+1)
p2(i)=p2(i)+a(j)*x^(j-1);
%递归法1
end
t2(i)=toc;
p3(i)=0;
q=1;
forj=2:
q=q*x;
p3(i)=p3(i)+a(j)*q;
%递归法2
t3(i)=toc;
p4(i)=0;
n(i);
p4(i)=x*p4(i)+a(n(i)+1-j);
%递归法3
end
t4(i)=toc;
end
figure
(1);
subplot(2,2,1);
h=semilogx(n,t1);
%这里不能用plot,横轴需要取对数,下同
set(h,'
linestyle'
'
-'
linewidth'
1.8,'
marker'
*'
color'
g'
markersize'
6);
xlabel('
Thescaleoftheproblem:
n'
);
ylabel('
timeforfirstmethod(s)'
title('
therelationshipbetweentimeandscale'
gridon;
subplot(2,2,2);
h=semilogx(n,t2);
b'
timeforsecondmethod(s)'
subplot(2,2,3);
k'
timeforthirdmethod(s)'
subplot(2,2,4);
r'
timeforforthmethod(s)'
figure
(2);
g=semilogx(n,t1,'
g+'
n,t2,'
bx'
n,t3,'
k*'
n,t4,'
ro'
legend('
thefirstmethod'
thesecondmethod'
thethirdmethod'
theforthmethod'
set(g,'
2.0,'
8);
n=10,50,100,150,200,300,400,500,10000,20000,50000,100000'
time'
Thecomparisonchartoffourdifferentmethodsforpolyval'
运行结果如下:
图1.1四种方法所用时间随规模不同而变化的结果图
图1.2四种方法所用时间随规模不同而变化的对比图
由理论分析可知,四种算法的时间复杂度分别为
、
,由图1.2分析可知,直接带入计算和递归法所用时间相差无几,这与理论分析一直。
而第三种方法与第四种方法的差异可能是由于每次加法所用时间与每次乘法所用时间不同所导致。
另外,在问题规模较小(n<
1000)时,在图上几乎看不出区别,更精细的分析需要更深入地讨论,本文不做讨论。
2、分析题意可知,要利用四种方法计算矩阵相乘,每种方法取矩阵大小从
~
不同的规模。
矩阵计算法、定义法、分治法和Strassen方法。
详细程序如下:
程序2.1
文件名matrix.m
%比较三种算法的运行时间与MATLAB自带的矩阵相乘的运行时间
n=[2^22^32^42^52^62^72^82^92^102^112^12];
form=1:
11
A=round(rand(n(m)));
%随机生成矩阵
B=round(rand(n(m)));
C1=A*B;
%MATLAB自带的矩阵相乘
t1(m)=toc;
C2=zeros(n(m));
fori=1:
n(m)
fork=1:
C2(i,j)=C2(i,j)+A(i,k)*B(k,j);
%按照定义进行计算
t2(m)=toc;
A11=A(1:
n(m)/2,1:
n(m)/2);
A12=A(1:
n(m)/2,n(m)/2+1:
n(m));
A21=A(n(m)/2+1:
n(m),1:
A22=A(n(m)/2+1:
n(m),n(m)/2+1:
B11=B(1:
B12=B(1:
B21=B(n(m)/2+1:
B22=B(n(m)/2+1:
C3=zeros(n(m));
C11=A11*B11+A12*B21;
%分治法
C12=A11*B12+A12*B22;
C21=A21*B11+A22*B21;
C22=A21*B12+A22*B22;
C3=[C11C12;
C21C22];
t3(m)=toc;
C4=zeros(n(m));
M1=A11*(B12-B22);
M2=(A11+A12)*B22;
M3=(A21+A22)*B11;
M4=A22*(B21-B11);
M5=(A11+A22)*(B11+B22);
M6=(A12-A22)*(B21+B22);
M7=(A11-A21)*(B11+B12);
C11=M5+M4-M2+M6;
%Strassen方法
C12=M1+M2;
C21=M3+M4;
C22=M5+M1-M3-M7;
C4=[C11C12;
t4(m)=toc;
Thescaleofthematrix:
theMATLABmethod'
thedefinitionmethod'
分治法'
theStrassenmethod'
n=2^22^32^42^52^62^72^82^92^102^112^12'
Thecomparisonchartoffourdifferentmethodsformatrixmultiplication'
实验结果如下:
图2.1四种方法所用时间随规模不同而变化的结果图
3、
方法1:
将原函数取负,求
的最小值即得原函数的最大值。
程序采用MATLAB自带的工具箱实现,程序如下:
程序3.1
文件名main_function.m
用遗传算法求解带约束二元函数的最大值
G=100;
%进化的代数
optionsOrigin=gaoptimset('
Generation'
G/2);
[x,fval,reason,output,final_pop]=ga(@fun,2,optionsOrigin);
options1=gaoptimset('
G/2,'
InitialPopulation'
final_pop,'
PlotFcns'
@gaplotbestf);
[x,fval,reason,output,final_pop]=ga(@fun,2,options1);
Bestx=x
BestFval=fval
%子程序:
带约束的目标函数
functionf=fun(x)
if(x
(1)>
12.1|(x
(2)>
5.8))
f=inf;
elseif(x
(1)<
-3.0|x
(2)<
4.1)
else
f=-(21.5+x
(1)*sin(4*pi*x
(1))+x
(2)*sin(20*pi*x
(2)));
运行后的结果:
Bestx=
11.61845.7273
BestFval=
-38.7478
从而可知原函数在(11.6184,5.7273)取得最大值38.7478。
方法2:
按照遗传算法的思路编程,程序如下:
程序3.2
%进化代数
N=80;
%群体规模
pm=0.05;
%变异概率
pc=0.8;
%交叉概率
u1max=12.1;
u1min=-3.0;
%参数取值范围
u2max=5.8;
u2min=4.1;
%参数取值范围
L=10;
%单个参数字串长度,总编码长度2L
bval=round(rand(N,2*L));
%随机产生初始种群
bestv=-inf;
%最优适应度初值
fork=1:
G
N
y1=0;
y2=0;
1:
L
y1=y1+bval(i,L-j+1)*2^(j-1);
x1=(u1max-u1min)*y1/(2^L-1)+u1min;
y2=y2+bval(i,2*L-j+1)*2^(j-1);
x2=(u2max-u2min)*y2/(2^L-1)+u2min;
fun(i)=21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2);
%目标函数
xx(i,:
)=[x1,x2];
fitfun=fun;
%目标函数转换为适应度函数
p=fitfun./sum(fitfun);
%轮盘赌选择函数
q=cumsum(p);
[fmax,indmax]=max(fitfun);
%记录每一代最佳个体
iffmax>
=bestv
bestv=fmax;
%到目前为止最优适应度值
bvalxx=bval(indmax,:
%到目前为止最佳位串
optxx=xx(indmax,:
%到目前为止最优参数
Bestfit(k)=bestv;
%记录每代的最优适应度
(N-1)
r=rand;
tmp=find(r<
=q);
newbval(i,:
)=bval(tmp
(1),:
newbval(N,:
)=bvalxx;
%最优保留
bval=newbval;
2:
cc=rand;
ifcc<
pc
point=ceil(rand*(2*L-1));
ch=bval(i,:
bval(i,point+1:
2*L)=bval(i+1,point+1:
2*L);
bval(i+1,point+1:
2*L)=ch(1,point+1:
bval(N,:
mm=rand(N,2*L)<
pm;
bval(mm)=1-bval(mm);
plot(Bestfit);
%绘制最优适应度进化曲线
FitnessValue'
TherelationshipbetweenFitnessValueandGeneration'
Optxx
bestv
optxx=
11.6276637341153485.525806451612903
bestv=
38.639864218199662
从而可知原函数在(11.627663734115348,5.525806451612903)取得最大值38.639864218199662。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 作业 答案
![提示](https://static.bingdoc.com/images/bang_tan.gif)