分治算法
一回铛、基本概念
在計(jì)算機(jī)科學(xué)中，分治法是一種很重要的算法茵肃。字面上的解釋是“分而治之”，就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題袭祟，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并巾乳。這個技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序胆绊，歸并排序)氨鹏，傅立葉變換(快速傅立葉變換)……
??? 任何一個可以用計(jì)算機(jī)求解的問題所需的計(jì)算時間都與其規(guī)模有關(guān)压状。問題的規(guī)模越小喻犁，越容易直接求解何缓，解題所需的計(jì)算時間也越少肢础。例如碌廓，對于n個元素的排序問題传轰，當(dāng)n=1時谷婆，不需任何計(jì)算慨蛙。n=2時纪挎，只要作一次比較即可排好序期贫。n=3時只要作3次比較即可异袄，…通砍。而當(dāng)n較大時，問題就不那么容易處理了封孙。要想直接解決一個規(guī)模較大的問題，有時是相當(dāng)困難的虎忌。
二泡徙、基本思想及策略
分治法的設(shè)計(jì)思想是：將一個難以直接解決的大問題膜蠢，分割成一些規(guī)模較小的相同問題堪藐，以便各個擊破挑围，分而治之礁竞。
分治策略是：對于一個規(guī)模為n的問題贪惹，若該問題可以容易地解決（比如說規(guī)模n較兴照隆）則直接解決奏瞬，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同硼端，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解寓搬。這種算法設(shè)計(jì)策略叫做分治法。
如果原問題可分割成k個子問題句喷，1
三、分治法適用的情況
?? ?分治法所能解決的問題一般具有以下幾個特征：
1) 該問題的規(guī)耐偾恚縮小到一定的程度就可以容易地解決
2) 該問題可以分解為若干個規(guī)模較小的相同問題兄春，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)锡溯。
3) 利用該問題分解出的子問題的解可以合并為該問題的解赶舆；
4) 該問題所分解出的各個子問題是相互獨(dú)立的祭饭，即子問題之間不包含公共的子子問題芜茵。
第一條特征是絕大多數(shù)問題都可以滿足的倡蝙，因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加九串；
第二條特征是應(yīng)用分治法的前提它也是大多數(shù)問題可以滿足的寺鸥，此特征反映了遞歸思想的應(yīng)用蒸辆；、
第三條特征是關(guān)鍵躬贡，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征拂玻，而不具備第三條特征酸些，則可以考慮用貪心法或動態(tài)規(guī)劃法檐蚜。
第四條特征涉及到分治法的效率魄懂，如果各子問題是不獨(dú)立的則分治法要做許多不必要的工作闯第，重復(fù)地解公共的子問題市栗，此時雖然可用分治法咳短，但一般用動態(tài)規(guī)劃法較好填帽。
四咙好、分治法的基本步驟
分治法在每一層遞歸上都有三個步驟：
?? ?step1 分解：將原問題分解為若干個規(guī)模較小篡腌，相互獨(dú)立勾效，與原問題形式相同的子問題嘹悼；
?? ?step2 解決：若子問題規(guī)模較小而容易被解決則直接解层宫，否則遞歸地解各個子問題
?? ?step3 合并：將各個子問題的解合并為原問題的解杨伙。
它的一般的算法設(shè)計(jì)模式如下：
??? Divide-and-Conquer(P)
??? 1. if |P|≤n0
??? 2. then return(ADHOC(P))
??? 3. 將P分解為較小的子問題 P1 ,P2 ,...,Pk
??? 4. for i←1 to k
??? 5. do yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi
??? 6. T ← MERGE(y1,y2,...,yk) △ 合并子問題
??? 7. return(T)
??? 其中|P|表示問題P的規(guī)模萌腿；n0為一閾值限匣，表示當(dāng)問題P的規(guī)模不超過n0時哮奇，問題已容易直接解出膛腐，不必再繼續(xù)分解鼎俘。ADHOC(P)是該分治法中的基本子算法哲身，用于直接解小規(guī)模的問題P贸伐。因此勘天，當(dāng)P的規(guī)模不超過n0時直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是該分治法中的合并子算法脯丝，用于將P的子問題P1 ,P2 ,...,Pk的相應(yīng)的解y1,y2,...,yk合并為P的解商膊。
五宠进、分治法的復(fù)雜性分析
??? 一個分治法將規(guī)模為n的問題分成k個規(guī)模為n／m的子問題去解晕拆。設(shè)分解閥值n0=1材蹬，且adhoc解規(guī)模為1的問題耗費(fèi)1個單位時間实幕。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間堤器。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計(jì)算時間昆庇，則有：
?T（n）= k T(n/m)+f(n)
??? 通過迭代法求得方程的解：
?? ?遞歸方程及其解只給出n等于m的方冪時T(n)的值闸溃，但是如果認(rèn)為T(n)足夠平滑整吆，那么由n等于m的方冪時T(n)的值可以估計(jì)T(n)的增長速度辉川。通常假定T(n)是單調(diào)上升的表蝙，從而當(dāng) ? ? ? ? ? ? ? ? ?mi≤n
六员串、可使用分治法求解的一些經(jīng)典問題
?（1）二分搜索
（2）大整數(shù)乘法
?（3）Strassen矩陣乘法
（4）棋盤覆蓋
（5）合并排序
（6）快速排序
（7）線性時間選擇
（8）最接近點(diǎn)對問題
（9）循環(huán)賽日程表
（10）漢諾塔
七昼扛、依據(jù)分治法設(shè)計(jì)程序時的思維過程
?? ?實(shí)際上就是類似于數(shù)學(xué)歸納法寸齐，找到解決本問題的求解方程公式抄谐，然后根據(jù)方程公式設(shè)計(jì)遞歸程序渺鹦。
1、一定是先找到最小問題規(guī)模時的求解方法
2毅厚、然后考慮隨著問題規(guī)模增大時的求解方法
3、找到求解的遞歸函數(shù)式后（各種規(guī)钠窒洌或因子），設(shè)計(jì)遞歸程序即可酷窥。
動態(tài)規(guī)劃算法
一、基本概念
?? ?動態(tài)規(guī)劃過程是：每次決策依賴于當(dāng)前狀態(tài)蓬推，又隨即引起狀態(tài)的轉(zhuǎn)移妆棒。一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以糕珊，這種多階段最優(yōu)化決策解決問題的過程就稱為動態(tài)規(guī)劃。
二红选、基本思想與策略
?? ?基本思想與分治法類似澜公，也是將待求解的問題分解為若干個子問題（階段）喇肋，按順序求解子階段玛瘸，前一子問題的解苟蹈，為后一子問題的求解提供了有用的信息糊渊。在求解任一子問題時慧脱，列出各種可能的局部解渺绒，通過決策保留那些有可能達(dá)到最優(yōu)的局部解菱鸥，丟棄其他局部解宗兼。依次解決各子問題氮采，最后一個子問題就是初始問題的解殷绍。
?? ?由于動態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個特點(diǎn)鹊漠，為減少重復(fù)計(jì)算主到，對每一個子問題只解一次躯概，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中登钥。
與分治法最大的差別是：適合于用動態(tài)規(guī)劃法求解的問題娶靡，經(jīng)分解后得到的子問題往往不是互相獨(dú)立的（即下一個子階段的求解是建立在上一個子階段的解的基礎(chǔ)上牧牢，進(jìn)行進(jìn)一步的求解）姿锭。
三塔鳍、適用的情況
能采用動態(tài)規(guī)劃求解的問題的一般要具有3個性質(zhì)：
??? (1) 最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的呻此，就稱該問題具有最優(yōu)子結(jié)構(gòu)轮纫，即滿足最優(yōu)化原理趾诗。
??? (2) 無后效性：即某階段狀態(tài)一旦確定蜡感，就不受這個狀態(tài)以后決策的影響。也就是說郑兴，某狀態(tài)以后的過程不會影響以前的狀態(tài)犀斋，只與當(dāng)前狀態(tài)有關(guān)情连。
（3）有重疊子問題：即子問題之間是不獨(dú)立的叽粹，一個子問題在下一階段決策中可能被多次使用到却舀。（該性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件虫几，但是如果沒有這條性質(zhì)挽拔，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢）
四辆脸、求解的基本步驟
?動態(tài)規(guī)劃所處理的問題是一個多階段決策問題螃诅，一般由初始狀態(tài)開始啡氢，通過對中間階段決策的選擇术裸，達(dá)到結(jié)束狀態(tài)倘是。這些決策形成了一個決策序列袭艺，同時確定了完成整個過程的一條活動路線(通常是求最優(yōu)的活動路線)搀崭。如圖所示猾编。動態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式瘤睹，一般要經(jīng)歷以下幾個步驟袍镀。
?初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài)
?? ? ? ? ? ? ? ? ? ? ?圖1 動態(tài)規(guī)劃決策過程示意圖
(1)劃分階段：按照問題的時間或空間特征默蚌，把問題分為若干個階段苇羡。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的鼻弧，否則問題就無法求解。
(2)確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來攘轩。當(dāng)然，狀態(tài)的選擇要滿足無后效性度帮。
(3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系歼捏，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策瞳秽，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過來做练俐，根據(jù)相鄰兩個階段的狀態(tài)之間的關(guān)系來確定決策方法和狀態(tài)轉(zhuǎn)移方程袖迎。
(4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式腺晾，需要一個遞推的終止條件或邊界條件燕锥。
一般悯蝉，只要解決問題的階段归形、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了鼻由，就可以寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件）连霉。
實(shí)際應(yīng)用中可以按以下幾個簡化的步驟進(jìn)行設(shè)計(jì)：
?? ?（1）分析最優(yōu)解的性質(zhì)嗡靡，并刻畫其結(jié)構(gòu)特征跺撼。
?? ?（2）遞歸的定義最優(yōu)解讨彼。
?? ?（3）以自底向上或自頂向下的記憶化方式（備忘錄法）計(jì)算出最優(yōu)值
?? ?（4）根據(jù)計(jì)算最優(yōu)值時得到的信息歉井，構(gòu)造問題的最優(yōu)解
五哈误、算法實(shí)現(xiàn)的說明
??? 動態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)哩至，也就是上面4個步驟的確定蜜自，一旦設(shè)計(jì)完成菩貌，實(shí)現(xiàn)部分就會非常簡單重荠。
使用動態(tài)規(guī)劃求解問題箭阶，最重要的就是確定動態(tài)規(guī)劃三要素：
（1）問題的階段?
（2）每個階段的狀態(tài)
?（3）從前一個階段轉(zhuǎn)化到后一個階段之間的遞推關(guān)系戈鲁。
遞推關(guān)系必須是從次小的問題開始到較大的問題之間的轉(zhuǎn)化仇参，從這個角度來說婆殿，動態(tài)規(guī)劃往往可以用遞歸程序來實(shí)現(xiàn)诈乒，不過因?yàn)檫f推可以充分利用前面保存的子問題的解來減少重復(fù)計(jì)算，所以對于大規(guī)模問題來說怕磨，有遞歸不可比擬的優(yōu)勢喂饥，這也是動態(tài)規(guī)劃算法的核心之處肠鲫。
確定了動態(tài)規(guī)劃的這三要素仰泻，整個求解過程就可以用一個最優(yōu)決策表來描述滩届，最優(yōu)決策表是一個二維表集侯，其中行表示決策的階段帜消，列表示問題狀態(tài)棠枉，表格需要填寫的數(shù)據(jù)一般對應(yīng)此問題的在某個階段某個狀態(tài)下的最優(yōu)值（如最短路徑泡挺，最長公共子序列辈讶，最大價值等），填表的過程就是根據(jù)遞推關(guān)系贱除，從1行1列開始，以行或者列優(yōu)先的順序媳溺，依次填寫表格，最后根據(jù)整個表格的數(shù)據(jù)通過簡單的取舍或者運(yùn)算求得問題的最優(yōu)解悬蔽。
f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}
六、動態(tài)規(guī)劃算法基本框架
代碼
1for(j=1; j<=m; j=j+1) // 第一個階段
2? xn[j] =初始值;
3
4?for(i=n-1; i>=1; i=i-1)// 其他n-1個階段
5?? for(j=1; j>=f(i); j=j+1)//f(i)與i有關(guān)的表達(dá)式
6? ? xi[j]=j=max（或min）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};
8
9t = g(x1[j1:j2]); // 由子問題的最優(yōu)解求解整個問題的最優(yōu)解的方案10
11print(x1[j1]);
12
13for(i=2; i<=n-1; i=i+1）
15{?17? ? t = t-xi-1[ji];
18
19? ? for(j=1; j>=f(i); j=j+1)
21? ? ? ? if(t=xi[ji])
23? ? ? ? ? ? break;
25}
貪心算法
一蝎困、基本概念：
?所謂貪心算法是指，在對問題求解時禾乘，總是做出在當(dāng)前看來是最好的選擇澎埠。也就是說始藕，不從整體最優(yōu)上加以考慮蒲稳，他所做出的僅是在某種意義上的局部最優(yōu)解鳄虱。
?貪心算法沒有固定的算法框架弟塞，算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇拙已。必須注意的是，貪心算法不是對所有問題都能得到整體最優(yōu)解摧冀，選擇的貪心策略必須具備無后效性系宫，即某個狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)建车。
?所以對所采用的貪心策略一定要仔細(xì)分析其是否滿足無后效性。
二缤至、貪心算法的基本思路：
??? 1.建立數(shù)學(xué)模型來描述問題。
??? 2.把求解的問題分成若干個子問題领斥。
??? 3.對每一子問題求解嫉到，得到子問題的局部最優(yōu)解月洛。
??? 4.把子問題的解局部最優(yōu)解合成原來解問題的一個解何恶。
三嚼黔、貪心算法適用的問題
????? 貪心策略適用的前提是：局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解细层。
實(shí)際上唬涧，貪心算法適用的情況很少疫赎。一般碎节，對一個問題分析是否適用于貪心算法虚缎，可以先選擇該問題下的幾個實(shí)際數(shù)據(jù)進(jìn)行分析钓株，就可做出判斷实牡。
四轴合、貪心算法的實(shí)現(xiàn)框架
??? 從問題的某一初始解出發(fā)创坞；
??? while （能朝給定總目標(biāo)前進(jìn)一步）
??? {?
????????? 利用可行的決策受葛，求出可行解的一個解元素题涨；
??? }
??? 由所有解元素組合成問題的一個可行解总滩；
五纲堵、貪心策略的選擇
???? 因?yàn)橛秘澬乃惴ㄖ荒芡ㄟ^解局部最優(yōu)解的策略來達(dá)到全局最優(yōu)解闰渔，因此席函，一定要注意判斷問題是否適合采用貪心算法策略，找到的解是否一定是問題的最優(yōu)解茂附。
六正蛙、例題分析
??? 下面是一個可以試用貪心算法解的題目营曼，貪心解的確不錯乒验，可惜不是最優(yōu)解蒂阱。
??? [背包問題]有一個背包锻全，背包容量是M=150录煤。有7個物品鳄厌，物品可以分割成任意大小。
??? 要求盡可能讓裝入背包中的物品總價值最大部翘，但不能超過總?cè)萘俊?/p>
??? 物品 A B C D E F G
??? 重量 35 30 60 50 40 10 25
??? 價值 10 40 30 50 35 40 30
??? 分析：
??? 目標(biāo)函數(shù)： ∑pi最大
??? 約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)
??? （1）根據(jù)貪心的策略，每次挑選價值最大的物品裝入背包响委，得到的結(jié)果是否最優(yōu)？
??? （2）每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解赘风？
??? （3）每次選取單位重量價值最大的物品，成為解本題的策略邀窃。
??? 值得注意的是荸哟，貪心算法并不是完全不可以使用瞬捕，貪心策略一旦經(jīng)過證明成立后鞍历，它就是一種高效的算法肪虎。
??? 貪心算法還是很常見的算法之一劣砍，這是由于它簡單易行扇救，構(gòu)造貪心策略不是很困難刑枝。
??? 可惜的是迅腔，它需要證明后才能真正運(yùn)用到題目的算法中装畅。
??? 一般來說沧烈，貪心算法的證明圍繞著：整個問題的最優(yōu)解一定由在貪心策略中存在的子問題的最優(yōu)解得來的掠兄。
??? 對于例題中的3種貪心策略，都是無法成立（無法被證明）的徽千，解釋如下：
??? （1）貪心策略：選取價值最大者苫费。反例：
??? W=30
??? 物品：A B C
??? 重量：28 12 12
??? 價值：30 20 20
??? 根據(jù)策略双抽，首先選取物品A，接下來就無法再選取了闲礼，可是，選取B柬泽、C則更好。
??? （2）貪心策略：選取重量最小锨并。它的反例與第一種策略的反例差不多露该。
??? （3）貪心策略：選取單位重量價值最大的物品第煮。反例：
??? W=30
??? 物品：A B C
??? 重量：28 20 10
??? 價值：28 20 10
??? 根據(jù)策略解幼，三種物品單位重量價值一樣包警，程序無法依據(jù)現(xiàn)有策略作出判斷撵摆，如果選擇A害晦，則答案錯誤特铝。
五大常用算法之四：回溯法
分支限界法
一壹瘟、基本描述
類似于回溯法鲫剿，也是一種在問題的解空間樹T上搜索問題解的算法稻轨。但在一般情況下灵莲，分支限界法與回溯法的求解目標(biāo)不同澄者。回溯法的求解目標(biāo)是找出T中滿足約束條件的所有解笆呆，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解赠幕，即在某種意義下的最優(yōu)解。
?? （1）分支搜索算法
??? 所謂“分支”就是采用廣度優(yōu)先的策略询筏，依次搜索E-結(jié)點(diǎn)的所有分支，也就是所有相鄰結(jié)點(diǎn)，拋棄不滿足約束條件的結(jié)點(diǎn)逆屡，其余結(jié)點(diǎn)加入活結(jié)點(diǎn)表。然后從表中選擇一個結(jié)點(diǎn)作為下一個E-結(jié)點(diǎn)魏蔗，繼續(xù)搜索砍的。
???? 選擇下一個E-結(jié)點(diǎn)的方式不同莺治，則會有幾種不同的分支搜索方式廓鞠。
?? 1）FIFO搜索
?? 2）LIFO搜索
?? 3）優(yōu)先隊(duì)列式搜索
（2）分支限界搜索算法?
二谣旁、分支限界法的一般過程
由于求解目標(biāo)不同床佳，導(dǎo)致分支限界法與回溯法在解空間樹T上的搜索方式也不相同榄审。回溯法以深度優(yōu)先的方式搜索解空間樹T砌们，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹T搁进。
分支限界法的搜索策略是：在擴(kuò)展結(jié)點(diǎn)處浪感，先生成其所有的兒子結(jié)點(diǎn)（分支），然后再從當(dāng)前的活結(jié)點(diǎn)表中選擇下一個擴(kuò)展對點(diǎn)篮撑。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，以加速搜索的進(jìn)程匆瓜，在每一活結(jié)點(diǎn)處，計(jì)算一個函數(shù)值（限界）驮吱，并根據(jù)這些已計(jì)算出的函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)左冬，使搜索朝著解空間樹上有最優(yōu)解的分支推進(jìn)桐筏，以便盡快地找出一個最優(yōu)解拇砰。
分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹梅忌。問題的解空間樹是表示問題解空間的一棵有序樹除破，常見的有子集樹和排列樹牧氮。在搜索問題的解空間樹時瑰枫，分支限界法與回溯法對當(dāng)前擴(kuò)展結(jié)點(diǎn)所使用的擴(kuò)展方式不同踱葛。在分支限界法中，每一個活結(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)表為空時為止瓢湃。
三理张、回溯法和分支限界法的一些區(qū)別
??? 有一些問題其實(shí)無論用回溯法還是分支限界法都可以得到很好的解決绵患，但是另外一些則不然雾叭。也許我們需要具體一些的分析——到底何時使用分支限界而何時使用回溯呢落蝙？
回溯法和分支限界法的一些區(qū)別：
方法對解空間樹的搜索方式?存儲結(jié)點(diǎn)的常用數(shù)據(jù)結(jié)構(gòu)????? 結(jié)點(diǎn)存儲特性常用應(yīng)用
? 回溯法深度優(yōu)先搜索堆椫活結(jié)點(diǎn)的所有可行子結(jié)點(diǎn)被遍歷后才被從棧中彈出找出滿足約束條件的所有解
? 分支限界法廣度優(yōu)先或最小消耗優(yōu)先搜索隊(duì)列筏勒、優(yōu)先隊(duì)列每個結(jié)點(diǎn)只有一次成為活結(jié)點(diǎn)的機(jī)會找出滿足約束條件的一個解或特定意義下的最優(yōu)解
