算法設(shè)計(jì)與分析大作業(yè)答案

算法設(shè)計(jì)技術(shù)與方法

大作業(yè)

學(xué)院電子工程學(xué)院

專(zhuān)業(yè)_________電路與系統(tǒng)____________

姓名________________________________

學(xué)號(hào)________________________________

導(dǎo)師姓名

作業(yè)

1.分別實(shí)現(xiàn)多項(xiàng)式求值的四種運(yùn)算，若針對(duì)不同規(guī)模的輸入值a,各算法的運(yùn)行時(shí)間，問(wèn)題

規(guī)模n分別取10,50,100,150,200,300,400,500,10000,20000,50000,100000

時(shí)繪制四種算法運(yùn)行時(shí)間的比較圖。

2.分別實(shí)現(xiàn)矩陣相乘的3種算法，比較三種算法在矩陣大小分別為22x22,23X23,24X24,

25X25,26X26,27X27,28x28,29x29,210x210,2nx2u,時(shí)的運(yùn)行時(shí)

間與MATLAB自帶的矩陣相乘的運(yùn)行時(shí)間，繪制時(shí)間對(duì)比圖。

3.利用遺傳算法求解下面的問(wèn)題:

max/(x15x2)=21.5+x；-sin(4^x1)+x2'sin(20^x2)

-3.0<x,<12.1

s.t.<

4.1<x2<5.8

1、分析題意可知，該題要用四種不同的方法實(shí)現(xiàn)對(duì)多項(xiàng)式的求值計(jì)算，每種方法取從

10-100000不同的規(guī)模。本文采用了以下方法進(jìn)行求值：直接代入法和遞歸法。而其中遞歸

法分三類(lèi)不同思路進(jìn)行遞歸：

①Pn(x)=Pn-i(x)+anx\

②P=a0,Q=l,Q=Qx,P=P+atQ；

③由x)=%(尤)x+%。

本文對(duì)上述四種方法進(jìn)行了編程，具體代碼如下：

程序1.1文件名poly.m

%主程序：實(shí)現(xiàn)不同規(guī)模下多項(xiàng)式求值的四種運(yùn)算

clc；

closeall；

clearall；

n=[1050100150200300400500100002000050000100000];

x=2;

fori=l：12

a=rand(l,(n(i)+1))；%產(chǎn)生多項(xiàng)式，最高次累為n(i)+1

tic；

pl(i)=polyval(a,x)；%直接代入法

tl(i)=toc；

tic；

p2(i)=0；

forj=1：(n(i)+1)

p2(i)=p2(i)+a(j)*xx(j-1);%遞歸法1

end

t2(i)=toc；

tic；

p3(i)=0;

q=l；

forj=2：(n(i)+1)

q=q*x；

p3(i)=p3(i)+a(j)*q；%遞歸法2

end

t3(i)=toc；

tic；

p4(i)=0;

forj=1：n(i)；

p4(i)=x*p4(i)+a(n(i)+l-j)；%遞歸法3

end

t4(i)=toc；

end

figure(1)；

subplot(2,2,1)；

h=semilogx(n,tl)；%這里不能用plot,橫軸需要取對(duì)數(shù)，下同

set(hz'linestylelinewidth'z1.8z'marker','*','color','g','marke

rsize'z6)；

xlabel('Thescaleoftheproblem：n')；

ylabel('timeforfirstmethod(s)1)；

title('therelationshipbetweentimeandscale')；

gridon；

subplot(2,2,2)；

h=semilogx(nzt2)；

1

set(hz'linestylelinewidth'z1.8z'marker',*','color','b','marke

rsize'z6)；

xlabel('Thescaleoftheproblem：n')；

ylabel('timeforsecondmethod(s)')；

title('therelationshipbetweentimeandscale')；

gridon；

subplot(2,2,3)；

h=semilogx(nzt2)；

set(hz'linestylelinewidth'z1.8z'marker','*','color','k','marke

rsize'z6)；

xlabel('Thescaleoftheproblem：n')；

ylabel('timeforthirdmethod(s)1)；

title('therelationshipbetweentimeandscale')；

gridon；

subplot(2,2,4)；

h=semilogx(nzt2)；

111

set(hz'linestyle',-','linewidth,1.8,'markercolor','r',marke

rsize'z6)；

xlabel('Thescaleoftheproblem：n')；

ylabel('timeforforthmethod(s)')；

title('therelationshipbetweentimeandscale')；

gridon；

figure(2)；

1

g=semilogx(nztl,'bx',n,t3,k*',11^4,'ro')；

legend('thefirstmethod','thesecondmethod','thethirdmethod','the

forthmethod')；

set(gz'linestylelinewidth'z2.0z'markersize'z8)；

xlabel('n=10z50,100,150,200,300z400,500,10000,20000,50000,

100000');

ylabel('time')；

title('Thecomparisonchartoffourdifferentmethodsforpolyval')；

gridon；

運(yùn)行結(jié)果如下:

therelationshipbetweentimeandscale

101102103104105

Thescaleoftheproblems

圖1.1四種方法所用時(shí)間隨規(guī)模不同而變化的結(jié)果圖

圖2.2四種方法所用時(shí)間隨規(guī)模不同而變化的對(duì)比圖

由理論分析可知，四種算法的時(shí)間復(fù)雜度分別為0(r)、。(〃2)、o(〃)、o(〃)，由

圖1.2分析可知，直接帶入計(jì)算和遞歸法所用時(shí)間相差無(wú)幾，這與理論分析一直。而第三種

方法與第四種方法的差異可能是由于每次加法所用時(shí)間與每次乘法所用時(shí)間不同所導(dǎo)致。

另外，在問(wèn)題規(guī)模較小(n<1000)時(shí)，在圖上幾乎看不出區(qū)別，更精細(xì)的分析需要更深入

地討論，本文不做討論。

2、分析題意可知，要利用四種方法計(jì)算矩陣相乘，每種方法取矩陣大小從2ZX22~

212X212不同的規(guī)模。本文采用了以下方法進(jìn)行求值:矩陣計(jì)算法、定義法、分治法和Strassen

方法。

詳細(xì)程序如下：

程序2.1文件名matrix.m

%比較三種算法的運(yùn)行時(shí)間與MATLAB自帶的矩陣相乘的運(yùn)行時(shí)間

clc；

closeall；

clearall；

n=[2X22人32人42人52人62人72人82人92人102^112人工2];

form=l：11

A=round(rand(n(m)))；%隨機(jī)生成矩陣

B=round(rand(n(m)))；

tic；

C1=A*B;%MATLAB自帶的矩陣相乘

tl(m)=toc；

tic；

C2=zeros(n(m))；

fori=l：n(m)

fork=l：n(m)

forj=1：n(m)

C2(i,j)=C2(i,j)+A(i,k)*B(k,j);%按照定義進(jìn)行計(jì)算

end

end

end

t2(m)=toc；

All=A(l：n(m)/2zl：n(m)/2)；

A12=A(1：n(m)/2,n(m)/2+1：n(m))；

A21=A(n(m)/2+l：n(m),l：n(m)/2)；

A22=A(n(m)/2+1:n(m),n(m)/2+1：n(m))；

Bll=B(l：n(m)/2zl：n(m)/2)；

B12=B(1：n(m)/2,n(m)/2+1：n(m))；

B21=B(n(m)/2+l：n(m),l：n(m)/2)；

B22=B(n(m)/2+1:n(m)zn(m)/2+1：n(m))；

tic;

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=[CllC12;C21C22];

t3(m)=toc;

tic;

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=[CllC12;C21C22];

t4(m)=toc;

end

figure(1)；

subplot(2,2,1)；

h=semilogx(nztl)；%這里不能用plot,橫軸需要取對(duì)數(shù)，下同

set(hz'linestylelinewidth',1.8,'marker','*','color','marke

rsize'z6)；

xlabel('Thescaleofthematrix：n')；

ylabel('timeforfirstmethod(s)')；

title('therelationshipbetweentimeandscale')；

gridon；

subplot(2,2,2)；

h=semilogx(nzt2)；

1

set(hz'linestyle',-','linewidth',1.8,'marker','*','color','marke

rsize'z6)；

xlabel('Thescaleofthematrix：n')；

ylabel('timeforsecondmethod(s)')；

title('therelationshipbetweentimeandscale')；

gridon；

subplot(2,2,3)；

h=semilogx(nzt2)；

set(hz'linestylelinewidth',1.8,'marker','*','color','k','marke

rsize'z6)；

xlabel('Thescaleofthematrix：n')；

ylabel('timeforthirdmethod(s)')；

title('therelationshipbetweentimeandscale')；

gridon；

subplot(2,2,4)；

h=semilogx(nzt2)；

1

set(hz'linestyle',-','linewidth',1.8,'marker','*','color','r','marke

rsize'z6)；

xlabel('Thescaleofthematrix：n')；

ylabel('timeforforthmethod(s)')；

title('therelationshipbetweentimeandscale')；

gridon；

figure(2)；

1

g=semilogx(nztlzg+',n,t2,'bx',n,t3,'k*'znzt4,'ro')；

legend('theMATLABmethod','thedefinitionmethod','分治法','theStrassen

method')；

11

set(gz'linestyle'z'-z'linewidth',2.0zmarkersize'z8)；

xlabel('n=2^22人32人42人52人62人72人82人92人102^112^12');

ylabel('time')；

title('Thecomparisonchartoffourdifferentmethodsformatrix

multiplication')；

gridon；

實(shí)驗(yàn)結(jié)果如下:

圖2.1四種方法所用時(shí)間隨規(guī)模不同而變化的結(jié)果圖

3、

方法1：將原函數(shù)取負(fù)，求-/（占,9）的最小值即得原函數(shù)的最大值。

程序采用MATLAB自帶的工具箱實(shí)現(xiàn)，程序如下：

程序3.1文件名main_function.m

%主程序：用遺傳算法求解帶約束二元函數(shù)的最大值

clc；

closeall；

clearall；

G=100;%進(jìn)化的代數(shù)

optionsOrigin=gaoptimset('Generation',G/2)；

[xzfval,reason,output,final_pop]=ga(@fun,2,optionsOrigin)；

optionsl=gaoptimset('Generation*,G/2,'InitialPopulation',final_popz'P

lotFcns',@gaplotbestf)；

[xzfval,reason,output,final_pop]=ga(@funz2,optionsl)；

Bestx=x

BestFval=fval

%子程序：帶約束的目標(biāo)函數(shù)

functionf=fun(x)

if(x(l)>12.1|(x(2)>5.8))

f=inf；

elseif(x(l)<-3.0|x(2)<4.1)

f=inf；

else

f=-(21.5+x(1)*sin(4*pi*x(1))+x(2)*sin(20*pi*x(2)))；

end

運(yùn)行后的結(jié)果:

Best:-38,7478Mean:Inf

-38.7

一???????????????????????????????-------------------

?Bestfitness

-38.705-?Meanfitness

-38.71-

-38.715-

g-38.72-

'-38.725-

￡-38.73-

-38.735-

-38.74-

-38.745-

???????????????????

-38.75----------1----------1----------1----------1----------1----------1----------1----------1----------1----------1

0510伯20253035404550

[Stop||Pause]Generation

Bestx=

11.61845.7273

BestFval=

-38.7478

從而可知原函數(shù)在(11.6184,5.7273)取得最大值38.7478。

方法2：按照遺傳算法的思路編程，程序如下：

程序3.2文件名main_function.m

%主程序：用遺傳算法求解帶約束二元函數(shù)的最大值

clc；

clearall；

closeall；

G=100;%進(jìn)化代數(shù)

N=80;%群體規(guī)模

pm=0.05;%變異概率

pc=0.8;%交叉概率

ulmax=12.1；ulmin=-3.0；%參數(shù)取值范圍

u2max=5.8；u2min=4.1；%參數(shù)取值范圍

L=10;%單個(gè)參數(shù)字串長(zhǎng)度，總編碼長(zhǎng)度2L

bval=round(rand(N,2*L));%隨機(jī)產(chǎn)生初始種群

bestv=-inf；%最優(yōu)適應(yīng)度初值

fori=l：N

yl=0；y2=0；

forj=1：1：L

yl=yl+bval(i,L-j+l)*2^(j-l)；

end

xl=(ulmax-ulmin)*yl/(2AL-1)+ulmin；

forj=1：1：L

X

y2=y2+bval(iz2*L-j+l)*2(j-1);

end

x2=(u2max-u2min)*y2/(2AL-1)+u2min；

fun(i)=21.5+xl*sin(4*pi*xl)+x2*sin(20*pi*x2)；%目標(biāo)函數(shù)

xx(i,：)=[xlzx2]；

end

fitfun=fun；%目標(biāo)函數(shù)轉(zhuǎn)換為適應(yīng)度函數(shù)

p=fitfun./sum(fitfun)；%輪盤(pán)賭選擇函數(shù)

q=cumsum(p)；

[fmax,indmax]=max(fitfun)；%t己錄每——代最佳個(gè)體

iffmax>=bestv

bestv=fmax；%到目前為止最優(yōu)適應(yīng)度值

bvalxx=bval(indmax,：)；%到目前為止最佳位串

optxx=xx(indmax,：)；%到目前為止最優(yōu)參數(shù)

end

Bestfit(k)=bestv；%記錄每代的最優(yōu)適應(yīng)度

fori=l：(N-l)

r=rand；

tmp=find(r<=q)；

newbval(iz：)=bval(tmp(1),：)；