搜索深度優(yōu)先剪枝.ppt

1,搜索，深度優(yōu)先 剪枝 登山計劃問題,2,教學(xué)目標 深度優(yōu)先搜索的一般步驟 如何剪枝 如何編程 內(nèi)容要點 復(fù)雜問題如何切入 化簡思維 深度優(yōu)先搜索的一般步驟 寫好遞歸程序,3,任務(wù)：登山人選問題 攀登一座高山，假定勻速前進，從山腳登到山頂需走 N天，下山也需 N天。山上沒有水和食品，給養(yǎng)要靠登山隊員攜帶，而每個隊員所攜帶的給養(yǎng)量要少于他登頂再返回山腳所消耗的給養(yǎng)量。因此，一定要組成一個登山隊，在多人支援的情況下，保證有一個人登頂。 現(xiàn)在登山俱樂部有P個人待選，我們將P個人依次編號為 k=1, 2, , P，令Ek 表示編號為k的人每日消耗的給養(yǎng)量，Mk表示編號為k的人最多可攜帶的給養(yǎng)量。登山計劃要求所組成的登山隊所有成員同時出發(fā)，其中一些人分別在啟程若干天后返回，最終保證出發(fā)N天后至少有一人登頂，出發(fā) 2N 天后所有人都已返回山腳，無人滯留山上。,4,編程要求：用鍵盤輸入天數(shù)N（N10）、俱樂部人數(shù)P（P10）之后，依次輸入Ek和Mk，k=1, 2, , P，分別輸出兩個登山組隊計劃， 計劃1，要求參加登山的人數(shù)最少，在滿足這一條件之下消耗的總給養(yǎng)量最少。 計劃2，要求消耗的總給養(yǎng)量最少。 輸出的內(nèi)容是：有多少隊員參加登山，消耗的總給養(yǎng)量，在出發(fā)時每人分別攜帶多少給養(yǎng)，每人分別在出發(fā)幾天后返回（幾天后開始下山）。題目數(shù)據(jù)保證有解。 【輸入格式】第1行為2個小于10的整數(shù)N和P, 兩個整數(shù)之間有一個空格。第2行為P個整數(shù)，分別是E1,E2,EP, 相鄰兩整數(shù)之間有一個空格。第3行為P個整數(shù)，分別是M1,M2,MP, 相鄰兩整數(shù)之間有一個空格。,5,【輸出格式】第1行到第3行為計劃1的內(nèi)容，第1行有兩個整數(shù)，前者是參加登山人數(shù)Q1，后者是消耗的總給養(yǎng)量。第2行是Q1個整數(shù)，表示Q1個人在出發(fā)時每人攜帶的給養(yǎng)。第3 行是Q1個整數(shù)，表示Q1個人中的每個人在出發(fā)幾天后返回。第4行到第6行為計劃2的內(nèi)容，第4行有兩個整數(shù)，前者是參加登山人數(shù)Q2，后者是消耗的總給養(yǎng)量。第5行是Q2個整數(shù)，表示Q2個人在出發(fā)時每人攜帶的給養(yǎng)。第6行是Q2個整數(shù)，表示Q2個人中的每個人在出發(fā)幾天后返回。,6,【輸入樣例】 6 6 1 2 2 2 3 3 7 8 17 18 22 25 【輸出樣例】 2 42 18 24 6 3 3 38 18 17 3 6 3 1 輸出表明： 計劃1中有2個人組隊，分別攜帶18和24的給養(yǎng)量，分別在出發(fā)6天和3天之后返回； 計劃2中有3個人組隊，分別攜帶18、17和3的給養(yǎng)量，分別在出發(fā)后6天、3天和1天之后返回。,7,登山人選解題思路 當我們遇到一道難題時，先要想到：一、可不可以先從一個較簡單的情況分析起，把難度先降低一些，等從中總結(jié)出規(guī)律性的認識后，再回到原題的要求上來；二、能不能先從一個特殊的例子分析起，再推廣到一般情況。 為了簡化問題，理出思路，可先將問題化簡為：每人所能攜帶的給養(yǎng)量相同，且每人每天消耗的給養(yǎng)量也相同，選擇一座不高的山，用一組人數(shù)不多的具體數(shù)據(jù)。比如有如下一組數(shù)據(jù)： N = 4 從山腳到山頂需4天路程 P = 6 登山俱樂部成員人數(shù) E = 1 每人每天消耗的給養(yǎng)量 M = 5 每人最多攜帶的給養(yǎng)量,8,為了便于分析，圖1畫出了用上述數(shù)據(jù)組隊登山的思路圖。 4 下 返回高度 1 1 山 3 3 2 1 2 2 2 2 3 1 3 2 3 3 1 1 上 4 1 4 2 4 3 4 4 山0 0 1號隊員 2號隊員 3號隊員 4號隊員,9,1#2#3#的支援點 h 1#2#的支援點 1#的支援點 4 3 2 2 1 1 4 3 0 0 1 2 3 4 5 6 7 8 t 4人登山的高度與時間圖,10,在圖中，山高是以（路程）天為單位的。山頂?shù)母叨仁?天的路程。在1號隊員上下山的示意圖中，每個方塊代表一天的路程，1號隊員被選中為登頂者，用4天路程上山，再用4天路程下山。如果完全自食其力的話，1號隊員需要自帶8天的給養(yǎng)，而題目限定的每人最多攜帶給養(yǎng)量M = 5。因此，沒有同伴支援的話，1號隊員是無法登頂?shù)?。?號登頂后能安全下山考慮，下山只有他一個人，只能自己攜帶給養(yǎng)。因此，在做計劃時讓1號隊員上山時，從山腳（高度0）到高度3使用同伴的給養(yǎng)。過了高度3之后再吃自帶的給養(yǎng)。在圖中小方塊內(nèi)所填的數(shù)字，表示在這一天的路程中由該號隊員供應(yīng)給養(yǎng)。從圖可見1號隊員上山的第一天（從高度0至高度1）由4號隊員提供給養(yǎng)；上山的第2天（從高度1至高度2）由3號隊員提供給養(yǎng)；上山的第3天（從高度2至高度3）由2號隊員提供給養(yǎng)；上山的第4天（從高度3至高度4）吃自己的給養(yǎng)；登頂成功之后，下山的4天也均自食其力。從1號隊員登頂?shù)倪^程需要2號隊員支援的情況看，1號隊員需要在第3天吃2號隊員攜帶的給養(yǎng)，這就意味著2號隊員要跟1號一起爬到高度3之后才能下山。,11,因此，2號隊員上山走3天，再下山走3天，自己要消耗6天的給養(yǎng)，可是自己只能攜帶5天的給養(yǎng)，當然還需要3號支援他。可以這樣計劃：2號隊員上山時，第1天由4號隊員供給；第2天由3號隊員供給；第3天將1份給養(yǎng)支援給1號隊員，自己用掉1份給養(yǎng)。到了高度3之后，用還剩下的3份給養(yǎng)安全下山。 同理，在計劃3號隊員的行程時，要考慮1號和2號隊員的情況：1號和2號隊員都需要在第2天得到3號隊員的支援，因此只需3號隊員上山走2天，下山走2天。3號隊員上山的第 1天使用4 號隊員支援給他的給養(yǎng)；在第 2天，3號隊員將自己攜帶的給養(yǎng)1份給1號隊員，另1份給2號隊員，自己消耗1份；走到高度2后，帶著2份給養(yǎng)下山，走2天回到山腳。 同理，計劃4號隊員的行程時，考慮前3個隊員需他支援的時間，都是在上山的第1天。因此，4號隊員只需跟著大家走1天上山，然后獨自再走1天下山。,12,定義 Hk 為隊友需對第 k 號隊員支援的高度， 對1號隊員，H1 = 3；對2號隊員，H2 = 2； 對3號隊員，H3 = 1；4號隊員不需他人支援，H4 = 0。 令 need(k) 表示 k 個人登山，保證 1人登頂所需給養(yǎng)； 令 take(k) 表示 k 個人登山共攜帶的給養(yǎng)； 令 d(k) 表示 k 個人一共差多少給養(yǎng)。 還是用圖的情況來說明上述參數(shù)的計算方法。 k = 1，讓號隊員獨自一人登山 need(1) = 2 * N = 2 * 4 = 8 take(1) = M = 5 d(1) = need(1) take(1) = 8 5 = 3 號隊員如果單槍匹馬登頂，缺3天給養(yǎng)， 因此需別人支援，要計算需隊友支援的高度 H1 = d(1) / 1 = 3,13,k = 2，讓1號隊員與2號隊員攜手登山， 2號隊員只需上到H1高度，故 need(2) = need(1) + 2 * H1 = 8 + 2 * 3 = 14 take(2) = 2 * M = 2 * 5 = 10 d(2) = need(2) take(2) = 14 10 = 4 兩個人登山共缺4份給養(yǎng)，分屬兩人，每人缺2天，故需隊友支援的高度為 H2 = d(2) / 2 = 4 / 2 = 2 k = 3，讓1號、2號和3號隊員一起登山， 3號隊員只需上到H2高度 need(3) = need(2) + 2 * H2 = 14 + 2 * 2 = 18 take(3) = 3 * M = 3 * 5 = 15 d(3) = need(3) take(3) = 18 15 = 3,14,三個人登山共缺3份給養(yǎng)，分屬三人，每人缺1天，故需隊員支援的高度為 H3 = d(3) / 3 = 1 k = 4，讓1號、2號、3號和4號組隊登山， 4號隊員只需上到H3高度 need(4) = need(3) + 2 * H3 = 18 + 2 * 1 = 20 take(4) = 4 * M = 20 d(4) = need(4) take(4) = 20 20 = 0 說明四人一起登山所需和所用相等，可以保證一人登頂，其他人也可安全返回。 我們可以將上述計算數(shù)據(jù)歸納成表1。,15,表 1 登山者 k個人所需 k個人所帶 k個人所差 對k個人需 k need(k) take(k) d(k) 支援高度 1 1# 8 5 3 3 2 1#2# 14 10 4 2 3 1# 2# 18 15 3 1 3# 4 1# 2# 20 20 0 0 3# 4#,16,以上是簡單情況下的解題思路，由于每個隊員的攜帶量與消耗量相同，所以實際上計算的是給養(yǎng)如何分配。 現(xiàn)在將難度加大到題目的要求，即要考慮每個隊員的攜帶量與消耗量各不相同的情況。沿用前面的思路，現(xiàn)在需要明確區(qū)分誰是登頂者？誰第一支援？誰第二支援？,17,在前面登山計劃的計算過程中，當挑選第k個人作為支援者時，認為他的登山高度為 Hk-1，并計算下一個支援者的登山高度為Hk，算法隱含著Hk-1Hk。因為計算過程中認為第k個人的總消耗量為2 * Hk-1* Ek， 如果Hk-1Hk的話，隊伍的總消耗量計算就不正確，從而迭代計算得到的支援高度也不正確。若第k個人剛巧獨立登至Hk-1并消耗完自帶給養(yǎng)，則前面的迭代計算將得到 Hk-1Hk，雖然實際上沒有起到支援的作用，但迭代過程的計算還是正確的。因此，在已知需支援高度為H時，并不是任選一名隊員都可作為支援者的，支援者應(yīng)保證 H * E M 。,18,可以采用深度優(yōu)先策略來搜索可能的組隊計劃。題目要求輸出不同條件下的最優(yōu)解，所以在實際搜索過程中，不一定要枚舉所有可能的登山組隊情況。例如在搜索給養(yǎng)總消耗量最小的組隊計劃時，若挑選某隊員進行支援，發(fā)現(xiàn)因此計算得到的隊伍給養(yǎng)總消耗量已經(jīng)大于之前某個成功登頂計劃的總消耗量，那就不用再枚舉之后的支援者了。,19,表2給出了題目示例數(shù)據(jù)下給養(yǎng)消耗總量最小的登山計劃的部分計算過程，相應(yīng)的搜索樹如圖2所示。在圖2中，搜索樹的根結(jié)點是虛設(shè)的，視作第0層；第1層結(jié)點表示登頂者；第2層結(jié)點表示第一支援；第3層結(jié)點表示第二支援；表2和圖2中，紅色表示該隊員無法提供支援，綠色表示找到一個當前的最優(yōu)解，粉紅色表示搜索至該隊員時進行剪枝。,20,【輸入樣例】 6 6 山高為6（天的路程） 1 2 2 2 3 3 7 8 17 18 22 25 隊員 每日消耗給養(yǎng) 自帶給養(yǎng) 1# 1 7 2# 2 8 3# 2 17 4# 2 18 5# 3 22 6# 3 25,21,登山者 k人需 k個人帶 k人差 對k人需 k need(k) take(k) d(k) 支援高度 說明 1 1# 12 7 5 5 2 1#2# 2#走不到高度5 2 1#3# 32 24 8 3 3 1#3#2# 44 32 12 3 4 1#3# 56 50 6 1 2#4# 5人組隊 5 1#3#2# 62 62 0 0 總消耗62 4#5#,22,k 登山者 need(k) take(k) d(k) 支援高度 說明 5 1#3#2# 不小于62 4#6# 62 剪枝 4 1#3# 62 不小于62 2#5# 剪枝 4 1#3# 62 不小于62 2#6# 剪枝 3 1#3#4# 44 42 2 1 4 1#3#4# 48 48 0 0 4人組隊 2# 總消耗48,23,k 登山者 need(k) take(k) d(k) 支援高度 說明 4 1#3#4#2# 48 48 0 0 48 4 1#3#4#5# 50 剪枝 4 1#3#4#6# 50 剪枝 4 1#3#5# 50 剪枝 4 1#3#6# 50 剪枝 4 1#3#4#5# 50 剪枝 2 1#4# 32 25 7 3 3 1#4#2# 44 33 11 3 4 1#4#2#3# 56 剪枝 4 1#4#2#5# 62 剪枝 4 1#4#2#6# 62 剪枝,24,k 登山者 need(k) take(k) d(k) 支援高度 說明 3 1#4#3# 44 42 2 1 4 1#4#3#5# 50 剪枝 4 1#4#3#6# 50 剪枝 3 1#4#5# 50 剪枝 3 1#4#6# 50 剪枝,25,0 登頂者 12 1 2 3 4 5 6 不可能 第1支援 2 32 3 32 4 5 6 第2支援 44 2 44 4 5 6 2 3 5 6 50 50 44 44 50 50 第3支援 4 5 6 56 62 62 2 5 6 3 5 6 3 5 6 48 50 50 56 62 62 48 50 50 第4支援 5 6 62 62,26,我們可以用遞歸來實現(xiàn)深度搜索。以搜索給養(yǎng)總消耗量最小的登山計劃為例，為了實現(xiàn)上述迭代計算過程，需要定義need、take和H數(shù)組，分別表示前k個人的登山給養(yǎng)總需求量、總攜帶量和需支援的高度，同時定義minNeed、minP、minTake和minH分別表示成功的組隊計劃中最小給養(yǎng)總消耗量、組隊人數(shù)、每人攜帶量和每人登山高度，以便保存當前最優(yōu)解用于剪枝，如下所示：,27,const int MAXP = 10; int N, P, EMAXP, MMAXP; int needMAXP = 0, takeMAXP = 0， HMAXP = 0; int minNeed = -1, minP = 0, minTakeMAXP = 0, minHMAXP = 0;,28,讀數(shù)據(jù)，可用以下函數(shù)實現(xiàn)（為了與前面的計算過程一致，我們讓數(shù)據(jù)從數(shù)組下標1開始）： void ReadData() cin N P; for (int i = 1; i Ei; for (int i = 1; i Mi; ,29,定義遞歸函數(shù) Search(int k, int dayUse) 其中k表示要挑選登山隊伍中的第k個人，dayUse表示目前隊伍每天消耗的給養(yǎng)量。為了記錄目前哪些人已被選入登山隊伍中，我們用一個數(shù)組 int whoMAXP來記錄，而數(shù)組元素的下標正好可以表示搜索樹中的層數(shù)，即表示該隊員是登頂者還是第幾號支援者。 Search函數(shù)可以實現(xiàn)如下：,30,void Search( int k, int dayUse ) if (k P) return; / 所有人均已入選，遞歸終止 for ( int i = 1; i = P; i+ ) bool bSelected = false; / 預(yù)置該隊員尚未入選 for ( int j = 1; j k; j+ ) if ( whoj = i ) bSelected = true; /記 該隊員已入選 if ( bSelected ) / 如果該隊員已入選 continue;,31,if (Hk-1 * Ei Mi) / 如果該隊員無法獨自登至高度Hk-1 continue; /換人再試 whok = i; / i#入選為第k個登山人 needk = needk-1 + 2 * Hk-1 * Ei; if (needk = minNeed) /所需太多 continue; /換人再試（剪枝） takek = takek-1 + Mi;,32,if (needk = takek) / 組隊完成，更新最優(yōu)解 /if minNeed = needk; minP = k; takek = needk; / 最后一人不必滿負荷 for ( int j = 1; j = k; j+) /for j minTakej = takej - takej-1; minHj = Hj-1; /for j /if,33,else / 需要支援 / else int d = needk - takek; / 缺的給養(yǎng)量 int dayUseNow = dayUse + Ei; / 新的每日消耗量 int w = d / dayUseNow; / 計算新的支援高度 if (w * dayUseNow = d) / dayUseNow整除d Hk = w; else Hk = w + 1; Search(k+1, dayUseNow); / 遞歸搜索下一層 / else / /,34,為了正確調(diào)用Search函數(shù)，需要先初始化有關(guān)變量，使 need0 = take0 = 0; H0 = N; minNeed = (unsigned)-1; 然后調(diào)用Search(1, 0)。如果函數(shù)調(diào)用后minNeed不等于初始值，說明搜索得到組隊計劃，可以輸出。,35,對于題目中要求的另一組隊方案，即參加登山的人數(shù)最少，且在滿足這一條件之下消耗的總給養(yǎng)量最少的組隊方案，剪枝時應(yīng)首先考慮當前參與登山的人數(shù)k是否大于minP，然后可再考慮needk是否大于minNeed。請讀者自行完成遞歸函數(shù)，同時確定函數(shù)調(diào)用前該如何初始化相關(guān)變量，函數(shù)調(diào)用后如何判斷搜索得到組隊計劃。 回顧解決這個問題的過程，在解題思路上，我們先主動降低題目難度，從簡單情況入手，等到明確題目含義，并找到規(guī)律和思路后，再回到題目要求的難度，將已有思路推廣和完善；在程序設(shè)計上，我們采用遞歸函數(shù)來實現(xiàn)深度搜索，同時采用分支定界的方法實現(xiàn)動態(tài)剪枝，從而提高搜索速度。,36,改進措施 先按獨行能力排序 隊員號 負載量 每天消耗 可獨行天數(shù) 排序 4# 18 2 9 1 3# 17 2 8.5 2 6# 25 3 8.3 3 5# 23 3 7.3 4 1# 7 1 7 5 2# 8 2 4 6,37,4# 6#上山消耗42 4#3#1#上山消耗38 24 3 4# 24 4 3# 6# 5# 1# 2# 30 1 30 2 32 3 3# 6# 5# 1# 2# 4# 6# 5# 1# 2# 42 0 42 1 42 2 48 2 48 2 6# 5# 1# 2# 3# 6# 5# 2# 4# 6# 5# 2# 42 0 42 0 38 0 40 0 38 0 42 0 42 0 38 1 44 1 50 1 50 1 44 3,38,k 登山人 k個人所需 k個人所帶 k個人所差 需支援高度 結(jié)點評價 1 4# 24 18 6 3 (24,3) 2 4#3# 36 35 1 1 (36,1) 3 4#3#6# 42 42 0 0 (42,0) 3 4#3#5# 42 42 0 0 (42,0) 3 4#3#1# 38 38 0 0 (38,0)V 3 4#3#2# 40 40 0 0 (40,0)X 2 4#6# 42 42 0 0 (42,0) V 2 4#5# 42 40 2 1 (42,1) X 2 4#1# 30 25 5 3 (30,2) 3 4#1#3# 38 38 0 0 (38,0) X 3 4#1#6# 42 42 0 0 (42,0) X 3 4#1#5# 42 42 0 0 (42,0) X 3 4#1#2# 38 33 5 2 (38,2) X,39,#include #include using namespace std; const int maxp = 10; /俱樂部人數(shù) int mimneed=1000; /最小消耗，初始化為一個大數(shù) int i,j; / 整數(shù)變量 int N,p; /整數(shù)變量 int kneed,ktake,kd,kh,kk; /整數(shù)變量,40,struct person /結(jié)構(gòu)，描述登山俱樂部的每一個人 int No; /編號 int need; /本人每日消耗 int take; /本人的攜帶量 float t; /本人可獨行天數(shù) int hh; /本人支援高度 bool flag; /入選標志，初始化 為0 clubmaxp+1,q,listmaxp+1; /結(jié)構(gòu)變量和結(jié)構(gòu)數(shù)組,41,void sort(); /排序 void display(int); /顯示輸出 void Search1(int,int,int,int); /搜索組隊方案（最小消耗） int cm(int,int); /求整數(shù)值 void ReadData(); /輸入數(shù)據(jù),42,int main() for(i=1;i=p;i+) /初始化 clubi.flag=0; /置未入隊標志 ReadData(); /輸入數(shù)據(jù) sort(); /排序 Search1(1,0,0,N); /調(diào)用搜索函數(shù) display(kk); /輸出組隊信息 return 0; ,43,void ReadData() /輸入數(shù)據(jù) cout N p; cout clubi.need; /for cout clubi.take; clubi.t=(float)clubi.tak