深度優(yōu)先搜索與回溯算法教學(xué)內(nèi)容.ppt

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

1、深度優(yōu)先搜索與回溯算法回溯法算法框架Proceduredfs(s)//訪問狀態(tài)sBeginif邊界thenbegin判斷是否為目標(biāo)狀態(tài)；exit;end;fori：=狀態(tài)變換規(guī)則數(shù)beginsi=s+規(guī)則I保存局面dfs（si）還原局面end；End;【例1】設(shè)有n個(gè)整數(shù)的集合｛1,2,…,n｝，從中取出任意r個(gè)數(shù)（r

2、+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1+2+27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+4total=14【例3】素?cái)?shù)環(huán):從1到n（<=20）這n個(gè)數(shù)擺成一個(gè)環(huán)，要求相鄰的兩個(gè)數(shù)的和是一個(gè)素?cái)?shù)?！舅惴ǚ治觥糠浅Ｃ黠@，這是一道回溯的題目。從1開始，每個(gè)空位有20種可能，只要填進(jìn)去的數(shù)合法：與前面的數(shù)不相同；與左邊相鄰的數(shù)的和是一個(gè)素?cái)?shù)。第20個(gè)數(shù)還要判斷和第1個(gè)數(shù)的和是否素?cái)?shù)?！纠?】八皇后問題：要在國際象棋棋盤中放八個(gè)皇后，使

3、任意兩個(gè)皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一對(duì)角線的任意棋子。）１２３４５６７８１２３４５６７８｜／＼｜／＼｜／＼｜／－－－▲－－－－／｜＼／｜＼／｜＼【例5】馬的遍歷中國象棋半張棋盤如圖4（a）所示。馬自左下角往右上角跳。今規(guī)定只許往右跳，不許往左跳。比如圖4（a）中所示為一種跳行路線，并將所經(jīng)路線打印出來。打印格式為：0,0->2,1->3,3->1,4->3,5->2,7->4,8…【例6】數(shù)的劃分(NOIP2001)【問題描述】將整數(shù)n分成k份，且每份不能為空，任意兩種分法不能相同(不考慮順序)。例如:n=7,k=3,下面

4、三種分法被認(rèn)為是相同的。1，1，5；1，5，1；5，1，1；問有多少種不同的分法?！据斎敫袷健縩,k(6

5、???19??6???912?7???4???23??143??18??13??8???5【課堂練習(xí)】1、輸出自然數(shù)1到n所有不重復(fù)的排列，即n的全排列。【參考過程】intSearch(inti){Intj;for(j=1;j<=n;j++)if(b[j]){a[i]=j;b[j]=false;if(I

6、/組合的總數(shù)【分析】：設(shè)在b[1],b[2],…,b[i-1]中已固定地取了某一組值且b[i-1]=k的前提下，過程Search(i,k)能夠列出所有可能的組合。由于此時(shí)b[i]只能取k+1至n-r+i，對(duì)j=k+1,k+2,…,n-r+i，使b[i]:=j，再調(diào)用過程Search(i+1,j)，形成遞歸調(diào)用。直至i的值大于r時(shí)，就可以在b中構(gòu)成一種組合并輸出。3、輸出字母a、b、c、d，4個(gè)元素全排列的每一種排列。4、顯示從前m個(gè)大寫英文字母中取n個(gè)不同字母的所有種排列。5、有A、B、C、D、E五本書，要分給張、王、劉、趙、錢五位同學(xué)，每人只能選

7、一本，事先讓每人把自已喜愛的書填于下表，編程找出讓每人都滿意的所有方案?！敬鸢浮克姆N方案張王劉趙錢①CABDE②DACBE③DBCAE④DECAB6、有紅球4個(gè)，白球3個(gè)，黃球3個(gè)，將它們排成一排共有多少種排法？【分析】：可以用回溯法來生成所有的排法。用數(shù)組b[1..3]表示尚未排列的這3種顏色球的個(gè)數(shù)。設(shè)共有I-1個(gè)球已參加排列，用子程序Search(i)生成由第I個(gè)位置開始的以后n-I+1位置上的各種排列。對(duì)于第I個(gè)位置，我們對(duì)3種顏色的球逐一試探，看每種顏色是否還有未加入排序的球。若有，則選取一個(gè)放在第I個(gè)位置上，且將這種球所剩的個(gè)數(shù)減1，然

8、后調(diào)用Search(I+1),直至形成一種排列后出。對(duì)第I個(gè)位置上的所有顏色全部試探完后，則回溯至前一位置?！旧蠙C(jī)練習(xí)】1