課前視頻學(xué)習(xí)任務(wù)2.3.1回溯法-八皇后問題（時(shí)長(zhǎng)：12分22秒）2.3.2回溯法-01背包問題（時(shí)長(zhǎng)：6分31秒）課前樣例學(xué)習(xí)任務(wù)Ex2.3八皇后問題Ex2.40-1背包問題課堂測(cè)試（5分鐘）課堂討論課堂討論討論1：八皇后問題主要解題過程問題引入八皇后問題，是一個(gè)古老而著名的問題，是回溯算法的典型案例。該問題是國(guó)際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結(jié)果。計(jì)算機(jī)發(fā)明后，有多種計(jì)算機(jī)語(yǔ)言可以解決此問題。基本思路回溯法基本思路：2.第二行再放一個(gè)且不能與第一個(gè)皇后相互攻擊3.第三行再放一個(gè)

。。。。。n.第n行放一個(gè)，當(dāng)?shù)趎行放不下的時(shí)候，取消n-1行的皇后，在原第n-1皇后的下一個(gè)位置重新放一個(gè)皇后，直到放到最n-1行的最后一個(gè)位置，當(dāng)還不行的時(shí)候，就取消第n-2行，……當(dāng)n-2行的皇后在n-2行的最后一個(gè)位置的時(shí)候，就取消n-3(n-2在最后一個(gè)位置，那么n-3行的一定不在最后一個(gè)位置)。再重新尋找n-2行的皇后的位置。

。。。。。

。。。。。直到找到最后一個(gè)皇后。1.第一行先放一個(gè)皇后課堂討論回溯法基本思路：找完第一種解法，重新開始尋找第二種解法，直接第一個(gè)皇后放在第一行的第2個(gè)位置，尋找第三種解法時(shí)首先在第一行的第3個(gè)位置放第一個(gè)皇后。。。。直到尋找第n個(gè)解法。課堂討論詳細(xì)步驟：1.判斷新的皇后是否與已經(jīng)存在的皇后互相攻擊，加入是第一個(gè)則不用判斷直接加入。第1個(gè)皇后課堂討論詳細(xì)步驟：2.第二行新生成的皇后，然后與第一行判斷是否攻擊，是的話，向右移動(dòng)一個(gè)格子，否則添加上去。第2個(gè)皇后課堂討論詳細(xì)步驟：3.第三行從左至右從第一個(gè)格子開始，判斷是否與上面所有的皇后相互攻擊，是的話，向右移動(dòng)一個(gè)格子，否則添加上去。第3個(gè)皇后課堂討論詳細(xì)步驟：3.第三行從左至右從第一個(gè)格子開始，判斷是否與上面所有的皇后相互攻擊，是的話，向右移動(dòng)一個(gè)格子，否則添加上去。第3個(gè)皇后。。。

。。。課堂討論詳細(xì)步驟：8.到第八行，新生成一個(gè)皇后，判斷是否與上面所有的皇后相互攻擊，沒有則添加。有則向右移動(dòng)一個(gè)格子。當(dāng)移動(dòng)至一個(gè)不相互攻擊的格子，則一個(gè)解法已經(jīng)生成。向后則尋找第二個(gè)方案，將第8行的皇后刪除，新生成的皇后在剛才最后一個(gè)皇后的右邊，為什么在右邊呢？因?yàn)樽筮厔偛乓呀?jīng)判斷過都失敗了，所以新生成的在右邊，然后在判斷是否與上邊的皇后相互攻擊。課堂討論詳細(xì)步驟：9.當(dāng)向右移動(dòng)最后一個(gè)格子而且與上邊的皇后相互攻擊，則刪除掉此皇后，然后把上一行的皇后向右移動(dòng)一個(gè)格子，第8行從左向右從0開始生成一個(gè)新的皇后。然后步驟8.課堂討論詳細(xì)步驟：10.直到第一行的皇后走到第一行的最后一個(gè)，第二行也找到最后一個(gè)格子的皇后，而且失敗，則是所有解法都尋找完成。課堂討論回溯法基本思路：012300000100002000030000課堂討論討論2：0-1背包問題主要解題過程問題描述給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問:應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?使用典型的三種物品為例，問題描述如下：設(shè)有三個(gè)物品，其重量、價(jià)值分別如右表所示；請(qǐng)選擇物品放入背包，使背包中物品總重量不超過30，但價(jià)值最大。重量?jī)r(jià)值物品11645物品21525物品31525課堂討論討論2：0-1背包問題主要解題過程每個(gè)物品都可以被選擇中（1）或者不選（0），理論上如果不加任何限制的話一共有八種可能（2×2×2），但在搜索的過程中要時(shí)刻注意總重量不可超過30，在這個(gè)基礎(chǔ)上使其總價(jià)值最大?？梢詮牡谝粋€(gè)物品開始，先選中它，其重量是16，小于30，沒有問題，然后在選擇第二個(gè)物品，其重量為15，二者總重量為31，超過30，所以不能選擇第二個(gè)物品，同理第三個(gè)物品也不能選，也就是說在選中第一個(gè)物品的前提下，另外兩個(gè)物品就都不能再選了，這是八種理論可能情況中的一種；以此類推，不選第一個(gè)物品，在此基礎(chǔ)上選擇第二個(gè)物品，總重量為15，沒有問題，再選第三個(gè)，此時(shí)總重量為30，也沒有問題；對(duì)照這兩種情況，前者總價(jià)值為45，后者總價(jià)值為50課堂討論討論2：0-1背包問題主要解題過程對(duì)于上述的物品問題，在此二叉樹結(jié)構(gòu)中可以簡(jiǎn)單地理解為：從A出發(fā)，往左子樹方向走說明選中了A，往右子樹方向走說明沒有選中A，即“左選右不選”，落實(shí)到上圖中就是1代表選中0代表未選中；上述的第一種情況，即只選中第一個(gè)物品的情況對(duì)應(yīng)上圖的A->B->E->K；

當(dāng)搜索路徑到達(dá)K后，得到了一組值，即總重量為16，總價(jià)值為45，此時(shí)，由于已經(jīng)到了樹的葉子結(jié)點(diǎn)，因此需要回溯直到根，再繼續(xù)進(jìn)行后續(xù)的搜索；在后續(xù)搜索過程中，一方面要進(jìn)行結(jié)點(diǎn)的判斷，另一方面，一旦得到了一個(gè)合符要求的價(jià)值，則與前一次搜索所得到的結(jié)果進(jìn)行比較，如果比前一次搜索得到的值大，則取代，反之，繼續(xù)搜索直到整個(gè)樹搜索結(jié)束所得到的最大值即為問題的解。例：n=3，C=20，(v1,v2,v3)=(45,25,2)，(w1,w2,w3)=(12,7,7)，求X=(x1,x2,x3)使背包價(jià)值最大？ABFGHJLKMNOx1=1x1=0x2=1x2=0x3=1x3=0x3=1x3=0x2=1x2=0x3=1x3=0x3=1x3=0當(dāng)前最優(yōu)價(jià)值當(dāng)前背包剩余容量當(dāng)前剩余價(jià)值當(dāng)前背包價(jià)值045+25+2=72200027845C45272000+27<45，剪枝D4521704570A70284545+2<70，剪枝1<7，不可達(dá)I700170課堂討論討論2：0-1背包問題主要解題過程整體思路01背包屬于找最優(yōu)解問題，可用回溯法需要構(gòu)造解的子集樹。對(duì)于每一個(gè)物品i，對(duì)于該物品只有選與不選2個(gè)決策，總共有n個(gè)物品，可以順序依次考慮每個(gè)物品，這樣就形成了一棵解空間樹：

基本思想就是遍歷這棵樹，以枚舉所有情況，最后進(jìn)行判斷，如果重量不超過背包容量，且價(jià)值最大的話，該方案就是最后的答案。

在搜索狀態(tài)空間樹時(shí)，只要左子節(jié)點(diǎn)是可一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入其左子樹。對(duì)于右子樹時(shí)，先計(jì)算上界函數(shù)，以判斷是否將其減去（剪枝）。上界函數(shù)bound():當(dāng)前價(jià)值cw+剩余容量可容納的最大價(jià)值<=當(dāng)前最優(yōu)價(jià)值bestp。

為了更好地計(jì)算和運(yùn)用上界函數(shù)剪枝，選擇先將物品按照其單位重量?jī)r(jià)值從大到小排序，此后就按照順序考慮各個(gè)物品。課堂討論討論2：0-1背包問題主要解題過程整體思路01背包屬于找最優(yōu)解問題，可用回溯法需要構(gòu)造解的子集樹。對(duì)于每一個(gè)物品i，對(duì)于該物品只有選與不選2個(gè)決策，總共有n個(gè)物品，可以順序依次考慮每個(gè)物品，這樣就形成了一棵解空間樹：

基本思想就是遍歷這棵樹，以枚舉所有情況，最后進(jìn)行判斷，如果重量不超過背包容量，且價(jià)值最大的話，該方案就是最后的答案。

課堂討論討論2：0-1背包問題主要解題過程整體思路

在搜索狀態(tài)空間樹時(shí)，只要左子節(jié)點(diǎn)是可一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入其左子樹。當(dāng)右子樹中有可能包含最優(yōu)解時(shí)才進(jìn)入右子樹搜索；否則將右子樹剪去。設(shè)r是當(dāng)前剩余物品價(jià)值總和；cp是當(dāng)前價(jià)值；bestp是當(dāng)前最優(yōu)價(jià)值。當(dāng)cp+r<=bestp時(shí)，可剪去右子樹。計(jì)算右子樹中解的上界的更好方法是將剩余物品依其單位重量?jī)r(jià)值排序，然后依次裝入物品，直至裝不下時(shí)，再裝入該物品的一部分而裝滿背包；由此得到的價(jià)值是右子樹中解的上界。為了便于計(jì)算上界，可先將物品依其單位重量?jī)r(jià)值從大到小排列，此后只要按順序考察各物品即可。課堂討論討論2：0-1背包問題主要解題過程整體思路-0-1背包問題的解空間可用子集樹表示。在搜索解空間樹時(shí)，只要其左兒子結(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹。當(dāng)右子樹中有可能包含最優(yōu)解時(shí)才進(jìn)入右子樹搜索。否則將右子樹剪去。設(shè)r是當(dāng)前剩余物品價(jià)值總和；cp是當(dāng)前價(jià)值；bestp是當(dāng)前最優(yōu)價(jià)值。當(dāng)cp+r<=bestp時(shí)，可剪去右子樹。計(jì)算右子樹中解的上界的更好方法是將剩余物品依其單位重量?jī)r(jià)值排序，然后依次裝入物品，直至裝不下時(shí)，再裝入該物品的一部分而裝滿背包。由此得到的價(jià)值是右子樹中解的上界。為了便于計(jì)算上界，可先將物品依其單位重量?jī)r(jià)值從大到小排列，此后只要按順序考察各物品即可。應(yīng)用實(shí)例—0-1背包問題解空間：子集樹可行性約束函數(shù)：上界函數(shù)：template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound(inti){//計(jì)算上界,剪枝依據(jù)。

Typewcleft=c-cw;//剩余容量

Typepb=cp;//以物品單位重量?jī)r(jià)值遞減序裝入物品

while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//裝滿背包

if(i<=n)b+=p[i]/w[i]*cleft;returnb;}裝載問題的上界函數(shù)為當(dāng)前載量cp+剩余集裝箱重量r<=當(dāng)前最優(yōu)裝載量bestp;對(duì)于0-1背包問題，更好的上界為：當(dāng)前價(jià)值cw+剩余容量可容納的最大價(jià)值<=當(dāng)前最優(yōu)價(jià)值bestp。樣例代碼回顧樣例程序回顧Ex2.3八皇后問題參考代碼：/p/7PfVgwz7WM/樣例程序回顧Ex2.40-1背包問題參考代碼：/p/GrDWVVVsW2/作業(yè)（三選一）解題思路習(xí)題1：*迷宮問題。如圖所示，迷宮可以用一個(gè)矩陣表示，迷宮中有一個(gè)入口、一個(gè)出口，迷宮內(nèi)有通道，也有墻，迷宮中行走時(shí)可以從當(dāng)前位置的上、下、左、右四個(gè)方向的通道通過。迷宮中的通道和墻可以用矩陣中元素0和1表示，編寫程序，輸入迷宮矩陣和入口、出口位置，找到一條從入口到出口的路徑，沒有這樣的路徑時(shí)，提示迷宮設(shè)置有問題。解題思路：迷宮數(shù)據(jù)可存放在文件里，可采用試探回溯法（深度優(yōu)先策略）找出入口到出口的一條路徑（或所有路徑），為避免重復(fù)經(jīng)過，可設(shè)置經(jīng)過標(biāo)記。本題也可采用廣度優(yōu)先策略，分別求出經(jīng)過1、2、3...n步可以到達(dá)的位置，最后可求出最短路徑或判斷出不存在這樣的路徑。附加拓展選項(xiàng)：用圖形化方法顯示迷宮和動(dòng)態(tài)搜索過程，圖形庫(kù)可參考第8章采用MFC、QT或其他簡(jiǎn)易圖形庫(kù)。習(xí)題2：排列組合問題之排列部分。編寫程序，輸入正整數(shù)n（n<10），輸出由1、2、3...n組成的所有排列，統(tǒng)計(jì)并輸出所有排列。解題思路：采用回溯法實(shí)現(xiàn)。先將1、2、3...n放入一個(gè)線性表中，如果已試探取出整數(shù)個(gè)數(shù)達(dá)到要求，則輸出一種排列；否則，依次循環(huán)取出線性表中剩余數(shù)中一個(gè)，再遞歸處理剩余數(shù)的排列問題。注意，回溯時(shí)，試探取出的數(shù)需放回線性表原先位置，恢復(fù)未取狀態(tài)。習(xí)題3：

排列組合問題之組合部分。某單位有若干人員，現(xiàn)執(zhí)行某任務(wù)需要一定人數(shù)人員。編寫程序，輸入單位總?cè)藬?shù)和每位員工名字，再輸入執(zhí)行任務(wù)所需人數(shù)，輸出所有可能派出人員方案，統(tǒng)計(jì)并輸出方案數(shù)。派出人員方案中，先輸入人員排在前面，后輸入人員排在后面。解題思路：假設(shè)單位總?cè)藬?shù)為n，需要派出人員數(shù)為m，可將單位人員依次編號(hào)為1、2、3...n，這實(shí)際是組合問題，同樣可以采用回溯法實(shí)現(xiàn)。先將1、2、3...n放入一個(gè)線性表中，如果已試探取出整數(shù)個(gè)數(shù)達(dá)到要求m，則輸出一種組合；否則，依次循環(huán)取出線性表中剩余數(shù)中一個(gè)，這里取出的數(shù)必須大于方案中前面已取出數(shù)，再遞歸處理剩余數(shù)的組合問題。注意，回溯時(shí)，試探取出的數(shù)需放回線性表原先