算法設(shè)計及分析 第五章ppt

1、第一章第一章 算法概述算法概述第二章第二章 遞歸與分治策略遞歸與分治策略第三章第三章 動態(tài)規(guī)劃動態(tài)規(guī)劃第四章第四章 貪心算法貪心算法第五章第五章 回溯法回溯法第六章第六章 分支限界法分支限界法第七章第七章 概率算法概率算法算法設(shè)計與分析算法設(shè)計與分析 目錄目錄1通用解題法通用解題法5.1 5.1 基本思想基本思想5.2 5.2 裝載問題裝載問題5.3 5.3 批處理作業(yè)調(diào)度批處理作業(yè)調(diào)度5.5 5.5 n后問題后問題5.7 5.7 最大團問題最大團問題5.8 5.8 圖的著色問題圖的著色問題算法設(shè)計與分析算法設(shè)計與分析 目錄目錄25.4 5.4 符號三角形問題符號三角形問題5.9 5.9 旅行

2、售貨員問題旅行售貨員問題5.125.12 連續(xù)郵資問題連續(xù)郵資問題3有許多問題，當需要找出它的解集或者要求有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ腔厮莘ǖ幕咀龇ㄊ撬阉魉阉鳎蚴且环N，或是一種組織得組織得井井有條井井有條的、能避免不必要搜索的的、能避免不必要搜索的窮舉式搜窮舉式搜索法索法。這種方法適用于解一些組合數(shù)相當大。這種方法適用于解一些組合數(shù)相當大的問題。的問題。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法引言4回溯法在問題的解空間樹中，按回溯法在問題的解空間

3、樹中，按深度優(yōu)先深度優(yōu)先策策略，從根結(jié)點出發(fā)搜索解空間樹。略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解：如果肯定不包含，該結(jié)點是否包含問題的解：如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。按深度優(yōu)先策略搜索。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法5應用回溯法解問題時，首先應明確定義問題的解應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應至少包含問題的一

4、個空間。問題的解空間應至少包含問題的一個(最優(yōu)最優(yōu))解。解。問題的解向量問題的解向量：回溯法希望一個問題的解能夠表示成：回溯法希望一個問題的解能夠表示成一個一個n元式元式(x1,x2,xn)的形式的形式。顯約束顯約束：對分量：對分量xi的取值限定。的取值限定。解解空間空間：對于問題的一個實例，解向量滿足顯式約束：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空間。條件的所有多元組，構(gòu)成了該實例的一個解空間。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法5.1 5.1 算法框架算法框架注意：同一個問題可以有多種表示，有些表示方法更簡單，注意：同一個問題可以有多種表示，有

5、些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可伲阉鞣椒ê唵危?。所需表示的狀態(tài)空間更?。ù鎯α可?，搜索方法簡單）。 例如例如 0-10-1背包背包問題問題 設(shè)有設(shè)有n個物體和一個背包個物體和一個背包,物體物體i的重量為的重量為wi價值價值為為vi背包的載荷背包的載荷為為C, 若將物體若將物體i(1 i n,)裝入背包裝入背包,則有價值則有價值為為vi .目標是找到一個方案目標是找到一個方案,使得能放入背使得能放入背包的物體總價值最高。包的物體總價值最高。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法有限離散問題總可以用窮舉法求得問題的全部解.61、問題的解空間、問題的解空間7算法設(shè)計與分析算法

6、設(shè)計與分析 回溯法回溯法 例如例如 取取N=3 , N=3 , C=30, w=16, 15, 15, v=45, 25, 25w=16, 15, 15, v=45, 25, 25問題問題所有可能的解為所有可能的解為(解空間解空間): (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)可表示為一棵可表示為一棵3 3層的完全正則二叉樹層的完全正則二叉樹時間復雜性時間復雜性: O(2n)子集樹子集樹對物品對物品1的選擇的選擇對物品對物品3的選擇的選擇對物品對物品2的選擇的選擇1

7、11111000000011234578111214151310698算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法旅行售貨員問題旅行售貨員問題 該問題是一個該問題是一個NP完全問題，完全問題， 有有(n-1)!條可選路線條可選路線91234206305410ABCDEFGHIJKLMNOPQ1234344342322423算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 旅行售貨員問題旅行售貨員問題 最優(yōu)解最優(yōu)解(1,3,2,4,1)(1,3,2,4,1)，最優(yōu)值，最優(yōu)值2525解空間組織成一棵樹解空間組織成一棵樹,從樹的根從樹的根結(jié)點到任意一葉結(jié)點的路徑定結(jié)點到任意一葉結(jié)點的路徑定義了圖義了圖G的一

8、條周游路線的一條周游路線排列樹排列樹10 基本步驟：基本步驟：(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法2、回溯法的基本思想、回溯法的基本思想11 生成問題狀態(tài)基本方法生成問題狀態(tài)基本方法 擴展結(jié)點：一個正在產(chǎn)生兒子的結(jié)點稱為擴展結(jié)點 活結(jié)點：一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結(jié)點 死結(jié)點：一個所有兒子已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點 回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)來處死那些實際上不可能產(chǎn)生所需解的活結(jié)點，以

9、減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法12深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結(jié)點R，一旦產(chǎn)生了它的一個兒子C，就把C當做新的擴展結(jié)點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結(jié)點，繼續(xù)生成R的下一個兒子（如果存在）寬度優(yōu)先的問題狀態(tài)生成法：在一個擴展結(jié)點變成死結(jié)點之前，它一直是擴展結(jié)點算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法13 常用剪枝函數(shù)常用剪枝函數(shù)：u用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹；u用限界函數(shù)剪去得不到最優(yōu)解的子樹。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法例如:0-1背包問題的回

10、溯法用剪枝函數(shù)剪去導致不可行解的子樹;旅行售貨員問題的回溯法中剪去不含最優(yōu)解的子樹,如果從根結(jié)點到當前擴展結(jié)點處的部分周游路線的費用已超過當前找到的最好周游線路費用,則斷定該結(jié)點的子樹不含最優(yōu)解.14 關(guān)于復雜性：關(guān)于復雜性：u搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當前擴展結(jié)點的路徑。u如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n)。u存儲解空間則需要O(2h(n)或O(h(n)!)。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法153、遞歸回溯、遞歸回溯 回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回

11、溯法。void backtrack (int t)if (tn) output(x);elsefor (int i=f(n,t);i 回溯法回溯法記錄或輸出得到的可行解記錄或輸出得到的可行解x表示在當前擴展結(jié)點處表示在當前擴展結(jié)點處的約束函數(shù)和限界函數(shù)的約束函數(shù)和限界函數(shù)表示在擴展節(jié)點表示在擴展節(jié)點處的第處的第i個可選值個可選值t:遞歸深度遞歸深度n:葉結(jié)點葉結(jié)點f:起始編號起始編號g:終止編號終止編號164、迭代回溯、迭代回溯 采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。void iterativeBacktrack ()int t=1;while (t0) if (

12、f(n,t)=g(n,t) for (int i=f(n,t);i 回溯法回溯法判斷在當前擴展節(jié)點處是否已得到可行解判斷在當前擴展節(jié)點處是否已得到可行解假設(shè)現(xiàn)在有一列數(shù)a0,a1, .an-1 如果一個問題的解的長度不是固定的，并且解和元素順序無關(guān)，即可以從中選擇0個或多個，那么解空間的個數(shù)將是為2n指數(shù)級,可以用子集樹來表示所有的解如果解空間是由n個元素的排列形成，也就是說n個元素的每一個排列都是解空間中的一個元素，那么最后解空間的組織形式是排列樹175、子集樹與排列樹、子集樹與排列樹算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法遍歷子集樹需遍歷子集樹需O(2n)計算時間計算時間 void ba

13、cktrack (int t) if (tn) output(x); else for (int i=0;i 回溯法回溯法當所給出的問題是從當所給出的問題是從n個個元素的集合元素的集合S中找到滿足中找到滿足某種性質(zhì)的子集時，解某種性質(zhì)的子集時，解空間稱為空間稱為子集樹子集樹19算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法當所給出的問題是確定當所給出的問題是確定n個元素滿足某種性質(zhì)的排個元素滿足某種性質(zhì)的排列時，解空間稱為列時，解空間稱為排列樹排列樹遍歷排列樹需遍歷排列樹需O(n!)計算時間計算時間 void backtrack (int t) if (tn) output(x); else fo

14、r (int i=t;i 回溯法回溯法 裝載問題5.2 裝載問題1.問題描述問題描述:n個集裝箱裝到個集裝箱裝到2艘載重量分別為艘載重量分別為c1, c2的貨輪的貨輪,其中集裝箱其中集裝箱i的重量為的重量為wi且且 . 問題要求找到一個合理的裝載方案可將這問題要求找到一個合理的裝載方案可將這n個貨個貨箱裝上這箱裝上這2艘輪船。艘輪船。例如例如: 當當n=3, c1=c2=50, 若若 w=10, 40, 50, 有解有解; 若若 w=20, 40, 40, 問題無解問題無解.20211ccwnii21算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 裝載問題當當 時時, ,問題等價子集和問題問題等價

15、子集和問題; ;211ccwnii采用動態(tài)規(guī)劃求解采用動態(tài)規(guī)劃求解, , 其時間復雜性為其時間復雜性為: :O(minC1, 2O(minC1, 2n n ) )若裝載問題有解若裝載問題有解, 采用如下策略可得一個最優(yōu)裝載方案采用如下策略可得一個最優(yōu)裝載方案:(1)將第一艘輪船盡可能裝滿將第一艘輪船盡可能裝滿; (2)將剩余的將剩余的貨貨箱裝到第二艘船上。箱裝到第二艘船上。將第一艘船盡可能裝滿等價于如下將第一艘船盡可能裝滿等價于如下0-l背包問題背包問題:x xi i 0,1, 10,1, 1 i i n n,max1niiixw,11cxwniii算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法

16、裝載問題裝載問題用用子集子集樹樹表示表示解空間解空間,則解為則解為n元向量元向量x1, . ,xn , x xi i 0, 10, 1 由于由于是最優(yōu)化問題是最優(yōu)化問題: 當當cwc1,該結(jié)點該結(jié)點為根為根結(jié)點的子樹都不滿足約束條件，可利用此條件進結(jié)點的子樹都不滿足約束條件，可利用此條件進一步剪去不含最優(yōu)解的子樹一步剪去不含最優(yōu)解的子樹 。 2 2、回溯、回溯算法算法思路思路22,max1niiixwcw當前裝載量當前裝載量算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 裝載問題裝載問題例如例如 n=4, c1=12, w=8, 6, 2, 3. bestw初值初值=0;23不滿足約不滿足約束條件

17、束條件 算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 裝載問題裝載問題template Type Maxloading(type w, type c, int n) loading X； /初始化初始化X X X. w=w; /集裝箱重量數(shù)組集裝箱重量數(shù)組 X. c=c; /第一艘船載重量第一艘船載重量 X. n=n；/集裝箱數(shù)集裝箱數(shù) X. bestw=0; /當前最優(yōu)載重當前最優(yōu)載重 X. cw=0;/;/當前載重量當前載重量 /計算最優(yōu)載重量計算最優(yōu)載重量 X.Backtrack(1)； return X.bestw； 算法復雜性算法復雜性: : O(2O(2n n) )24調(diào)用遞歸函數(shù)調(diào)

18、用遞歸函數(shù)Backtrack(1)實現(xiàn)回溯搜索實現(xiàn)回溯搜索25算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 裝載問題裝載問題uBacktrack(i)搜索子集樹中第搜索子集樹中第i層子樹層子樹。uin,當前擴展節(jié)點當前擴展節(jié)點Z是子集樹中的內(nèi)部結(jié)點是子集樹中的內(nèi)部結(jié)點;該該結(jié)點有以下兩種情況結(jié)點有以下兩種情況:xi=1:進入左兒子進入左兒子, cw + wj+1 c1,對左子樹遞歸對左子樹遞歸搜索搜索xi=0:進入右兒子進入右兒子,總是可行總是可行,不檢查不檢查uin時時,算法搜索至葉結(jié)點算法搜索至葉結(jié)點,其相應裝載重量其相應裝載重量為為cw,如果如果cwbestw,更新更新bestw=cw約束

19、函數(shù)約束函數(shù)26算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 裝載問題裝載問題templatevoid Loading:Backtrack(int i) / /搜索第搜索第i層結(jié)點層結(jié)點 if (in) /到達葉結(jié)點到達葉結(jié)點 if (cw bestw) bestw=cw； return； /搜索子樹搜索子樹 if (cw+wi c1c1剪枝條件剪枝條件:算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 jiiixw13、加入上界函數(shù)、加入上界函數(shù)算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 裝載問題裝載問題例如例如 n=4, c1=12, w=8, 6, 2, 3. bestw初值初值=0;28不滿足

20、上不滿足上界函數(shù)界函數(shù) template Type Maxloading(type w, type c, int n,) loading X； /初始化初始化X X X. w=w; /集裝箱重量數(shù)組集裝箱重量數(shù)組 X. c=c; /第一艘船載重量第一艘船載重量 X. n=n；/集裝箱數(shù)集裝箱數(shù) X. bestw=0; /當前最優(yōu)載重當前最優(yōu)載重 X. cw=0;/;/當前載重量當前載重量 X. r=0; ; /剩余集裝箱重量剩余集裝箱重量 for (int i=1; i 回溯法回溯法 裝載問題裝載問題30void Loading:Backtrack(int i) / /搜索第搜索第i層結(jié)點層結(jié)

21、點 if (in) /到達葉結(jié)點到達葉結(jié)點 bestw=cw; return； /搜索子樹搜索子樹 r - = wi; if (cw+wi bestw) /搜索右子樹搜索右子樹 xi=0; Backtrack(i+1)； r+=wi ; 引入上界函數(shù)引入上界函數(shù),剪去不含最剪去不含最優(yōu)解的子樹優(yōu)解的子樹,改進算法效率改進算法效率算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 裝載問題裝載問題314、構(gòu)造最優(yōu)解、構(gòu)造最優(yōu)解算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 裝載問題裝載問題增加兩個私有成員：增加兩個私有成員： x：記錄從根到當前結(jié)點的路徑：記錄從根到當前結(jié)點的路徑 int *x; bestx

22、：記錄當前最優(yōu)解：記錄當前最優(yōu)解 int *bestx;初始化：初始化： X.x=new int n+1; X.bestx=bestx;Backtrack(int i)if (i n) / 在葉節(jié)點上在葉節(jié)點上for (int j = 1; j = n; j+) bestxj = xj;/最優(yōu)解最優(yōu)解bestw = cw; return;/搜索子樹搜索子樹 if (cw+wi bestw) /搜索右子樹搜索右子樹 xi=0; Backtrack(i+1)； r+=wi; 32算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 裝載問題裝載問題算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 5.35.3 批

23、處理作業(yè)調(diào)度批處理作業(yè)調(diào)度 問題描述問題描述 給定給定n個作業(yè)的集合個作業(yè)的集合J=(1, 2, . , n)。每。每一作業(yè)一作業(yè)i 須先由機器須先由機器l處理處理, 再由機器再由機器2處理處理. 設(shè)設(shè)tji是是在機器在機器j上處理作業(yè)上處理作業(yè)i的時間的時間, i=1,.,n, j=1, 2. Fji是是 在在 機器機器j上完成作業(yè)上完成作業(yè)i的時間的時間. 所有作業(yè)在機器所有作業(yè)在機器2上上完成時間和完成時間和: f=F2i . 對于給定對于給定J, 制定一最佳作業(yè)調(diào)度方案制定一最佳作業(yè)調(diào)度方案, 使完使完成時間和最小成時間和最小.3334 問題想法問題想法 ：顯然，批處理作業(yè)的一個最優(yōu)調(diào)

24、度應使機顯然，批處理作業(yè)的一個最優(yōu)調(diào)度應使機器器1沒有空閑時間，且機器沒有空閑時間，且機器2的空閑時間最小。的空閑時間最小。 可以證明，存在一個最優(yōu)作業(yè)調(diào)度使得在機器可以證明，存在一個最優(yōu)作業(yè)調(diào)度使得在機器1和機和機器器2上作業(yè)以相同次序完成。上作業(yè)以相同次序完成。解空間解空間E=E=x1,. ,xn , x xi i 1,.n,1,.n, 約束條件約束條件: : 當當i j , xi xj (元素不能重復選取元素不能重復選取) 限界函數(shù)限界函數(shù): bestf:為當前最小完成時間和為當前最小完成時間和 f : 當前作業(yè)當前作業(yè)k的完成時間的完成時間; 當當 f bestf 時時, 將將k對應的

25、子樹剪去對應的子樹剪去 算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 作業(yè)調(diào)度int Flow(int * M, int n, int bestx ) int ub = 32767; INT_MAX Flowshop X; X.x = new int n+ 1; /當前當前調(diào)度調(diào)度 X.f2 = new intn+ l; /機器機器2的完成時間的完成時間 X.M = M; /各各作業(yè)所需處理時間作業(yè)所需處理時間 X.n= n; /作業(yè)數(shù)作業(yè)數(shù) X.bestx = bestx; /當前當前最優(yōu)調(diào)度最優(yōu)調(diào)度 X. bestf = ub; /當前當前最優(yōu)調(diào)度

26、時間最優(yōu)調(diào)度時間 X.fl = 0; /機器機器1 1完成完成處理時間處理時間 X.f = 0; /完成完成處理處理時間和時間和 for(int i = 0;i= n; i+) X.f2i = 0,X.xi=i; X. Backtrack( 1 ); delete X. x; delete X. f2; return X. bestf ;算法復雜性算法復雜性: O(n!)3536Backtrack中中: 當當in時，算法搜索至葉結(jié)點，得到一個新時，算法搜索至葉結(jié)點，得到一個新的作業(yè)調(diào)度方案，此時算法適合更新當前最優(yōu)值的作業(yè)調(diào)度方案，此時算法適合更新當前最優(yōu)值和相應的當前最佳作業(yè)調(diào)度。和相應的當

27、前最佳作業(yè)調(diào)度。 當當i 回溯法回溯法 作業(yè)調(diào)度37void Flowshop: :Backtrack(int i) if (in) for(int j = 1;j = n; j+) bestxj = xj; bestf = f; else for (int j = i; j fl)?f2i-1:fl)+Mxj2; f+= f2i; if (f 回溯法回溯法 作業(yè)調(diào)度葉結(jié)點葉結(jié)點當前擴展結(jié)點當前擴展結(jié)點限界函數(shù)限界函數(shù)385.4 符號三角形問題 一、問題描述 二、問題分析 三、算法描述算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 391、問題描述、問題描述 右圖是由右圖是由14個個“+”和和14

28、個個“-”組成的符號三角形。組成的符號三角形。2個同號個同號下面都是下面都是“+”，2個異號下面?zhèn)€異號下面都是都是“-”。 在一般情況下，符號三角形在一般情況下，符號三角形的第一行有的第一行有n個符號。個符號。 符號三角形問題要求對于給符號三角形問題要求對于給定的定的n，計算有多少個不同的計算有多少個不同的符號三角形，使其所含的符號三角形，使其所含的“+”和和“-”的個數(shù)相同。的個數(shù)相同。+ + - + - + + - - - - +- + + + - - + + - - + - - - +算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 402、問題分析、問題分析l 定義：用定義：用n元組元組x1

29、:n表示符號三角形的第一行。表示符號三角形的第一行。 當當xi=1,表示符號三角形的第一行的第表示符號三角形的第一行的第i個符號為個符號為“+”當當xi=0,表示符號三角形的第一行的第表示符號三角形的第一行的第i個符號為個符號為“-”l使用回溯法解決符號三角形問題使用回溯法解決符號三角形問題用一棵完全二叉樹表示其解空間用一棵完全二叉樹表示其解空間.算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 子樹子樹集集41 可行性約束函數(shù)可行性約束函數(shù)：當前符號三角形所包含的當前符號三角形所包含的“+”個數(shù)與個數(shù)與“-”個數(shù)個數(shù)均不超過均不超過n*(n+1)/4 無解的判斷無解的判斷：n*(n+1)/2為奇數(shù)

30、為奇數(shù) 復雜度分析：復雜度分析：計算可行性約束需要計算可行性約束需要O(n)時間，在最時間，在最壞情況下有壞情況下有 O(2n)個結(jié)點需要計算可行性約束，故解個結(jié)點需要計算可行性約束，故解符號三角形問題的回溯算法所需的計算時間為符號三角形問題的回溯算法所需的計算時間為 O(n2n)。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 三角形中三角形中+-號總號總數(shù)為數(shù)為n(n+1)/242P1:tp2tp3t-1p1t+1算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 說明：說明：符號三角形距陣定義為符號三角形距陣定義為*p；已知深度已知深度t的三角形距陣的三角形距陣P1:t，只需要確定，只需要確定p1t

31、+1的的值，就能在已確定的三角形的右邊加一條邊擴展值，就能在已確定的三角形的右邊加一條邊擴展P1:t+1433、算法描述、算法描述void Triangle:Backtrack(int t) if (counthalf)|(t*(t-1)/2-counthalf) return; /加或減號個數(shù)大于符號總數(shù)的一半 if (tn) sum+; /找到一個符合條件的三角形 else for (int i=0;i2;i+) /i=1 為為”+”，i=0為為”-” p1t=i; count+=i; for (int j=2;j=t;j+) pjt-j+1=pj-1t-j+1pj-1t-j+2; cou

32、nt+=pjt-j+1; Backtrack(t+1); for (int j=2;j 回溯法回溯法 n:第一行符號個數(shù)第一行符號個數(shù)half:為為n(n+1)/4count:“+”個數(shù)個數(shù)*p:符號三角矩陣符號三角矩陣sum:符號三角形數(shù)符號三角形數(shù)計算新增的最計算新增的最后一斜列的后一斜列的+和和 - 號 個 數(shù)號 個 數(shù)44八八皇后問題是十九世紀著名的數(shù)學家高斯于皇后問題是十九世紀著名的數(shù)學家高斯于1850年提年提出的出的。問題：問題：在在88的棋盤上擺放八個皇后，使其不能互相的棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同攻擊，即任意兩個皇后都不能處于

33、同一行、同一列或同一斜線上一斜線上。把把八皇后問題擴展到八皇后問題擴展到n皇后問題，即在皇后問題，即在nn的棋盤上擺的棋盤上擺放放n個皇后，使任意兩個皇后都不能處于同一行、同一列個皇后，使任意兩個皇后都不能處于同一行、同一列或同一斜線上?；蛲恍本€上。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法5.5 八皇后問題八皇后問題 451 2 3 41234皇后皇后1皇后皇后2皇后皇后3皇后皇后4圖圖 四皇后問題四皇后問題四四皇后皇后問題問題四皇后問題的解空間樹是一個完全4叉樹樹的根結(jié)點表示搜索的初始狀態(tài)從根結(jié)點到第2層結(jié)點對應皇后1在棋盤中第1行的可能擺放位置，從第2層結(jié)點到第3層結(jié)點對應皇后2在棋盤

34、中第2行的可能擺放位置，依此類推。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法46想法想法: :棋盤棋盤的每一行上可以而且必須擺放一個皇后，的每一行上可以而且必須擺放一個皇后，所以，所以，n皇后問題的可能解用一個皇后問題的可能解用一個n元向量元向量X=(x1, x2, , xn)表示，其中，表示，其中，1in并且并且1xin，即第，即第i個皇個皇后放在第后放在第i行第行第xi列上。列上。由于由于兩個皇后不能位于同一列上，所以，解向量兩個皇后不能位于同一列上，所以，解向量X必須滿足約束條件：必須滿足約束條件： xixj算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法皇后皇后i,j不在同一列上不在同一列上

35、47若若兩個皇后擺放的位置分別是兩個皇后擺放的位置分別是(i, xi)和和(j, xj)，在在棋盤上斜率為棋盤上斜率為-1的斜線上，滿足條件的斜線上，滿足條件ij= xixj，在在棋盤上斜率為棋盤上斜率為1的斜線上，滿足條件的斜線上，滿足條件ij= xixj，綜合綜合兩種情況，由于兩個皇后不能位于同一斜線上，兩種情況，由于兩個皇后不能位于同一斜線上，所以，解向量所以，解向量X必須滿足約束條件：必須滿足約束條件： | |ixi| | |jxj| |算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法皇后皇后i,j不在同一斜線上不在同一斜線上48算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法算法：回溯法求解算法

36、：回溯法求解n皇后問題皇后問題1. 初始化解向量初始化解向量xn=-1;2. k=1;3. while (k=1)3.1 把皇后擺放在下一列位置，把皇后擺放在下一列位置，xk+;3.2 從從xk開始依次考察每一列，如果不發(fā)生沖突，則轉(zhuǎn)向開始依次考察每一列，如果不發(fā)生沖突，則轉(zhuǎn)向步驟步驟3.3；否則；否則xk+試探下一列；試探下一列；3.3 若若n個皇后已全部擺放，輸出一個解，個皇后已全部擺放，輸出一個解，結(jié)束；結(jié)束；3.4 若尚有皇后沒擺放，則若尚有皇后沒擺放，則k+,轉(zhuǎn)向步驟轉(zhuǎn)向步驟3,擺放下一皇后；擺放下一皇后；3.5 若若xk出界，則回溯：出界，則回溯：xk=-1,k-; 轉(zhuǎn)步驟轉(zhuǎn)步驟3

37、重新擺放重新擺放k皇后；皇后；4. 退出循環(huán)，退出循環(huán)，無解。無解。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 最大團問題 最大團問題的回溯算法最大團問題的回溯算法int MaxClique(int * a, int vi,int n) Clique Y;Y.x = new int n+l;Y.a= a; /圖圖G G的鄰接矩陣的鄰接矩陣Y.n= n; /圖圖G G頂點數(shù)頂點數(shù)Y.cn = 0; /當前團頂點數(shù)當前團頂點數(shù)Y.bestn=0; /當前最大團頂點數(shù)當前最大團頂點數(shù)Y.bestx = v; /當前最優(yōu)解當前最優(yōu)解Y. Backtrack( 1 );delete Y. x;retur

38、n Y. bestn； 49void clique:Backtrack(int i) if (in) /找到更大團找到更大團,更新更新 for (int j=1; j=n；j+) bestxj = xj; bestn = cn; return; /檢查頂點檢查頂點i是否與當前團相連是否與當前團相連 int OK = 1; /滿足加入團的條件滿足加入團的條件 for(int j =1; j bestn) /剪右枝條件，否則向右枝遞歸剪右枝條件，否則向右枝遞歸 Xi=0；Backtrack(i + 1);設(shè)設(shè)當前擴展節(jié)當前擴展節(jié)點點Z Z位于解空間位于解空間樹的第樹的第i i層，層，在在進入左子樹

39、進入左子樹之前，必須確之前，必須確認從頂點認從頂點i i到已到已入選的頂點集入選的頂點集中每一個頂點中每一個頂點都有邊相連。都有邊相連。在在進入右子樹進入右子樹之前，必須確之前，必須確認還有足夠多認還有足夠多的可選擇的頂?shù)目蛇x擇的頂點使算法有可點使算法有可能在右子樹中能在右子樹中找到更大的團。找到更大的團。復雜度分析：復雜度分析：回溯算法回溯算法backtrack所所需的計算時間需的計算時間顯然為顯然為O(n2n)。算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 著色問題著色問題圖的圖的m色判定問題色判定問題: 給定無向連通圖給定無向連通圖G和和m種顏色。用種顏色。用這些顏色為圖這些顏色為圖G的各

40、的各頂點著色頂點著色. 問是否存在著色方法問是否存在著色方法, 使得使得G中任中任2鄰接點有不同顏色鄰接點有不同顏色。圖的圖的m色優(yōu)化問題色優(yōu)化問題:給定無向連通圖給定無向連通圖G,為圖為圖G的各頂點的各頂點著色著色, 使圖中任使圖中任2鄰接點著不同顏色鄰接點著不同顏色,問最少需要幾種顏問最少需要幾種顏色色。所需的最少顏色的數(shù)目所需的最少顏色的數(shù)目m稱為該圖的稱為該圖的色數(shù)色數(shù)。5.8 圖的圖的m m著色問題著色問題 問題描述5152可平面圖：可平面圖：如果一個圖得所有頂點和邊都能用某種如果一個圖得所有頂點和邊都能用某種方式畫在平面上，且沒有任何兩面相交，則稱這個方式畫在平面上，且沒有任何兩面

41、相交，則稱這個圖為可平面圖。圖為可平面圖。4 4色定理：色定理：若圖若圖G是可平面圖是可平面圖,則它的色數(shù)不超過則它的色數(shù)不超過4色色4 4色定理的應用色定理的應用: :在一個平面或球面上的任何地圖能在一個平面或球面上的任何地圖能夠只用夠只用4種顏色來著色種顏色來著色使得使得相鄰的國家在地圖上著相鄰的國家在地圖上著有不同顏色有不同顏色4321512345算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 著色問題著色問題a).將將G的結(jié)點按照的結(jié)點按照度數(shù)遞減度數(shù)遞減的次序排列的次序排列. b).用用第一種顏色對第一個結(jié)點著色第一種顏色對第一個結(jié)點著色,并按照結(jié)點并按照結(jié)點排列的排列的次序?qū)Υ涡驅(qū)εc前

42、面著色點不鄰接的每一點著以與前面著色點不鄰接的每一點著以相同顏色相同顏色.c).用用第二種顏色對尚未著色的點重復步驟第二種顏色對尚未著色的點重復步驟b).用用第三種第三種顏色繼續(xù)顏色繼續(xù)這種作法這種作法, 直到所有點著色完為直到所有點著色完為止止. 任意圖的著色任意圖的著色Welch PowellWelch Powell法法算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 著色問題著色問題53算法設(shè)計與分析算法設(shè)計與分析 回溯法回溯法 著色問題著色問題u設(shè)圖設(shè)圖G=(V, E), |V|=n, 顏色數(shù)顏色數(shù)= m, 用鄰接矩陣用鄰接矩陣a表表示示G, 用整數(shù)用整數(shù)1, 2m來來表示表示m種不同的顏色

43、。頂點種不同的顏色。頂點i所著的顏色用所著的顏色用xi表示。表示。u問題的解向量可以表示為問題的解向量可以表示為n元組元組x= x1,.,xn . xi 1,2,.,m,u解空間樹為解空間樹為排序樹排序樹,是一棵是一棵n+1層的完全層的完全m叉樹叉樹.u約束條件約束條件: xi xj, 如果如果aji=1. (如果兩點相如果兩點相鄰鄰,不能著同色不能著同色)算法思路54算法設(shè)計與算法設(shè)計與分析分析 回溯法回溯法 著色問題著色問題 int mColoring(int n, int m, int *a ) Color X； /初始化X Xn=n； /圖的頂點數(shù) Xm=m /可用顏色數(shù) Xa=a； /圖的鄰接矩陣 XSum=0; /已找到的著色方案數(shù) int*p=new int n+1； for (int i=0；i=n；i+) p