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

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

大作業(yè)

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

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

姓名________________________________

學(xué)號________________________________

導(dǎo)師姓名

作業(yè)

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

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

時繪制四種算法運行時間的比較圖。

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

25X25,26X26,27X27,28x28,29x29,210x210,2nx2u,時的運行時

間與MATLAB自帶的矩陣相乘的運行時間，繪制時間對比圖。

3.利用遺傳算法求解下面的問題:

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、分析題意可知，該題要用四種不同的方法實現(xiàn)對多項式的求值計算，每種方法取從

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

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

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

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

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

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

程序1.1文件名poly.m

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

clc；

closeall；

clearall；

n=[1050100150200300400500100002000050000100000];

x=2;

fori=l：12

a=rand(l,(n(i)+1))；%產(chǎn)生多項式，最高次累為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,橫軸需要取對數(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；

運行結(jié)果如下:

therelationshipbetweentimeandscale

101102103104105

Thescaleoftheproblems

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

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

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

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

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

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

地討論，本文不做討論。

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

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

方法。

詳細(xì)程序如下：

程序2.1文件名matrix.m

%比較三種算法的運行時間與MATLAB自帶的矩陣相乘的運行時間

clc；

closeall；

clearall；

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

form=l：11

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

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)行計算

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,橫軸需要取對數(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；

實驗結(jié)果如下:

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

3、

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

程序采用MATLAB自帶的工具箱實現(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

運行后的結(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;%單個參數(shù)字串長度，總編碼長度2L

bval=round(rand(N,2*L));%隨機產(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)；%輪盤賭選擇函數(shù)

q=cumsum(p)；

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

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),：)；