(算法分析設(shè)計(jì)）第5章回溯法

1、( (算法分析設(shè)計(jì)第算法分析設(shè)計(jì)第5 5章回溯法章回溯法7回溯法的根本思想 根本思想根本思想 在確定解空間的組織結(jié)構(gòu)后，回溯法從開(kāi)始結(jié)點(diǎn)在確定解空間的組織結(jié)構(gòu)后，回溯法從開(kāi)始結(jié)點(diǎn)根結(jié)點(diǎn)出發(fā)，以深度優(yōu)先方式搜索整個(gè)解空根結(jié)點(diǎn)出發(fā)，以深度優(yōu)先方式搜索整個(gè)解空間。這個(gè)開(kāi)始結(jié)點(diǎn)成為活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前間。這個(gè)開(kāi)始結(jié)點(diǎn)成為活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。的擴(kuò)展結(jié)點(diǎn)。 在當(dāng)前擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新在當(dāng)前擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)成為新的活結(jié)點(diǎn)，并成為擴(kuò)展結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)成為新的活結(jié)點(diǎn)，并成為擴(kuò)展結(jié)點(diǎn)。結(jié)點(diǎn)。 如果在當(dāng)前擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，如果在當(dāng)前擴(kuò)

2、展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，那么當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回那么當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)回溯到最近的活結(jié)點(diǎn)處，并使該結(jié)點(diǎn)成移動(dòng)回溯到最近的活結(jié)點(diǎn)處，并使該結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。 回溯法按上述方式遞歸地在解空間中搜索，直到回溯法按上述方式遞歸地在解空間中搜索，直到找到所要求的解或解空間中無(wú)活結(jié)點(diǎn)為止。找到所要求的解或解空間中無(wú)活結(jié)點(diǎn)為止。8實(shí)例分析 n=3的的0-1背包問(wèn)題背包問(wèn)題 w=16,15,15 p=45,25,25 c=309解空間為：解空間為：(0,0,0), (0,1,0), (0,0,1), (1,0,0), (0,1,1), (

3、1,0,1), (1,1,0), (1,1,1)ABCDEFGHIJKLMNO10111111000000n=3的的0-1背包問(wèn)題的解空間樹(shù)背包問(wèn)題的解空間樹(shù)活結(jié)點(diǎn)&當(dāng)前擴(kuò)展結(jié)點(diǎn)BBB活結(jié)點(diǎn)死結(jié)點(diǎn)10ABCDEFGHIJKLMNO10111111000000當(dāng)前唯一的活結(jié)點(diǎn)，也是當(dāng)前的擴(kuò)展結(jié)點(diǎn)假定沿縱深方向假定沿縱深方向進(jìn)行搜索時(shí)，選進(jìn)行搜索時(shí)，選擇先移至結(jié)點(diǎn)擇先移至結(jié)點(diǎn)B11ABCDEFGHIJKLMNO10111111000000結(jié)點(diǎn)A、B都是活結(jié)點(diǎn)，B是當(dāng)前擴(kuò)展結(jié)點(diǎn)說(shuō)明：由于選中了w1，所以結(jié)點(diǎn)B處剩余背包容量為30-16=14，獲取的價(jià)值為45下一步向D移動(dòng)，還是向E移動(dòng)？12ABCD

4、EFGHIJKLMNO10111111000000分析：分析：由于移動(dòng)到由于移動(dòng)到D，說(shuō)明需要將物品，說(shuō)明需要將物品2放入背包，物放入背包，物品品2的體積為的體積為15，而背包目前的剩余容量為，而背包目前的剩余容量為1414移向結(jié)點(diǎn)移向結(jié)點(diǎn)K可行不增加容量可行不增加容量15ABCDEFGHIJKLMNO10111111000000分析：分析：由于從K結(jié)點(diǎn)無(wú)法再向縱深方向移動(dòng)，因此，K結(jié)點(diǎn)成為死結(jié)點(diǎn)，回溯到上一個(gè)活結(jié)點(diǎn)E。（1，0，0）為一可行解）為一可行解16ABCDEFGHIJKLMNO10111111000000分析：分析：由于從E結(jié)點(diǎn)無(wú)法再向縱深方向移動(dòng)，因此，E結(jié)點(diǎn)成為死結(jié)點(diǎn)，回溯到上

5、一個(gè)活結(jié)點(diǎn)B。17ABCDEFGHIJKLMNO10111111000000分析：分析：由于從B結(jié)點(diǎn)無(wú)法再向縱深方向移動(dòng)，因此，B結(jié)點(diǎn)成為死結(jié)點(diǎn)，回溯到上一個(gè)活結(jié)點(diǎn)A。18ABCDEFGHIJKLMNO10111111000000向縱深移動(dòng)到C19ABCDEFGHIJKLMNO10111111000000此時(shí)A、C為活結(jié)點(diǎn)C為當(dāng)前擴(kuò)展結(jié)點(diǎn)分析：分析：此時(shí)，背包的剩余容量為r=30，獲取的價(jià)值為0假定沿縱深方向進(jìn)假定沿縱深方向進(jìn)行搜索時(shí)，選擇先行搜索時(shí)，選擇先移至結(jié)點(diǎn)移至結(jié)點(diǎn)F20ABCDEFGHIJKLMNO10111111000000此時(shí)A、C、F為活結(jié)點(diǎn)F為當(dāng)前擴(kuò)展結(jié)點(diǎn)分析：分析：此時(shí)，背

6、包的剩余容量為r=30-15=15，獲取的價(jià)值為25移動(dòng)方向：移動(dòng)方向：L or M ？分析：分析：移向結(jié)點(diǎn)移向結(jié)點(diǎn)L、M都可行都在容量允許范圍內(nèi)都可行都在容量允許范圍內(nèi)21ABCDEFGHIJKLMNO10111111000000(0,1,1)為一可行解為一可行解22ABCDEFGHIJKLMNO10111111000000按上述規(guī)那么進(jìn)行解空間搜索，直到所有的結(jié)點(diǎn)都成為死結(jié)點(diǎn)此時(shí)共獲得5個(gè)可行解：(1,0,0)，(0,1,1)，(0,1,0)，(0,0,1)，(0,0,0)其中(0,1,1)為最優(yōu)解23如何防止回溯法的無(wú)效搜索 防止無(wú)效搜索防止無(wú)效搜索 用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束

7、用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹(shù)；的子樹(shù)； 見(jiàn)見(jiàn)0-1背包問(wèn)題背包問(wèn)題 用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)；用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)； 見(jiàn)見(jiàn)TSP問(wèn)題問(wèn)題 以上兩類函數(shù)統(tǒng)稱為剪枝函數(shù)以上兩類函數(shù)統(tǒng)稱為剪枝函數(shù)24回溯法的主要步驟 主要步驟主要步驟 針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；針對(duì)所給問(wèn)題，定義問(wèn)題的解空間； 確定易于搜索的解空間結(jié)構(gòu)；確定易于搜索的解空間結(jié)構(gòu)； 以深度優(yōu)先方式搜索解空間，并在搜索過(guò)以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)防止無(wú)效搜索。程中用剪枝函數(shù)防止無(wú)效搜索。25知識(shí)點(diǎn) 問(wèn)題的解空間 回溯法的根本思想 遞歸回溯 迭代回溯 子集樹(shù)與排列樹(shù)26遞歸回

8、溯void backtrackbacktrack( int t) if(tn) output(x); elsefor(int i=f(n,t);i0) if(f(n,t)=g(n,t) for(int i=f(n,t);in) output(x); elsefor(int i=0;in) output(x); elsefor(int i=t;i59，所以舍棄該結(jié)點(diǎn)所以舍棄該結(jié)點(diǎn)。按上述搜索原那么，對(duì)整按上述搜索原那么，對(duì)整個(gè)排列樹(shù)進(jìn)行遍歷，共找個(gè)排列樹(shù)進(jìn)行遍歷，共找到條可能的周游路徑，到條可能的周游路徑，其中費(fèi)用最少的周游路徑其中費(fèi)用最少的周游路徑為為1-3-2-4-1其費(fèi)用為其費(fèi)用為2545

9、剪枝函數(shù)的引入 剪枝函數(shù)的引入剪枝函數(shù)的引入 目的：提高回溯法的搜索效率；目的：提高回溯法的搜索效率； 剪枝函數(shù)的設(shè)定：剪枝函數(shù)的設(shè)定： 采用當(dāng)前的最短路徑為為標(biāo)準(zhǔn)，對(duì)采用當(dāng)前的最短路徑為為標(biāo)準(zhǔn)，對(duì)于有個(gè)結(jié)點(diǎn)的于有個(gè)結(jié)點(diǎn)的TSP問(wèn)題來(lái)說(shuō)，假設(shè)當(dāng)前問(wèn)題來(lái)說(shuō)，假設(shè)當(dāng)前搜索第層搜索第層(1i25，所以舍棄該結(jié)點(diǎn)所以舍棄該結(jié)點(diǎn)。I為根為根的子樹(shù)不可能包含更優(yōu)的解，剪去。的子樹(shù)不可能包含更優(yōu)的解，剪去。按上述搜索原那么，對(duì)整按上述搜索原那么，對(duì)整個(gè)排列樹(shù)進(jìn)行遍歷，共找個(gè)排列樹(shù)進(jìn)行遍歷，共找到條可能的周游路徑，到條可能的周游路徑，其中費(fèi)用最少的周游路徑其中費(fèi)用最少的周游路徑為為1-3-2-4-1其費(fèi)用為其

10、費(fèi)用為2547#include #include const int n=4; /圖的頂點(diǎn)數(shù)class Travelingfriend int TSP(int an, int v);private:void Swap(int &, int &);void Backtrack(int i);int ann, /圖G的鄰接矩陣 cv, /當(dāng)前費(fèi)用 bestv; /當(dāng)前最優(yōu)值 *x, /當(dāng)前解 *bestx, / 當(dāng)前最優(yōu)解;48void Traveling:Backtrack(int i)if (i+1n)if (axn-2xn-1 & axn-10 & cv+ axn-2xn-1+axn-10b

11、estv) / 比較當(dāng)前的最優(yōu)解與當(dāng)前獲得的解，當(dāng)前解更優(yōu)那么替換for (int j=0; jn; j+) bestxj=xj;bestv = cv + axn-2xn-1 + axn-10;return;for (int j=i; jn; j+)/ 判斷是否可進(jìn)入xj子樹(shù)，此處實(shí)現(xiàn)了剪枝if (axi-1xj & cv+axi-1xjbestv)/ 搜索子樹(shù)Swap(xi, xj);cv += axi-1xi;Backtrack(i+1);cv -= axi-1xi;Swap(xi, xj);49int TSP(int an, int v)/ 初始化Traveling Y;Y.x=new

12、int n;for (int i=0; in; i+) Y.xi=i;for (i=0; in; i+) /連接代價(jià)對(duì)稱for (int j=0; j=i; j+) Y.aij=Y.aji=aij;Y.cv=0;Y.bestv=100000; / Y.bestx=v;coutAdjacency Matrix of G:n;for (i=0; in; i+)for (int j=0; jn; j+) coutsetw(5)Y.aij;coutendl;Y.Backtrack(1);delete Y.x;return Y.bestv;50void main()int tn=0,30,6,5,4,1

13、0,20, vn=0,1,2,3;coutnBestv= TSP(t, v)nnPath = ;for (int i=0; in; i+) coutvi+1setw(4);coutv0+1endlendl;復(fù)雜度分析復(fù)雜度分析算法backtrack在最壞情況下可能需要更新當(dāng)前最優(yōu)解O(n-1)!)次，每次更新bestx需計(jì)算時(shí)間O(n)，從而整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為O(n!)。 51常用的TSP問(wèn)題求解方案 常用的求解常用的求解TSP問(wèn)題的方案問(wèn)題的方案 遺傳算法 模擬退火 神經(jīng)網(wǎng)絡(luò) 并行算法52N皇后問(wèn)題皇后問(wèn)題53皇后問(wèn)題 P129 皇后問(wèn)題皇后問(wèn)題 問(wèn)題描述：在問(wèn)題描述：在n*n格的棋

14、盤(pán)上放置彼此不受格的棋盤(pán)上放置彼此不受攻擊的個(gè)皇后。攻擊的個(gè)皇后。 按國(guó)際象棋規(guī)那么，皇后可以攻擊與之處按國(guó)際象棋規(guī)那么，皇后可以攻擊與之處于同一行或同一列或同一斜線上的棋子。于同一行或同一列或同一斜線上的棋子。54皇后問(wèn)題 皇后問(wèn)題皇后問(wèn)題 大數(shù)學(xué)家高斯于大數(shù)學(xué)家高斯于1850年提出年提出 N. Wirth在在?程序程序=算算法法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)?中給中給出了該問(wèn)題的回溯算出了該問(wèn)題的回溯算法法Pascal語(yǔ)言實(shí)現(xiàn)語(yǔ)言實(shí)現(xiàn) 可獲得個(gè)解，但可獲得個(gè)解，但實(shí)際上只有個(gè)不實(shí)際上只有個(gè)不同解考慮棋盤(pán)的對(duì)同解考慮棋盤(pán)的對(duì)稱性稱性55皇后問(wèn)題的個(gè)不同解圖示說(shuō)明圖示說(shuō)明56其中一個(gè)可行解的圖示其中一個(gè)可

15、行解：x1 x2 x3 x4 x5 x6 x7 x81 5 8 6 3 7 2 4表示第個(gè)皇后被放在第行的第列上57算法設(shè)計(jì) 算法設(shè)計(jì)算法設(shè)計(jì) 用元組x1:n表示n皇后問(wèn)題的解 xi表示皇后i放在第i行的第xi列上 用完全叉樹(shù)表示解空間用完全叉樹(shù)表示解空間 剪枝函數(shù)設(shè)計(jì)剪枝函數(shù)設(shè)計(jì)：對(duì)于兩個(gè)皇后A(i,j)、B(k,l) 兩個(gè)皇后不同行：i不等于k; 兩個(gè)皇后不同列：j不等于l; 兩個(gè)皇后不同一條斜線 |i-k|j-l|，即兩個(gè)皇后不處于同一條y=x+a或y=-x+a的直線上58實(shí)現(xiàn)遞歸算法bool Queen:Place(int k) for (int j=1;jn) sum+; else

16、for (int i=1;i=n;i+) xt=i; if (Place(t) Backtrack(t+1); 59實(shí)現(xiàn)迭代算法void nQueen( int nn) n=nn; sum=0; x= new intn+1; for (int i=0;i0) xk+=1; while(xk=n) & !(place(k) xk+=1; /搜索可能的放置位置 if (xkn，表示算法搜索到葉結(jié)點(diǎn) 得到一個(gè)新的方案，當(dāng)前找到的m可著色方案數(shù)加1； 當(dāng)in時(shí)，表示當(dāng)前擴(kuò)展結(jié)點(diǎn)為解空間樹(shù)的內(nèi)部結(jié)點(diǎn)，該結(jié)點(diǎn)有xi=1,2,m共m個(gè)子結(jié)點(diǎn) 對(duì)該結(jié)點(diǎn)的每一個(gè)子結(jié)點(diǎn)，根據(jù)鄰接矩陣a和兩個(gè)頂點(diǎn)的著色，判斷其可行

17、性； 如果可行，繼續(xù)按深度優(yōu)先方式遞歸地對(duì)可行子樹(shù)進(jìn)行搜索； 否那么，將以該子結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹(shù)中的所有結(jié)點(diǎn)都設(shè)置為死結(jié)點(diǎn)，算法回溯到為活結(jié)點(diǎn)的最近的父結(jié)點(diǎn)處繼續(xù)按深度優(yōu)先方式進(jìn)行搜索；剪枝函數(shù)剪枝函數(shù)69解向量：(x1, x2, , xn)表示頂點(diǎn)i所著顏色xi 可行性約束函數(shù)：頂點(diǎn)i與已著色的相鄰頂點(diǎn)顏色不重復(fù)。類Coloring記錄解空間中結(jié)點(diǎn)信息void Color:Backtrack(int t) if (tn) sum+; for (int i=1; i=n; i+) cout xi ; cout endl; else for (int i=1;i=m;i+) xt=i; if (

18、Ok(t) Backtrack(t+1); xt=0; bool Color:Ok(int k)/ 檢查顏色可用性 for (int j=1;jn時(shí)，算法搜索到葉結(jié)點(diǎn)，得到新的圓排時(shí)，算法搜索到葉結(jié)點(diǎn)，得到新的圓排列方案并計(jì)算當(dāng)前圓排列長(zhǎng)度；列方案并計(jì)算當(dāng)前圓排列長(zhǎng)度； 如果小于當(dāng)前的最優(yōu)解，那么將該解定為當(dāng)如果小于當(dāng)前的最優(yōu)解，那么將該解定為當(dāng)前的最優(yōu)解；前的最優(yōu)解； 否那么，舍棄；否那么，舍棄； 當(dāng)當(dāng)in時(shí)，表示當(dāng)前擴(kuò)展結(jié)點(diǎn)為結(jié)空間樹(shù)的內(nèi)時(shí)，表示當(dāng)前擴(kuò)展結(jié)點(diǎn)為結(jié)空間樹(shù)的內(nèi)部結(jié)點(diǎn)，此時(shí)算法要選擇下一個(gè)要排列的圓，部結(jié)點(diǎn)，此時(shí)算法要選擇下一個(gè)要排列的圓，并計(jì)算相應(yīng)的下界函數(shù)。并計(jì)算相應(yīng)的下界函

19、數(shù)。 如果滿足下界約束小于設(shè)定的閾值，繼如果滿足下界約束小于設(shè)定的閾值，繼續(xù)按深度優(yōu)先方式遞歸地對(duì)相應(yīng)子樹(shù)進(jìn)行搜續(xù)按深度優(yōu)先方式遞歸地對(duì)相應(yīng)子樹(shù)進(jìn)行搜索；索； 否那么，剪去該子樹(shù)，算法回溯到為活結(jié)點(diǎn)否那么，剪去該子樹(shù)，算法回溯到為活結(jié)點(diǎn)的最近的父結(jié)點(diǎn)處繼續(xù)按深度優(yōu)先方式進(jìn)行的最近的父結(jié)點(diǎn)處繼續(xù)按深度優(yōu)先方式進(jìn)行搜索；搜索；76算法實(shí)現(xiàn)void Circle:Backtrack( int t) if(tn) compute();compute(); elsefor(int j=t;j=n;j+) Swap(rt,rj); float centerx= Center(t);Center(t); i

20、f(centerx+rt+r1min) /下界約束xt=centerx;Backtrack(t+1); Swap(rt,rj);已經(jīng)找到一個(gè)新的圓排列已經(jīng)找到一個(gè)新的圓排列方案，計(jì)算該方案的圓排方案，計(jì)算該方案的圓排列長(zhǎng)度列長(zhǎng)度計(jì)算當(dāng)前所選擇的圓的圓心計(jì)算當(dāng)前所選擇的圓的圓心橫坐標(biāo)（取最小值返回）橫坐標(biāo)（取最小值返回）77算法實(shí)現(xiàn)Float Circle:Center(int t) float temp=0; for(int j=1;jtemp) temp= valuex; 2)()(22jrtrjrtrjrtr242x記錄當(dāng)前圓排列中各圓的圓心橫坐標(biāo)78算法實(shí)現(xiàn)float Circle:Co

21、mpute(void) float low=0, high=0; for(int i=1;i=n;i+) if (xi-rihigh) high = xi+ri; if (high-lowmin) min = high low; low/high記錄當(dāng)前圓排列中各圓的最左/右橫坐標(biāo)79算法復(fù)雜性分析)!1( nO析圓排列的算法復(fù)雜性分80回溯法的效率分析回溯法的效率分析回溯法的效率分析影響回溯法效率的主要因素 產(chǎn)生xk的時(shí)間 滿足顯約束的xk值的個(gè)數(shù) 計(jì)算約束函數(shù)constrain的時(shí)間 計(jì)算上界函數(shù)bound的時(shí)間1. 滿足約束函數(shù)和上界函數(shù)約束的所有xk的個(gè)數(shù)好的約束函數(shù)可以明顯降低生成結(jié)

22、點(diǎn)的數(shù)量，但往往需要較大的計(jì)算量。在選擇約束函數(shù)時(shí)，通常采取在生成結(jié)點(diǎn)數(shù)和約束函數(shù)計(jì)算量之間取折衷。解空間的結(jié)構(gòu)一旦選定，影響回溯法效解空間的結(jié)構(gòu)一旦選定，影響回溯法效率的前三個(gè)因素就可以確定，剩下的就率的前三個(gè)因素就可以確定，剩下的就是考慮回溯過(guò)程中生成結(jié)點(diǎn)的個(gè)數(shù)。是考慮回溯過(guò)程中生成結(jié)點(diǎn)的個(gè)數(shù)。隨問(wèn)題的具體內(nèi)容以及結(jié)點(diǎn)的隨問(wèn)題的具體內(nèi)容以及結(jié)點(diǎn)的不同生成方式而變動(dòng)不同生成方式而變動(dòng)81對(duì)于許多問(wèn)題而言，在搜索試探時(shí)選取xi的值順序是任意的。在其它條件相當(dāng)?shù)那疤嵯拢尶扇≈底钌俚脑谄渌鼦l件相當(dāng)?shù)那疤嵯?，讓可取值最少的xi優(yōu)先優(yōu)先。從圖中關(guān)于同一問(wèn)題的2棵不同解空間樹(shù)，可以體會(huì)到這種策略的潛力

23、。圖(a)中，從第1層剪去1棵子樹(shù)，那么從所有應(yīng)當(dāng)考慮的3元組中一次消去12個(gè)3元組。對(duì)于圖(b)，雖然同樣從第1層剪去1棵子樹(shù)，卻只從應(yīng)當(dāng)考慮的3元組中消去8個(gè)3元組。前者的效果明顯比后者好。(a)(b)82存在的困難 存在的困難存在的困難 對(duì)回溯法在解具體問(wèn)題時(shí)所產(chǎn)生的結(jié)點(diǎn)對(duì)回溯法在解具體問(wèn)題時(shí)所產(chǎn)生的結(jié)點(diǎn)數(shù)的估計(jì)數(shù)的估計(jì) 即使對(duì)兩個(gè)非常相近的實(shí)例，其產(chǎn)生的即使對(duì)兩個(gè)非常相近的實(shí)例，其產(chǎn)生的結(jié)點(diǎn)數(shù)也會(huì)存在很大的差異結(jié)點(diǎn)數(shù)也會(huì)存在很大的差異 可參考性不理想可參考性不理想 解決的方法：概率方法解決的方法：概率方法83用概率方法估計(jì)將產(chǎn)生的接點(diǎn)數(shù) 用概率方法估計(jì)將產(chǎn)生的結(jié)點(diǎn)數(shù)用概率方法估計(jì)將產(chǎn)生的結(jié)點(diǎn)數(shù) 主要思想主要思想 在解空間樹(shù)上產(chǎn)生一條隨機(jī)路徑，然后沿該路徑估算解空間中滿足約束條件的結(jié)點(diǎn)樹(shù)m。 直到延伸到葉節(jié)點(diǎn)或所有子節(jié)點(diǎn)都不滿足約束條件為止84public int estimate( int n )public int estimate( int n ) int m=