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

《搜索深度優(yōu)先剪枝課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、教學(xué)目標(biāo)深度優(yōu)先搜索的一般步驟如何剪枝如何編程內(nèi)容要點(diǎn)復(fù)雜問題如何切入化簡思維深度優(yōu)先搜索的一般步驟寫好遞歸程序1任務(wù)：登山人選問題攀登一座高山，假定勻速前進(jìn)，從山腳登到山頂需走N天，下山也需N天。山上沒有水和食品，給養(yǎng)要靠登山隊(duì)員攜帶，而每個(gè)隊(duì)員所攜帶的給養(yǎng)量要少于他登頂再返回山腳所消耗的給養(yǎng)量。因此，一定要組成一個(gè)登山隊(duì)，在多人支援的情況下，保證有一個(gè)人登頂?，F(xiàn)在登山俱樂部有P個(gè)人待選，我們將P個(gè)人依次編號(hào)為k=1,2,…,P，令E[k]表示編號(hào)為k的人每日消耗的給養(yǎng)量，M[k]表示編號(hào)為k的人最多可攜帶的給養(yǎng)量。登山計(jì)劃要求所組成的登山隊(duì)所有成員同時(shí)

2、出發(fā)，其中一些人分別在啟程若干天后返回，最終保證出發(fā)N天后至少有一人登頂，出發(fā)2N天后所有人都已返回山腳，無人滯留山上。2編程要求：用鍵盤輸入天數(shù)N（N<10）、俱樂部人數(shù)P（P<10）之后，依次輸入E[k]和M[k]，k=1,2,…,P，分別輸出兩個(gè)登山組隊(duì)計(jì)劃，計(jì)劃1，要求參加登山的人數(shù)最少，在滿足這一條件之下消耗的總給養(yǎng)量最少。計(jì)劃2，要求消耗的總給養(yǎng)量最少。輸出的內(nèi)容是：有多少隊(duì)員參加登山，消耗的總給養(yǎng)量，在出發(fā)時(shí)每人分別攜帶多少給養(yǎng)，每人分別在出發(fā)幾天后返回（幾天后開始下山）。題目數(shù)據(jù)保證有解?！据斎敫袷健康?行為2個(gè)小于10的整數(shù)N和P,兩個(gè)整

3、數(shù)之間有一個(gè)空格。第2行為P個(gè)整數(shù)，分別是E[1],E[2],…,E[P],相鄰兩整數(shù)之間有一個(gè)空格。第3行為P個(gè)整數(shù)，分別是M[1],M[2],…,M[P],相鄰兩整數(shù)之間有一個(gè)空格。3【輸出格式】第1行到第3行為計(jì)劃1的內(nèi)容，第1行有兩個(gè)整數(shù)，前者是參加登山人數(shù)Q1，后者是消耗的總給養(yǎng)量。第2行是Q1個(gè)整數(shù)，表示Q1個(gè)人在出發(fā)時(shí)每人攜帶的給養(yǎng)。第3行是Q1個(gè)整數(shù)，表示Q1個(gè)人中的每個(gè)人在出發(fā)幾天后返回。第4行到第6行為計(jì)劃2的內(nèi)容，第4行有兩個(gè)整數(shù)，前者是參加登山人數(shù)Q2，后者是消耗的總給養(yǎng)量。第5行是Q2個(gè)整數(shù)，表示Q2個(gè)人在出發(fā)時(shí)每人攜帶的給養(yǎng)。第

4、6行是Q2個(gè)整數(shù)，表示Q2個(gè)人中的每個(gè)人在出發(fā)幾天后返回。4【輸入樣例】661222337817182225【輸出樣例】24218246333818173631輸出表明：計(jì)劃1中有2個(gè)人組隊(duì)，分別攜帶18和24的給養(yǎng)量，分別在出發(fā)6天和3天之后返回；計(jì)劃2中有3個(gè)人組隊(duì)，分別攜帶18、17和3的給養(yǎng)量，分別在出發(fā)后6天、3天和1天之后返回。5《登山人選》解題思路當(dāng)我們遇到一道難題時(shí)，先要想到：一、可不可以先從一個(gè)較簡單的情況分析起，把難度先降低一些，等從中總結(jié)出規(guī)律性的認(rèn)識(shí)后，再回到原題的要求上來；二、能不能先從一個(gè)特殊的例子分析起，再推廣到一般情況。為了

5、簡化問題，理出思路，可先將問題化簡為：每人所能攜帶的給養(yǎng)量相同，且每人每天消耗的給養(yǎng)量也相同，選擇一座不高的山，用一組人數(shù)不多的具體數(shù)據(jù)。比如有如下一組數(shù)據(jù)：N=4從山腳到山頂需4天路程P=6登山俱樂部成員人數(shù)E=1每人每天消耗的給養(yǎng)量M=5每人最多攜帶的給養(yǎng)量6為了便于分析，圖1畫出了用上述數(shù)據(jù)組隊(duì)登山的思路圖。4下返回高度11山3321222231323311上41424344山001號(hào)隊(duì)員2號(hào)隊(duì)員3號(hào)隊(duì)員4號(hào)隊(duì)員71#2#3#的支援點(diǎn)h1#2#的支援點(diǎn)1#的支援點(diǎn)432211430012345678t4人登山的高度與時(shí)間圖8在圖中，山高是以（路程）天

6、為單位的。山頂?shù)母叨仁?天的路程。在1號(hào)隊(duì)員上下山的示意圖中，每個(gè)方塊代表一天的路程，1號(hào)隊(duì)員被選中為登頂者，用4天路程上山，再用4天路程下山。如果完全自食其力的話，1號(hào)隊(duì)員需要自帶8天的給養(yǎng)，而題目限定的每人最多攜帶給養(yǎng)量M=5。因此，沒有同伴支援的話，1號(hào)隊(duì)員是無法登頂?shù)?。?號(hào)登頂后能安全下山考慮，下山只有他一個(gè)人，只能自己攜帶給養(yǎng)。因此，在做計(jì)劃時(shí)讓1號(hào)隊(duì)員上山時(shí)，從山腳（高度0）到高度3使用同伴的給養(yǎng)。過了高度3之后再吃自帶的給養(yǎng)。在圖中小方塊內(nèi)所填的數(shù)字，表示在這一天的路程中由該號(hào)隊(duì)員供應(yīng)給養(yǎng)。從圖可見1號(hào)隊(duì)員上山的第一天（從高度0至高度1）由

7、4號(hào)隊(duì)員提供給養(yǎng)；上山的第2天（從高度1至高度2）由3號(hào)隊(duì)員提供給養(yǎng)；上山的第3天（從高度2至高度3）由2號(hào)隊(duì)員提供給養(yǎng)；上山的第4天（從高度3至高度4）吃自己的給養(yǎng)；登頂成功之后，下山的4天也均自食其力。從1號(hào)隊(duì)員登頂?shù)倪^程需要2號(hào)隊(duì)員支援的情況看，1號(hào)隊(duì)員需要在第3天吃2號(hào)隊(duì)員攜帶的給養(yǎng)，這就意味著2號(hào)隊(duì)員要跟1號(hào)一起爬到高度3之后才能下山。9因此，2號(hào)隊(duì)員上山走3天，再下山走3天，自己要消耗6天的給養(yǎng)，可是自己只能攜帶5天的給養(yǎng)，當(dāng)然還需要3號(hào)支援他。可以這樣計(jì)劃：2號(hào)隊(duì)員上山時(shí)，第1天由4號(hào)隊(duì)員供給；第2天由3號(hào)隊(duì)員供給；第3天將1份給養(yǎng)支援給1號(hào)

8、隊(duì)員，自己用掉1份給養(yǎng)。到了高度3之后，用還剩下的3份給養(yǎng)安全下山