算法期末参考（Algorithm final reference）

算法期末参考(Algorithmfinalreference)

1.Divide-and-conquermethod:

**algorithmthinking**

**decomposesaproblemofsizenintoksmallersubproblems

thatareindependentandidenticaltotheoriginalproblem.

**solvethisksubproblemseparately.Ifthesizeofthe

subproblemisstillnotsmallenough,thenitcanbedivided

intoksubproblems,sotherecursiongoeson,untiltheproblem

issmallenoughtosolvetheproblem.

**thesolutionofthesmallscaleproblemwillbemergedinto

asolutionofalargerproblem,andthesolutionoftheoriginal

problemwillbeobtainedfromthebottomup.

Nonrecursivealgorithmforbinarysearch

PublicstaticintbinarySearch(inta口，intx,intn)

{//ina[0]<=a[1]<=...<=a[n-l]searchforxandreturn

itwhenxisfound

//inthearray,returns-1

Intleft=0;Intright=n-1;

While(left<=right){

Intmid=(left+right)/2;

If(x==a(mids))returnmid;//findreturnpositionmid?

If(x>(mids)a)left=mid+1;//narrowingtherange

Theelseright=mid-1;//narrowingtherange

)

Thereturn-1;//notfoundx

)

Recursivealgorithmforbinarysearch

Int?Binary(int?A[],int?Left,?Int?Right?Int?X)//

Binaryrecursivelookup

(

????Int?Mid?=?(left+right)/2;

????If?(left?>?Right?Thereturn?-1;//notfound????

????If?(a/mid?==?X)??Thereturn?Mid;//justfindit?

????Theelse?If?(a(mids)?>?X)?//smallerthanthemiddle

element,recursivelyfindtheleftarray

??????????Thereturn?Binary(a,left,?Mid-1,?X);

????Else??//largerthanthemiddleelement,recursivelyfind

therightarray

??????????Thereturn?Binary(a,+1,mid?Right?X);

)

2.Dynamicplanning:

**algorithmthinking**

**dynamicprogrammingalgorithmissimilartothe

divide-and-conquermethod,anditsbasicideaistodecompose

theproblemintoseveralsub-problems

Butthedecomposedsubproblemstendnottobeindependentof

eachother.Thenumberofdifferentsubproblemsisoftenonly

polynomials.Somesubproblemsarerepeatedsomanytimesthat

solvingtheoriginalproblemrequiresexponentialtime.

Ifyoucansavetheanswertoasolvedsubproblem,andthenfind

theanswerwhenyouneedit,youcanavoidalargenumberof

repeatedcomputationsandgetapolynomialtimealgorithm.

**

**basicelements**

**optimalsubstructure

**overlappingsubproblems

**memomethod

Matrixmultiplicationproblem

//p:thedimensionofarrayI:matrixchainstartingposition

j:matrixchainterminationposition

//r:matrixchainlengthk:matrixchaindisconnectlocation

s:recordoptimaldisconnectionposition

PublicstaticvoidmatrixChain(int[]p,int[][]m,int[]

口s)

{//computetheoptimumvalueofm[][][].

Intn=p.1ength-1;

For(intI=1;I<=n;I)[I][I][I][I][I][I][I][I][I]

[I][I][I][I][I][I][I]

For(intr=2;r<=n;r++)

For(int1=1;I<=n-r+l;I++){

Intj=I+r-1;

M[I][j]=m+1][I[j]+[]I-1p*p*p[I][j];

S[I][j]=I;

For(intk=I+l;k<j;k++){

Intt=m[I][k]+m[k+1][j]+p[I-1]*p[j].

If(t<m[I][j]){

M[I][j]=t;S[I][j]=k;}

)

)

)

//constructtheoptimalsolution

Publicstaticvoidtraceback(int[][]s,intI,intj)

{if(I==j)return;

Traceback(s,I,s[I][j]);

Traceback(s,s[I][j]+1,j);

System.Out.printin("MultiplyA"+I+”,"+s[I][j]+“and

A

[I][j]+(s)+1)+〃，〃+j);

Longestcommonsubsequenceproblem

AlgorithmIcsLength(x,y,b){//optimalvalue

//c[j]:thelengthoftheLCSforXiandYi

1:m=x.1ength-1;

2:n=y.1ength-1;

3:c[I][0]=0;C[0][I]=0;

For(int1=1;I<=m;I++)

5:for(intj=1;j<=n;j++)

6:theif(x==y[j][I])

7:[I][j]c=c[1][I-1]+1;

8:[I][j]b='\;

9:elseif(c[j][I-1]>=c[I][1])

10:[I][j]c=c[I-1)[j];

11:b[I][j]='write';

12:theelse

13:[I][j]c=c[I][1];

14:b[I][j]='please';

15:}

AlgorithmLCS(intI,intj,char[]x,int[][]b)

{//constructthelongestcommonsubsequence

If(I=0|Ij=0)return;

If(b[I][j]=='、){

TheLCS(I-1,j-1,x,b);\\theLCS(xi,yj)=theLCS

(yj-xi-1,1)+xi

System.Theout.Print(x[I]);

)

Elseif(b[I][j]=='write')

TheLCS(I-1,j,x,b);\\theLCS(xi,yj)=theLCS(xi

-1,yj)

Theelse

TheLCS(I,j-1,x,b);\\theLCS(xi,yj)=theLCS(xi,

yj-1)

0-lknapsackproblem

//theoptimalvalue

Publicstaticvoidknapsack(int[]v,int[]w,intc,int[]

[]m)

{intn=v.1ength-1;

IntjMax=Math.Min(w[n]1,c);//thecapacityofabackpack

thatcannotbeloadedincurrentnitems

For(intj=0;j<=jMax;j++)//backpackcapacityisless

thanwn

M[n][j]=0;

For([n].Intj=wj<=c;

Mj++)[n][j][n]=v;//loadwn

For(intI=n-1;I>1;I一){

JMax=Math.Min(w[I]1,c);//thecriticalvaluethatwi

cannotload

For(intj=0;j<=jMaxj++)m[I][j]=m+1][I[j];/

/j<wi,cannotbeloaded

For(intj=w[I];j<=c;++)//userecursiontodefine

theoptimalvaluefromthebottomup

M[I][j]=Math.Max(m+1][I[j],m[I+1,jw.[I]]+v

[I])；}

M[1][2][c]=m[c];//calculatem[1]c][0..

If(c>=w[1])

M[1],[c]=math,hMax(m[1],[c]m[2],[[1]]c-w+v[1]).

)

//constructtheoptimalsolution

Publicstaticvoidtraceback(int[]m,int[]w,intc,int

[]x)

(

Intn=w.ength-1;//nisthenumberofitems

For(int1=1;I<n;i++)

If(m==[c][I]m[I+1)[c])x[I]=0;//unloadeditem

I

Theelse{

[I]x=1;//loaditemI

C-w=

)

[n]=x(m[n][c]>0?1-0);//lastitemn

)

3.Greedyalgorithm:

**algorithmthinking**

**greedyalgorithmalwaysmakesthebestchoiceatpresent.

Inotherwords,thegreedyalgorithmdoesn'ttaketheoverall

optimalconsideration,andthechoiceitmakesisonlythelocal

optimalchoiceinasense.Ofcourse,thefinalresultofthe

greedyalgorithmisalsotheoveralloptimal.

**

**basicelements**

**greedychoiceofnature

**optimalsubstructureproperty

Activityschedulingproblem

//S[]:thestartingtimeofeachactivity

//f口:theendtimeofeachactivityandthenon-decreasing

orderoftheendtime

//a[]:thecollectionofselectedactivities

PublicstaticintgreedySelector(int[]s,int[]f,Boolean

[]a)

(

Intn=s.1ength-1;

A[1]=true;

Intj=1;

Intcount=1;

For(int1=2;I<=ni++){

If(s[I]>=f[j]){//ifthestarttimeoftheactivityI

wascheckedislessthantheendtimeoftherecentlyselected

activityj,

//donotselectactivityI,otherwiseselectactivityIto

joinA.

A[I]=true;

J=I；

Count++;

Elsea[I]=false;

)

Returnthecount.

)

Multi-machineschedulingproblem

Publicstaticintgreedy(int[]a,intm){

Intn=a.ength-1,sum=0;

If(n<m){

For(int1=0;I<ni++)sum+=a,[I].

("assignamachinetoeachassignment.")

Returnthesum.

JobNode[]d=newJobNode[n].

For(int1=0;I<n;I++)//initializethejobarray

D[I]=newJobNode(I+1,a[I+1));

MergeSort.MergeSort(d);

//ascendingorderbytheprocessingtimeofthejob

For(int1=1;I<=m;I++){//machinenumberand

initialization,putintheheap

MachineNodex=newMachineNode(I,0).

H.put(x);

)

For(intI=n;I>=1;I一){//frombigtosmalltakeout

thejob

MachineNodex=(MachineNode)practiceemoveMin();

//selectthemachinewiththesmallesttotaltime

System.Out.Printin("themachinefrom"++x.idx.avail

+“to”+(x.avail+d[I-1].Time)+“timeassignedhomework

"+d[I-1].Id);

X.avail+=d[I-1].Thetime;//modifythestarttimeof

themachine'snextjob

Sum=x.avail;//jobcompletionrequiredprocessingtime

H.put(x);

Returnthesum.

)

Knapsackproblem

Publicstaticfloatknapsack(floatc,float[]w,float[]v,

float[]x)

(

Intn=v.1ength;

Element[]d=newElement[n];

For(int1=0;I<n;i++)d[I]=newElement(w[I],v[I],

I)；

MergeSort.MergeSort(d);//arrangeitemsbyVi/Wifrombig

tosmal1

IntI;Floatopt=0;

For(I=0;I<ni++)[I]x=0;

For(I=0;I<n;i++){

If(d[I].W>c)break;//thesparecapacityofthebackpack

isnotenoughtoputintotheitemI

[I]x[d]I=1;//loaditemI

[I].Opt+=dv.//loadthetotalvalueofitemI

C-=d[I].W;//loadtheremainingcapacityofthebackpack

afterloadingtheitemI

)

If(I<n){//lastcanonlyloadpartofitemI

[I]x[d]I=c/d[I],W.

Opt+=x*d/d[I].I[I].V.

)

Returnopt;//returnpackvalue

)

Minimumspanningtree(Prim,Kruskal)algorithmintroduction

p366

-thePrimalgorithm一

Publicstaticvoidprim(intn,float口[]c)

{float[]lowcost=newfloat[n+1);

Int[]closest=newint[n+1);

Boolean[]s=newBoolean[n+1);

S[1]=true;//vertex1isalreadyinthespanningtree,

belongingtothesetS

For(int1=2;I<=n;I++){//arraytheinitialvalue

oftheelement

Lowcost[I]=c[1][I];

Closest[I]=1;

S[I]=false;

)

For(int1=1;I<n;i++){

Thefloatmin=float.MAX_VALUE;

Intj=1;

For(intk=2;k<=n;k++)//searchweightminimumedge

(I,j)

If((lowcost[k]<min)&&(!S[k])){

Min=lowcost[k].J=k;}

System.Theout.Printin(j+”,"+closest[j]);//output

theedgeofthetree

S[j]=true;//addvertexjtosetS

For(intk=2k<=nk++)

//Sjoinsthevertexjandreselectsthesmallestside

If((c[j][k])<lowcost[k])&&(!S[k])){

Lowcost[k][j][k]=c;

Closest[k]=j;

)

)

)

-kruskalalgorithm一

Publicstatickruskal(intn,inte,EdgeNode[]e,EdgeNode

[]t)

{MinHeapH=newMinHeap(1);

H.initialize(E,E);//initializeheap

FastUnionFindU=newFastUnionFind(n);

Intk=0;

While(>0e&k<n-l){

EdgeNodex=(EdgeNode)practiceemoveMin();//selectthe

minimumedge

E一;

Inta=U.find(x.u);//returntoUcontainsthenameofthe

connectedcomponentofvertexU

Intb=U.find(x.v);//returnUcontainsthenameofthe

connectedcomponentofthevertexv

If(a!=b){//ifu,vdoesnotbelongtothesameconnected

component

T[k++]=x;

U.unoin(a,b);//tocombineaandbintoaconnectedcomponent

Return(k==n-1);

4.Retrospectivemethod:

**algorithmthinking**

**

Afterdeterminingtheorganizationalstructureofthespace,

theretrospectivemethodstartsfromthebeginningnode(root)

andsearchestheentiresolutionspaceinadeepfirstway.

Thisstartingnodeisknownasthenodeofthenode,andit

becomesthecurrentextensionnode.

Atthecurrentextensionnode,thesearchmovestoanewnode

inthedeepdirection.Thisnewnodebecomesthenewnode,and

becomesthecurrentextensionnode.

Ifyoucantmoveinthedeeperdirectionatthecurrent

extensionpoint,thecurrentextensionnodebecomesadeadlock

point.Atthispoint,youshouldmoveback(back)tothenearest

1ivingnodeandmakethenodeacurrentextensionnode.

Theretrospectivemethodisrecursivelysearchedinthe

solutionspaceuntilthedesiredsolutionorsolutionspacehas

noactivejunction.

**

Afternproblem

PublicclassNQueenl{

Staticintn;

Staticint[]x;

Thestaticlongsum;

PublicstaticlongnQueen(intnn){

N=nn;

Sum=0;

X=newint[n+1);

For(int1=0;I<=ni++)[I]x=0;

Backtrack(1);

Returnthesum.

)

PrivatestaticBooleanplace(intk)

(

For(intj=1;j<k;j++)

//checkthepositionx[j]ofthepreviousk-1rowqueenhas

beenplaced

//thepositionoftheKTHqueen

If((Math.Abs(k-j)==math,habs(x[j]-[k]x))//k,

j,onthesamediagonallines

(x[j]==x[k]))//k,jisonthesamecolumn

Returnfalse;

Returntrue;

)

Privatestaticvoidbacktrack(intt)

{

If(t>n)sum++;

Theelse

For(int1=1;I<=ni++){

X[t]=I;

If(place(t))backtrack(t+1);

Travelsalesmanproblem

Privatestaticvoidbacktrack(intI){

If(I==n){//thecurrentextensionnodeistheparentof

theleafofthetree

If(a[x][n-1][n][x]<Float.MAX_VALUE&&//vertices

havebetweennandn-1

A[x[n]][1]<Float.MAXJVALUE||//vertexnto1hasedges

Cc+a[x][n-1][n]],[x+a[n][x][1]<bestc)){

For(intj=1;j<=nj++)bestx[j]=x[j];//gettheoptimal

solution

Bestc=cc+a[x][n-1]+[n][x]a[n][x][1].//getthe

optimalvalue

)

)

Else{//I<n,thecurrentextensionnodeisinthei-1layer

For(intj=I;j<=n;j++)//searchallsubtreesofthe

ithlayer

//canIenterthex[j]subtree?

If(a[x][I-1][j][x]<Float.MAX_VALUE&&

(bestc==Float.MAX_VALUE||cc+a[x][I-1][j][x]<

bestc))

{//searchsubtree

MyMath.Swap(x,I,j);//exchangex[I],x[j]

Cc+=a[x][I-1][I]Ex];

Backtrack(I+1);//enterthenextlayeroftree

Cc-=a[x][I-1][I][x];//restorethevalueofcc

MyMath.Swap(x,I,j);//restorex[I],x[j]

5.Branchlimitmethod:

**algorithmthinking**

**

Thebranchlimitlawoftensearchesforthesolutionspacetree

intermsofbreadthfirstorintermsoftheminimumcost

(maximumbenefit).

Inthebranchboundedmethod,eachnodehasonlyonechanceto

becomeanextensionnode.Oncethenodebecomesanextension

node,itproducesallitssonsatonce.Inthesesons,thechild

nodethatcausesanunfeasiblesolutionorleadstoa

non-optimalsolutionisabandoned,andtheremainingchildren

areaddedtotheactivejunctiontable.

Afterthat,thenodebecomesthecurrentextensionnodefrom

thenodetable,andtheextensionprocessofthenodeis

repeated.Thisprocesscontinuesuntilyoufindthedesired

solutionortheactivitypointtableisempty.

**

**

Thebranchlimitingmethodisdifferentfromthebacktracking

method

:(1)targetofbacktrackingmethodisusedtosolvethegoal

istofindallsolutionssatisfytheconstraintconditionsin

thesolutionspacetree,whilethebranchthresholdmethodis

usedtosolvethetargetistofindmeettheconstraintsofa

solution,orsatisfytheconstraintconditionsofsolutionto

findouttheoptimalsolutionofinsomesense.

(2)differentwaysofsearching:theretrospectivemethod

searchesforthesolutionspacetreeinadepthfirstway,while

thebranchlimitrulesearchesforthesolutionspacetreein

breadthfirstorintheleastexpensiveway.

**

Singlesourceshortestpathproblem

PublicclassBBShortest{

StaticclassHeapNodeforexample

IntI;

Thefloatlength;

HeapNode(intii,float11){

I=2;

Length=11;

)

PublicintcompareTo(Objectx){

Floatxl=((HeapNode)x.)length;

If(length(xl)return1;

If(length==xl)return0;