深度優(yōu)先搜索unit3課件

信奧算法提高CS101第三講課件下載地址：

走迷宮尋找一條從入口到出口的通路8123456781234567入口出口前進方向：上(北)、下(南)、左(西)、右(東)東南北西走步規(guī)則：首先從向下開始，按照逆時針方向搜索下一步可能前進的位置走迷宮棧8123456781234567(1,1)i(2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i走迷宮棧8123456781234567(1,1)i(2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i@

@

(5,2)i(5,3)i(6,3)i(6,4)i…(8,8)iiiiii走迷宮迷宮表示81234567812345670010001000100010000011000111000000010000010001000111011011000000二維數(shù)組maze[][]maze[i][j]==1表示障礙maze[i][j]==0表示道路走迷宮選擇移動方向移動方向行變化列變化0下+101右0+12上-103左0-1structGrid{introw,col;}//表示選擇方向Gridoffset[4];當(dāng)前位置(x,y)選擇方向后移動到相鄰的位置(x+offset[i].row,y+offset[i].col)走迷宮1.把迷宮的入口作為當(dāng)前位置。2.判斷當(dāng)前位置2.1

如果當(dāng)前位置是迷宮出口，那么已經(jīng)找到了一條路徑，搜索工作結(jié)束。2.2

如果當(dāng)前位置不是迷宮出口，則在當(dāng)前位置上放置障礙物，以便阻止搜索過程又繞回到這個位置。3.檢查相鄰的位置中是否有空閑的。3.1如果有，就移動到這個新的相鄰位置上，然后從這個位置開始搜索通往出口的路徑。3.2如果3.1不成功，選擇另一個相鄰的空閑位置，并從它開始搜索通往出口的路徑。3.3為了方便移動，在進入新的相鄰位置之前，把當(dāng)前位置保存在一個棧中。4.如果所有相鄰的空閑位置都已經(jīng)被探索過，并且未能找到路徑，則表明在迷宮中不存在從入口到出口的路徑。算法描述（自然語言版）走迷宮…maze.cpp演示程序走迷宮簡化版mazesimple.cpp深度優(yōu)先搜索很多問題無法根據(jù)某種確定的計算法則來求解，可以嘗試?yán)盟阉髋c回溯的技術(shù)求解?；舅枷霝榱饲蟮脝栴}的解，先選擇某一種可能情況向前探索，在探索過程中，一旦發(fā)現(xiàn)原來的選擇是錯誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復(fù)進行，直至得到解或證明無解。不撞南墻不死心WhyDFS？深度優(yōu)先搜索初始位置??死路一條死路一條??死路一條死路一條?出口死路一條搜索過程演示深度優(yōu)先搜索三類節(jié)點根節(jié)點中間節(jié)點葉子結(jié)點搜索的目標(biāo)是尋找一個特殊的葉子節(jié)點，稱為目標(biāo)，它就是問題的解深度優(yōu)先搜索的整個過程構(gòu)成了一棵樹深度優(yōu)先搜索實現(xiàn)非常簡單，按照下面的規(guī)則搜索每一個節(jié)點1.如果P是目標(biāo)節(jié)點，返回成功2.

如果P是葉子結(jié)點，返回失敗3.對當(dāng)前P節(jié)點的每個孩子節(jié)點C3.1搜索C節(jié)點3.1.1如果搜索C成功了，那么返回成功4.返回失敗基本流程解題的萬能鑰匙例題：生成排列給定n個不同的元素，輸出所有可能的排列方式

例如，對于a,b,c三個元素，全部的排列方式：abcacbbacbcacabcba例題：生成排列perm.cpp調(diào)用perm(a,0,n-1);next_permutation使用方法#include<algorithm>//頭文件boolnext_permutation(iteratorstart,iteratorend);輸出字符串的字典序排列輸出數(shù)組的字典序排列stlperm.cpp復(fù)習(xí)：素數(shù)環(huán)從1到n擺成一個環(huán)，要求相鄰的兩個數(shù)的和是一個素數(shù)。23541819187612131720910111415161-20的素數(shù)環(huán)primering.cpp復(fù)習(xí)：素數(shù)環(huán)復(fù)習(xí)：八皇后問題例題：選書期末考試，班上5名三好學(xué)生獲得獎勵，共有A，B，C，D，E五本書，每人一本。每人都有自己想要的書，在發(fā)獎之前，老師統(tǒng)計了他們的喜好。求書的分配方案，使每個學(xué)生都滿意。ABCDE甲11乙111丙11丁1X111表示想要例題：選書才5本書，暴力枚舉!可行解就是五本書的所有全排列，一共有5！=120種。然后在120種可行解中刪去不符合“每人都滿意”的解，留下的就是本題的解答。算法設(shè)計：1.產(chǎn)生5個數(shù)字的一個全排列；

2.檢查是否符合“喜愛書表”的條件，如果符合就打印出來；

3.檢查是否所有的排列都產(chǎn)生了，如果沒有產(chǎn)生完，則重復(fù)1；例題：選書可以優(yōu)化，有些排列前面位置不符合學(xué)生的喜好，后面都沒有必要生成了怎么做呢？采用深度優(yōu)先搜索從第一個學(xué)生，每次選擇喜好的書，分發(fā)后再搜索下一個學(xué)生例題：工作安排n個工人從事m項工作(m>=n)，每個工人只能做一項工作。工人做工作的收益表示為二維數(shù)組。求如何為工人安排工作，使得總收益最大？輸入第一行兩個整數(shù)n和m，分別表示工人數(shù)和工作數(shù)接下來n行，每行m列，表示工人做m項工作的收益輸出工作安排和總收益例題：工作安排n個工人從事m項工作(m>=n)，每個工人只能做一項工作。工人做工作的收益表示為二維數(shù)組。求如何為工人安排工作，使得總收益最大？輸入第一行兩個整數(shù)n和m，分別表示工人數(shù)和工作數(shù)接下來n行，每行m列，表示工人做m項工作的收益輸出工作安排和總收益例題：工作安排算法設(shè)計1.從第1個工人開始依次搜索2.從pick數(shù)組選擇還可以分配的工作，分配給當(dāng)前工人2.1記錄當(dāng)前工作分配2.2更新當(dāng)前工作方案的收益值3.當(dāng)所有工人搜索完畢，更新