-.z.算法分析與設(shè)計2013~2014年度第1學(xué)期課程學(xué)習(xí)報告院系： **：：任課教師：成績評定：完成日期：2013年12月30日遞歸與分治在任何可以用計算機(jī)求解的問題所需的計算時間都與其規(guī)模有關(guān)。問題的規(guī)模越小，解題所需要的計算時間也就越少從而比擬容易處理。要想直接解決一個較大的問題，有時是相當(dāng)困難的。分治法的設(shè)計思想是，講一個難以解決的大問題，分割成規(guī)模較小的一樣問題，以便各個擊破，分而治之。如果原問題可分割成k個子問題，1＜k≤n，且這些子問題都可解，并可利用這些子問題的解求出原問題的解，則這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分之手段，可以使子問題與原問題的類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易求出其解。由此自然導(dǎo)出遞歸算法。并以其為根底，可以產(chǎn)生了許多高效算法。1.1遞歸的概念直接或間接的調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。在計算機(jī)算法設(shè)計與分析中，遞歸技術(shù)是十分有用的。使用遞歸技術(shù)往往使函數(shù)的定義和算法的描述簡潔且易于理解。1.1.1整數(shù)劃分問題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個數(shù)。例如正整數(shù)6有如下11種不同的劃分：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個自變量：將最大加數(shù)n1不大于m的劃分個數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。(1)q(n,1)=1,n1;當(dāng)最大加數(shù)n1不大于1時，任何正整數(shù)n只有一種劃分形式，即(2)q(n,m)=q(n,n),m≥n;最大加數(shù)n1實(shí)際上不能大于n。因此，q(1,m)=1。(3)q(n,n)=1+q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1≤n-1的劃分組成。(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1≤n-1的劃分組成。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個自變量：將最大加數(shù)n1不大于m的劃分個數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。據(jù)此，設(shè)計計算去q〔n，m〕的遞歸算法如下。publicstaticintq(intn,intm){if((n<1)||(m<1))return0;if((n==1)||(m==1))return1;if(n<m)returnq(n,n);If(n==m)returnq(n,m-1)+1;returnq(n,m-1)+q(n-m,m);}1.1.2遞歸小結(jié)優(yōu)點(diǎn)：構(gòu)造清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論是消耗的計算時間還是占用的存儲空間都比非遞歸算法要多。1.2分治法的根本思想分治法的根本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題一樣。人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致一樣。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。1.2.1分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為假設(shè)干個規(guī)模較小的一樣問題，即該問題具有最優(yōu)子構(gòu)造性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。這條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。分治法的根本步驟divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解決小規(guī)模的問題dividePintosmallersubinstancesP1,P2,...,Pk；//分解問題for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//遞歸的解各子問題returnmerge(y1,...,yk);//將各子問題的解合并為原問題的解}人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致一樣。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。1.3問題描述在一個2^k×2^k〔k≥0〕個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為特殊方格。顯然，特殊方格在棋盤中可能出現(xiàn)的位置有4^k種，因而有4k種不同的棋盤，所示是k=2時16種棋盤中的一個。棋盤覆蓋問題〔chesscoverproblem〕要求用4種不同形狀的L型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。當(dāng)k>0時，將2k×2k棋盤分割為4個2k-1×2k-1子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如(b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。用遞歸與分治求解下面算法中，用整數(shù)型數(shù)組board表示棋盤。board[0][0]是棋盤的左上角方格。tile是算法中的一個全局整形變量，用來表示L型骨牌的編號，其初始值為0.算法的輸入?yún)?shù)如下：tr：棋盤左上角方格的行號；tc：棋盤左上角方格的列號；dr：特殊方格所在的行號；size：，棋盤規(guī)格為2^k×2^k。設(shè)T(k)是算法chessBoard覆蓋一個2^k×2^k棋盤所需要的時間。從算法的分割策略可知，T〔k〕滿足如下遞歸方程解此遞歸方程可得T(K)=O()。由于覆蓋2^k×2^k棋盤所需要的L型骨牌個數(shù)為〔〕/3，故此算法是一個在漸進(jìn)意義下最優(yōu)的算法。程序代碼如下所示：publicvoidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌號s=size/2;//分割棋盤//覆蓋左上角子棋盤if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盤中chessBoard(tr,tc,dr,dc,s);else{//此棋盤中無特殊方格//用t號L型骨牌覆蓋右下角board[tr+s-1][tc+s-1]=t;//覆蓋其余方格chessBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆蓋右上角子棋盤if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盤中chessBoard(tr,tc+s,dr,dc,s);else{//此棋盤中無特殊方格//用t號L型骨牌覆蓋左下角board[tr+s-1][tc+s]=t;//覆蓋其余方格chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆蓋左下角子棋盤if(dr>=tr+s&&dc<tc+s)//特殊方格在此棋盤中chessBoard(tr+s,tc,dr,dc,s);else{//用t號L型骨牌覆蓋右上角board[tr+s][tc+s-1]=t;//覆蓋其余方格chessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆蓋右下角子棋盤if(dr>=tr+s&&dc>=tc+s)//特殊方格在此棋盤中chessBoard(tr+s,tc+s,dr,dc,s);else{//用t號L型骨牌覆蓋左上角board[tr+s][tc+s]=t;//覆蓋其余方格chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}1.4課后習(xí)題設(shè)有N個運(yùn)發(fā)動要進(jìn)展網(wǎng)球循環(huán)賽，設(shè)計一個滿足以下要求的比賽日程表〔1〕每個選手必須與其他n-1個選手各賽一次〔2〕每個選手一天只能賽一次〔3〕當(dāng)n是偶數(shù)，循環(huán)賽進(jìn)展n-1天，當(dāng)n是奇數(shù)，循環(huán)賽進(jìn)展n天分治策略：我們可以將所有的選手分為兩半，則n個選手的比賽日程表可以通過n/2個比賽日程表來決定。遞歸地用這種一分為二的策略對選手進(jìn)展劃分，直選手的到只剩下兩個選手時，比賽日程表的制定就變得很簡單。這時只要讓這兩個選手進(jìn)展比賽就可以了。按分治策略，我們可以將所有的選手分為兩半，則n個選手的比賽日程表可以通過n/2個選手的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進(jìn)展劃分，直到只剩下兩個選手時，比賽日程表的制定就變得很簡單。這時只要讓這兩個選手進(jìn)展比賽就可以了。代碼局部#include<stdlib.h>#include<stdio.h>int**A;//int*指針數(shù)組，int*schedule;//int數(shù)組，一維數(shù)組保存二維數(shù)組的數(shù)據(jù)intN=1;//問題的規(guī)模。初始化時會設(shè)定//isodd:判斷*是否奇數(shù)，是則返回1，否則0intisodd(int*){return*&1;}//print:打印賽程voidprint(){inti,j,row,col;if(isodd(N)){row=N;col=N+1;}else{row=N;col=N;}printf("第1列是選手編號\n");for(i=0;i<row;i++){for(j=0;j<col;j++){printf("%4d",A[i][j]);}printf("\n");}}/*init：初始化，設(shè)置問題規(guī)模N值，分配內(nèi)存，用schedule指向；把A構(gòu)造成一個二維數(shù)組*/voidinit(){inti,n;charline[100]={'\0'};printf("請輸入選手人數(shù)：");fgets(line,sizeof(line),stdin);N=atoi(line);if(N<=0)e*it(-1);if(isodd(N))n=N+1;elsen=N;//schedule是行化的二維數(shù)組schedule=(int*)calloc(n*n,sizeof(int));A=(int**)calloc(n,sizeof(int*));if(!schedule||A==NULL)e*it(-2);for(i=0;i<n;i++)//把A等價為二維數(shù)組{A[i]=schedule+i*n;A[i][0]=i+1;//初始化這個數(shù)組的第一列}return;}/*replaceVirtual:把第m號虛的選手去掉〔換做0〕*/voidreplaceVirtual(intm){inti,j;for(i=0;i<m-1;i++)//行：對應(yīng)選手號1～m-1{for(j=0;j<=m;j++)//列:比行要多1A[i][j]=(A[i][j]==m)"0:A[i][j];}return;}/*copyeven:m為偶數(shù)時用,由前1組的m位選手的安排，來構(gòu)成第2組m位選手的賽程安排，以及兩組之間的比賽安排*/voidcopyeven(intm){if(isodd(m))return;inti,j;for(j=0;j<m;j++)//1.求第2組的安排〔+m〕{for(i=0;i<m;i++){A[i+m][j]=A[i][j]+m;}}for(j=m;j<2*m;j++)//兩組間比賽的安排{for(i=0;i<m;i++)//2.第1組和第2組{A[i][j]=A[i+m][j-m];//把左下角拷貝到右上角}for(i=m;i<2*m;i++)//3.對應(yīng)的，第2組和第1組{A[i][j]=A[i-m][j-m];//把左上角拷貝到右下角}}return;}/*copyodd:m為奇數(shù)時用,由前1組的m位選手的安排，來構(gòu)成第2組m位選手的賽程安排，以及兩組之間的比賽安排。這時和m為偶數(shù)時的處理有區(qū)別。*/voidcopyodd(intm){inti,j;for(j=0;j<=m;j++)//1.求第2組的安排(前m天){for(i=0;i<m;i++)//行{if(A[i][j]!=0){A[i+m][j]=A[i][j]+m;}else//特殊處理：兩個隊(duì)各有一名選手有空，安排他們比賽{A[i+m][j]=i+1;A[i][j]=i+m+1;}}}///////////安排兩組選手之間的比賽(后m-1天)////////////////////////for(i=0,j=m+1;j<2*m;j++){A[i][j]=j+1;//2.1號選手的后m-1天比賽A[(A[i][j]-1)][j]=i+1;//3.他的對手后m-1天的安排}//以下的取值要依賴于1號選手的安排，所以之前先安排1號的賽程for(i=1;i<m;i++)//第1組的其他選手的后m-1天的安排{for(j=m+1;j<2*m;j++){//2.觀察得到的規(guī)則一：向下m+1~2*m循環(huán)遞增A[i][j]=((A[i-1][j]+1)%m==0)"A[i-1][j]+1:m+(A[i-1][j]+1)%m;//3.對應(yīng)第2組的對手也要做相應(yīng)的安排A[(A[i][j]-1)][j]=i+1;}}return;}/*makecopy:當(dāng)前有m位〔偶數(shù)〕選手，分成兩組，每組由m/2位選手構(gòu)成由第一組的m/2位選手的安排來構(gòu)成第二組的比賽安排，第一組與第二組的比賽安排。要區(qū)分m/2為奇數(shù)和偶數(shù)兩種情況*/voidmakecopy(intm){if(isodd(m/2))//m/2為奇數(shù)copyodd(m/2);else//m/2為偶數(shù)copyeven(m/2);}voidtournament(intm){if(m==1){A[0][0]=1;return;}elseif(isodd(m))//如果m為奇數(shù)，則m+1是偶數(shù){tournament(m+1);//按照偶數(shù)個選手來求解replaceVirtual(m+1);//然后把第m+1號虛選手置成0return;}else//m是偶數(shù)，{tournament(m/2);//則先安排第1組的m/2人比賽makecopy(m);//然后根據(jù)算法，構(gòu)造左下、右下、右上、右下的矩陣}return;}/*endprogram:回收分配的內(nèi)存*/voidendprogram(){free(schedule);free(A);}intmain(){init();//初始化tournament(N);//求解print();//打印結(jié)果endprogram();//回收內(nèi)存return0;}動態(tài)規(guī)劃動態(tài)規(guī)劃算法與分治法類似，其根本思想是將待求解問題分解成假設(shè)干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的，假設(shè)用分治法解這類問題，則分解得到的子問題數(shù)目太多，以至于最后解決原問題需要消耗過多的時間。在用分治法求解時，有些子問題被重復(fù)計算了許屢次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以防止大量的重復(fù)計算。為了到達(dá)此目的，可以用一個表來記錄所有已解決的子問題的答案。這就是動態(tài)規(guī)劃法的根本思想。2.1動態(tài)規(guī)劃算法的根本要素2.1.1最優(yōu)子構(gòu)造矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子構(gòu)造性質(zhì)。在分析問題的最優(yōu)子構(gòu)造性質(zhì)時，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。利用問題的最優(yōu)子構(gòu)造性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。最優(yōu)子構(gòu)造是問題能用動態(tài)規(guī)劃算法求解的前提。2.1.2重疊子問題遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算屢次。這種性質(zhì)稱為子問題的重疊性質(zhì)。動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。通常不同的子問題個數(shù)隨問題的大小呈多項(xiàng)式增長。因此用動態(tài)規(guī)劃算法只需要多項(xiàng)式時間，從而獲得較高的解題效率。2.2實(shí)例分析2.2.1計算最優(yōu)值對于1≤i≤j≤n不同的有序?qū)?i,j)對應(yīng)于不同的子問題。因此，不同子問題的個數(shù)最多只有由此可見，在遞歸計算時，許多子問題被重復(fù)計算屢次。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)展計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而防止大量的重復(fù)計算，最終得到多項(xiàng)式時間的算法。用動態(tài)規(guī)劃法求最優(yōu)解publicstaticvoidmatri*Chain(int[]p,int[][]m,int[][]s){intn=p.length-1;for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)for(inti=1;i<=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}2.2.20-1背包問題給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包中物品，使得裝入背包中物品的總價值最大？設(shè)(y1,y2,...,yn)是所給0-1背包問題的一個最優(yōu)解，則(y2,y3,...,yn)是經(jīng)過一次選擇后的0-1背包問題的最優(yōu)解。0-1背包問題的遞歸關(guān)系，設(shè)當(dāng)前子問題的最優(yōu)值為m(i,j)，即m(i,j)是背包容量為j，可選擇物品為i,i+1,...,n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子構(gòu)造性質(zhì)，可以建立計算m(i,j)的遞歸式：當(dāng)i=n時，假設(shè)j>=wn，則m(i,j)=vn；假設(shè)0<=j<wn，則m(i,j)=0。當(dāng)i<n時，假設(shè)j>=wi，則m(i,j)=ma*{m(i+1,j),m(i+1,j-wi)+vi}；假設(shè)0<=j<wi，則m(i,j)=m(i+1,j)。程序代碼如下:importjava*.swing.*;publicclassKnapsacke*tendsJFrame{finalJScrollPanescrollPane=newJScrollPane();publicstaticJTe*tArearesultte*tArea;publicJLabell1=newJLabel("最優(yōu)解");publicJLabell3=newJLabel("所用時間");publicstaticJTe*tFieldt1=newJTe*tField();publicstaticJTe*tFieldt2=newJTe*tField();finalJLabellabel=newJLabel();finalJLabellabel_1=newJLabel();publicKnapsack(){this.setResizable(false);this.setTitle("動態(tài)規(guī)劃計算0-1背包");this.getContentPane().setLayout(null);this.setBounds(100,100,670,400);this.setDefaultCloseOperation(JFrame.E*IT_ON_CLOSE);scrollPane.setBounds(190,25,454,293);getContentPane().add(scrollPane);resultte*tArea=newJTe*tArea();resultte*tArea.setEditable(false);scrollPane.setViewportView(resultte*tArea);label.setHorizontalTe*tPosition(SwingConstants.RIGHT);label.setHorizontalAlignment(SwingConstants.RIGHT);label.setTe*t("最優(yōu)解：");label.setBounds(10,42,66,18);getContentPane().add(label);t1.setHorizontalAlignment(SwingConstants.RIGHT);t1.setHorizontalAlignment(SwingConstants.RIGHT);t1.setBounds(80,42,66,18);getContentPane().add(t1);label_1.setHorizontalTe*tPosition(SwingConstants.RIGHT);label_1.setHorizontalAlignment(SwingConstants.RIGHT);label_1.setTe*t("所用時間：");label_1.setBounds(10,75,66,18);getContentPane().add(label_1);t2.setHorizontalAlignment(SwingConstants.RIGHT);t2.setHorizontalAlignment(SwingConstants.RIGHT);t2.setBounds(80,75,66,18);getContentPane().add(t2);}voiddisplay(int[]v,int[]w,intc,intn,int[][]m){intjMa*=Math.min(w[n-1]-1,c);for(intj=0;j<=jMa*;j++){ m[n][j]=0; }//初始化for(intj=w[n-1];j<c;j++){ m[n][j]=v[n]; }for(inti=n-1;i>0;i--){ jMa*=Math.min(w[i]-1,c);for(intj=0;j<=jMa*;j++){ m[i][j]=m[i+1][j]; }for(intj=w[i];j<c;j++){ m[i][j]=Math.ma*(m[i+1][j],m[i+1][j-w[i]]+v[i]); } } System.out.println("出來的循環(huán)m[0][c-1]:"+m[0][c-1]); System.out.println("出來的循環(huán)m[1][c-1]:"+m[0][c-1]);m[0][c-1]=m[1][c-1];if(c>=w[0]){ m[0][c-1]=Math.ma*(m[0][c-1],m[1][c-w[0]]+v[0]); } System.out.println("------------------------------------------"); System.out.println("此0-1背包問題的最優(yōu)解為："+m[0][c-1]); System.out.println("物品的選擇〔‘0’代表沒有選擇，‘1’代表選擇〕如下：");System.out.println("------------------------------------------");t1.setTe*t(""+m[0][c-1]);}voidtaceback(int[]w,intc,intn,int[][]m,int[]*){resultte*tArea.append("物品的選擇〔‘0’代表沒有選擇，‘1’代表選擇〕如下：/n");for(inti=0;i<n;i++){if(m[i][c-1]==m[i+1][c-1])*[i]=0;else{ *[i]=1; c-=w[i]; } System.out.println("*["+i+"]="+*[i]);resultte*tArea.append("*["+i+"]="+*[i]+"/n");}if(m[n-1][c-1]==1)*[n-1]=1;else*[n-1]=0; System.out.println("*["+n+"]="+*[n-1]);resultte*tArea.append("*["+n+"]="+*[n-1]+"/n"); System.out.println("------------------------------------------"); }publicstaticvoidmain(String[]args){finalintc=1000;finalintn=50;int[]v={220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1,1};int[]w={80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,1,1};int[][]m=newint[n][c];int[]*=newint[n];longstart=System.currentTimeMillis(); Knapsackk=newKnapsack(); k.setVisible(true); k.display(v,w,c,n-1,m); k.taceback(w,c,n-1,m,*);longend=System.currentTimeMillis();t2.setTe*t((end-start)+"ms"); System.out.println("/nTimeconsuming:"+(end-start)); }}2.2.3石子合并

在一個圓形操場的四周擺放著n堆石子?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。

試設(shè)計一個算法，計算出將n堆石子合并成一堆的最小得分和最大得分。

輸入文件:包含兩行，第1行是正整數(shù)n〔1<=n<=100〕，表示有n堆石子。第2行有n個數(shù)，分別表示每堆石子的個數(shù)。輸出兩行。第1行中的數(shù)是最小得分；第2行中的數(shù)是最大得分。

動態(tài)規(guī)劃思路：

階段i：石子的每一次合并過程，先兩兩合并，再三三合并，...最后N堆合并

狀態(tài)s：每一階段中各個不同合并方法的石子合并總得分。

決策：把當(dāng)前階段的合并方法細(xì)分成前一階段已計算出的方法，選擇其中的最優(yōu)方案

具體來說我們應(yīng)該定義一個數(shù)組s[i,j]用來表示合并方法，i表示從編號為i的石頭開場合并，j表示從i開場數(shù)j堆進(jìn)展合并，s[i,j]為合并的最優(yōu)得分。

對于上面的例子來說，初始階段就是s[1,1],s[2,1],s[3,1],s[4,1],s[5,1],s[6,1]，因?yàn)橐婚_場還沒有合并，所以這些值應(yīng)該全部為0。

第二階段：兩兩合并過程如下，其中sum(i,j)表示從i開場數(shù)j個數(shù)的和

s[1,2]=s[1,1]+s[2,1]+sum(1,2)

s[2,2]=s[2,1]+s[3,1]+sum(2,2)

s[3,2]=s[3,1]+s[4,1]+sum(3,2)

s[4,2]=s[4,1]+s[5,1]+sum(4,2)

s[5,2]=s[5,1]+s[6,1]+sum(5,2)

s[6,2]=s[6,1]+s[1,1]+sum(6,2)

第三階段：三三合并可以拆成兩兩合并，拆分方法有兩種，前兩個為一組或后兩個為一組.

s[1,3]=s[1,2]+s[3,1]+sum(1,3)或s[1,3]=s[1,1]+s[2,2]+sum(1,3)，取其最優(yōu)

s[2,3]=s[2,2]+s[4,1]+sum(2,3)或s[1,3]=s[2,1]+s[3,2]+sum(2,3)，取其最優(yōu)

第四階段：四四合并的拆分方法用三種，同理求出三種分法的得分，取其最優(yōu)即可。以后第五階段、第六階段依次類推，最后在第六階段中找出最優(yōu)答案即可源程序#include"stdio.h"

#include"stdlib.h"

intnum[101];

ints[99][100];intsum(inti,intj,intn)//求和

{

intresult,final;

result=num[i];for(intp=1;p<=j-1;p++)

{

if(i+p>n)

final=(i+p)%n;

else

final=i+p;

result=result+num[final];

}

returnresult;

}intma*(intn)

{

intk,t,w,result;

for(inti=1;i<=n;i++)//初始階段就是s[1,1],s[2,1],s[3,1],s[4,1],s[5,1],s[6,1]，因?yàn)橐婚_場還沒有合并，所以這些值應(yīng)該全部為0

s[i][1]=0;

for(intr=2;r<=n;r++)//枚舉階段，從兩兩合并開場計算

for(i=1;i<=n;i++)//計算當(dāng)前階段的n種不同狀態(tài)的值,從一開場的1到n種不同狀態(tài)，例如s[1][n]和s[2][n]

{

if(i+1>n)

w=(i+1)%n;

else

w=i+1;

s[i][r]=s[i][1]+s[w][r-1]+sum(i,r,n);//s(i,r,n)表示從i開場數(shù)r個數(shù)的和

//m[i][r]=w;

for(k=1;k<=r-1;k++)//枚舉不同的分段方法

{

if(i+k>n)

w=(i+k)%n;

else

w=i+k;

t=s[i][k]+s[w][r-k]+sum(i,r,n);

if(t>s[i][r])//比擬取s[1...n][r]中的最值

{

s[i][r]=t;

//m[i][r]=k;

}

}

}

result=s[1][n];

for(intu=1;u<=n;u++)//從s[1][n]到s[n][n]中取最大值

{//printf("%d",s[u][n]);

if(s[u][n]>result)

result=s[u][n];

}

returnresult;

}

intmin(intn)//同ma*()差不多

{

intk,t,w,result;

for(inti=1;i<=n;i++)

s[i][1]=0;

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

for(i=1;i<=n;i++)

{

if(i+1>n)

w=(i+1)%n;

else

w=i+1;

s[i][r]=s[i][1]+s[w][r-1]+sum(i,r,n);

m[i][r]=w;

for(k=1;k<=r-1;k++)

{

if(i+k>n)

w=(i+k)%n;

else

w=i+k;

t=s[i][k]+s[w][r-k]+sum(i,r,n);

if(t<s[i][r])//比擬

{

s[i][r]=t;

m[i][r]=k;

}

}

}

result=s[1][n];

for(intu=1;u<=n;u++)//還是比擬，與ma*比擬不同

{//printf("%d",s[u][n]);

if(s[u][n]<result)

result=s[u][n];

}

returnresult;

}intmain()

{

intn;

scanf("%d",&n);

for(inti=1;i<=n;i++)

scanf("%d",&num[i]);

printf("%d\n",min(n));

printf("%d\n",ma*(n));

return1;

}第三章貪心算法貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在*種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。3.1貪心算法的特性貪婪算法可解決的問題通常大局部都有如下的特性：⑴有一個以最優(yōu)方式來解決的問題。為了構(gòu)造問題的解決方案，有一個候選的對象的集合：比方不同面值的硬幣。⑵隨著算法的進(jìn)展，將積累起其它兩個集合：一個包含已經(jīng)被考慮過并被選出的候選對象，另一個包含已經(jīng)被考慮過但被丟棄的候選對象。⑶有一個函數(shù)來檢查一個候選對象的集合是否提供了問題的解答。該函數(shù)不考慮此時的解決方法是否最優(yōu)。⑷還有一個函數(shù)檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數(shù)一樣，此時不考慮解決方法的最優(yōu)性。⑸選擇函數(shù)可以指出哪一個剩余的候選對象最有希望構(gòu)成問題的解。⑹最后，目標(biāo)函數(shù)給出解的值。為了解決問題，需要尋找一個構(gòu)成解的候選對象集合，它可以優(yōu)化目標(biāo)函數(shù)，貪婪算法一步一步的進(jìn)展。起初，算法選出的候選對象的集合為空。接下來的每一步中，根據(jù)選擇函數(shù)，算法從剩余候選對象中選出最有希望構(gòu)成解的對象。如果集合中加上該對象后不可行，則該對象就被丟棄并不再考慮；否則就加到集合里。每一次都擴(kuò)大集合，并檢查該集合是否構(gòu)成解。如果貪婪算法正確工作，則找到的第一個解通常是最優(yōu)的。3.2貪心算法的根本思路⒈建立數(shù)學(xué)模型來描述問題。⒉把求解的問題分成假設(shè)干個子問題。⒊對每一子問題求解，得到子問題的局部最優(yōu)解。⒋把子問題的解局部最優(yōu)解合成原來解問題的一個解。實(shí)現(xiàn)該算法的過程：從問題的*一初始解出發(fā)；while能朝給定總目標(biāo)前進(jìn)一步do求出可行解的一個解元素；由所有解元素組合成問題的一個可行解。3.3實(shí)例分析3.3.1活動安排問題活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用*一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。設(shè)有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個完畢時間fi,且si<fi。如果選擇了活動i，則它在半開時間區(qū)間[si,fi)內(nèi)占用資源。假設(shè)區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動i與活動j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時，活動i與活動j相容。在下面所給出的解活動安排問題的貪心算法greedySelector:publicstaticintgreedySelector(int[]s,int[]f,booleana[]){intn=s.length-1;a[1]=true;intj=1;intcount=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}3.3.2最優(yōu)裝載 有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。該問題可形式化描述為：其中，變量=0表示不裝入集裝箱i，=1表示裝入集裝箱i。1.算法描述 最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下頁。publicstaticfloatloading(floatc,float[]w,int[]*){intn=w.length;Element[]d=newElement[n];for(inti=0;i<n;i++)d[i]=newElement(w[i],i);MergeSort.mergeSort(d);floatopt=0;for(inti=0;i<n;i++)*[i]=0;for(inti=0;i<n&&d[i].w<=c;i++){*[d[i].i]=1;opt+=d[i].w;c-=d[i].w;}returnopt;}2.貪心選擇性質(zhì)設(shè)集裝箱已依其重量從小到大排序，〔*1，*2，...，*n〕是最優(yōu)裝載問題的一個最優(yōu)解。又設(shè)k=。易知，如果給定的最優(yōu)裝載問題有解，則1≤k≤n。當(dāng)k=1時，〔*1，*2，...，*n〕是一個滿足貪心選擇性質(zhì)的最優(yōu)解。當(dāng)k>1時，取y1=1，yk=0，yi=*i，1<i≤n，i≠k，則因此，〔y1，y2，...，yn〕是所給最優(yōu)裝載問題的可行解。另一方面，由，知〔y1，y2，...，yn〕是滿足貪心選擇性質(zhì)的最優(yōu)解?？梢宰C明最優(yōu)裝載問題具有貪心選擇性質(zhì)。3.最優(yōu)子構(gòu)造性質(zhì) 最優(yōu)裝載問題具有最優(yōu)子構(gòu)造性質(zhì)。由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子構(gòu)造性質(zhì)，容易證明算法loading的正確性。算法loading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為O(nlogn)。3.3.3課后習(xí)題汽車加油問題問題描述：一輛汽車加滿油后可行駛nkm。旅途中有假設(shè)干加油站。設(shè)計一個有效算法，指出應(yīng)在哪些加油站?？考佑?，使沿途加油次數(shù)最少。并證明算法能產(chǎn)出一個最優(yōu)解。編程任務(wù)：對于給定的n和k個加油站位置，編程計算最少加油次數(shù)。數(shù)據(jù)輸入：由文件input.t*t給出輸入數(shù)據(jù)。第1行有2個正整數(shù)n和k，表示汽車加滿油后可行駛nkm，且旅途中有k個加油站。接下來的1行中，有k+1個整數(shù)，表示第k個加油站與第k-1個加油站之間的距離。第0個加油站表示出發(fā)地，汽車已加滿油。第k+1個加油站表示目的地。結(jié)果輸出：將編程計算出的最少加油次數(shù)輸出到文件output.t*t。如果無法到達(dá)目的地，則輸出"NoSolution"。輸入文件例如輸出文件例如input.t*toutput.t*t77412345166源程序：#include"stdio.h"voidmain(){FILE*in,*out;inti,s,n,k,*[100],sum=0;//*數(shù)組用來存儲距離，sum表示加油次數(shù)，s表示加油后行駛的距離in=fopen("input.t*t","r");//讀入n，k以及距離fscanf(in,"%d",&n);fscanf(in,"%d",&k);for(i=0;i<=k;i++)fscanf(in,"%d",&*[i]);for(i=0;i<=k;i++){ if(*[i]>n)printf("NoSolution!");}for(i=0,s=0;i<=k;i++){ s+=*[i]; if(s>n){sum++; s=*[i];} }out=fopen("output.t*t","w");//輸出結(jié)果sum到output.t*t中fprintf(out,"%d",sum);}回溯法有許多問題，當(dāng)需要找出它的解集或者要求答復(fù)什么解是滿足*些約束條件的最正確解時，往往要使用回溯法?；厮莘ǖ母咀龇ㄊ撬阉?，或是一種組織得井井有條的，能防止不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。4.1回溯法的根本思想(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間構(gòu)造；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)防止無效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。4.2實(shí)例分析4.2.1裝在問題有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。容易證明，如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等價于以下特殊的0-1背包問題。用回溯法設(shè)計解裝載問題的O(2n)計算時間算法。在*些情況下該算法優(yōu)于動態(tài)規(guī)劃算法。解空間：子集樹可行性約束函數(shù)(選擇當(dāng)前元素)：上界函數(shù)(不選擇當(dāng)前元素)：當(dāng)前載重量cw+剩余集裝箱的重量r當(dāng)前最優(yōu)載重量bestw。privatestaticvoidbacktrack(inti){//搜索第i層結(jié)點(diǎn)if(i>n)//到達(dá)葉結(jié)點(diǎn)更新最優(yōu)解best*,bestw;return;r-=w[i];if(cw+w[i]<=c){//搜索左子樹*[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}if(cw+r>bestw){*[i]=0;//搜索右子樹backtrack(i+1);}r+=w[i];}4.2.2符號三角形問題下列圖是由14個"+〞和14個"-〞組成的符號三角形。2個同號下面都是"+〞，2個異號下面都是"-〞。++-+-++

++-+-++

+----+

-+++-

-++-

-+-

--

+在一般情況下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的"+〞和"-〞的個數(shù)一樣。解向量：用n元組*[1:n]表示符號三角形的第一行?？尚行约s束函數(shù)：當(dāng)前符號三角形所包含的"+〞個數(shù)與"-〞個數(shù)均不超過n*(n+1)/4無解的判斷：n*(n+1)/2為奇數(shù)。代碼局部：privatestaticvoidbacktrack(intt){if((count>half)||(t*(t-1)/2-count>half))return;if(t>n)sum++;elsefor(inti=0;i<2;i++){p[1][t]=i;count+=i;for(intj=2;j<=t;j++){p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];count+=p[j][t-j+1];}backtrack(t+1);for(intj=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}5.2.3課后習(xí)題最正確調(diào)度問題問題描述：假設(shè)有n個任務(wù)由k個可并行工作的機(jī)器來完成。完成任務(wù)i需要的時間為ti。試設(shè)計一個算法找到出完成這個n個任務(wù)的最正確調(diào)度，使得完成全部任務(wù)的時間最早。編程任務(wù)：對任意給定的整數(shù)n和k，以及完成任務(wù)i需要的時間為ti，i=1-n。編程計算完成這n個任務(wù)的最正確調(diào)度。數(shù)據(jù)輸入：由文件input.t*t給出輸入數(shù)據(jù)。第1行有2個正整數(shù)n和k。第2行的n個正整數(shù)是完成n根任務(wù)需要的時間。結(jié)果輸出：將計算出的完成全部任務(wù)的最早時間輸出到文件output.t*t。輸入文件例如輸出文件例如input.t*toutput.t*t7317214416653源程序：#include"stdio.h"intlen[100],t[100],best=1000,n,k;intp()//p函數(shù)用來計算完成時間{inttmp=0;for(inti=0;i<k;i++)if(len[i]>tmp)tmp=len[i]; returntmp;}voidsearch(intdep)//search函數(shù)用來回溯搜索{if(dep==n){ inttmp=p(); if(tmp<best)best=tmp; return;}for(inti=0;i<k;i++){ len[i]+=t[dep]; if(len[i]<best)search(dep+1); len[i]-=t[dep];}}voidmain(){FILE*in,*out;in=fopen("input.t*t","r");//讀入n，k以及每個任務(wù)需要時間t[i]fscanf(in,"%d",&n);fscanf(in,"%d",&k);for(inti=0;i<n;i++){ fscanf(in,"%d",&t[i]);len[i]=0;}search(0);//第一個任務(wù)開場搜索out=fopen("output.t*t","w");fprintf(out,"%d",best);}第五章分支限界法5.1 分支限界法的根本思想1、分支限界法與回溯法的不同〔1〕求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在*種意義下的最優(yōu)解。〔2〕搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小消耗優(yōu)先的方式搜索解空間樹。2、分支限界法根本思想分支限界法常以廣度優(yōu)先或以最小消耗〔最大效益〕優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結(jié)點(diǎn)只有一次時機(jī)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被參加活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時為止。3、常見的兩種分支限界法〔1〕隊(duì)列式(FIFO)分支限界法按照隊(duì)列先進(jìn)先出〔FIFO〕原則選取下一個節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)?！?〕優(yōu)先隊(duì)列式分支限界法按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。5.2實(shí)例分析5.2.1單源最短路徑問題1、問題描述下面以一個例子來說明單源最短路徑問題：在下列圖所給的有向圖G中，每一邊都有一個非負(fù)邊權(quán)。要求圖G的從源頂點(diǎn)s到目標(biāo)頂點(diǎn)t之間的最短路徑。下列圖是用優(yōu)先隊(duì)列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)所對應(yīng)的當(dāng)前路長。2.算法思想解單源最短路徑問題的優(yōu)先隊(duì)列式分支限界法用一極小堆來存儲活結(jié)點(diǎn)表。其優(yōu)先級是結(jié)點(diǎn)所對應(yīng)的當(dāng)前路長。算法從圖G的源頂點(diǎn)s和空優(yōu)先隊(duì)列開場。結(jié)點(diǎn)s被擴(kuò)展后，它的兒子結(jié)點(diǎn)被依次插入堆中。此后，算法從堆中取出具有最小當(dāng)前路長的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并依次檢查與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰的所有頂點(diǎn)。如果從當(dāng)前擴(kuò)展結(jié)點(diǎn)i到頂點(diǎn)j有邊可達(dá)，且從源出發(fā)，途經(jīng)頂點(diǎn)i再到頂點(diǎn)j的所相應(yīng)的路徑的長度小于當(dāng)前最優(yōu)路徑長度，則將該頂點(diǎn)作為活結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。這個結(jié)點(diǎn)的擴(kuò)展過程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時為止3.剪枝策略在算法擴(kuò)展結(jié)點(diǎn)的過程中，一旦發(fā)現(xiàn)一個結(jié)點(diǎn)的下界不小于當(dāng)前找到的最短路長，則算法剪去以該結(jié)點(diǎn)為根的子樹。在算法中，利用結(jié)點(diǎn)間的控制關(guān)系進(jìn)展剪枝。從源頂點(diǎn)s出發(fā)，2條不同路徑到達(dá)圖G的同一頂點(diǎn)。由于兩條路徑的路長不同，因此可以將路長長的路徑所對應(yīng)的樹