深度優(yōu)先搜索與回溯算法

深度優(yōu)先搜索與回溯算法

回溯是計(jì)算機(jī)解題中常用的算法，很多問題無法根據(jù)某種確定的計(jì)算法則來求解，可以利用搜索與回溯的技術(shù)求解。回溯是搜索算法中的一種控制策略。它的基本思想是：為了求得問題的解，先選擇某一種可能情況向前探索，在探索過程中，一旦發(fā)現(xiàn)原來的選擇是錯誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至得到解或證明無解。

如迷宮問題：進(jìn)入迷宮后，先隨意選擇一個前進(jìn)方向，一步步向前試探前進(jìn),如果碰到死胡同，說明前進(jìn)方向已無路可走，這時，首先看其它方向是否還有路可走，如果有路可走，則沿該方向再向前試探；如果已無路可走，則返回一步，再看其它方向是否還有路可走；如果有路可走，則沿該方向再向前試探。按此原則不斷搜索回溯再搜索，直到找到新的出路或從原路返回入口處無解為止。回溯法算法框架Proceduredfs(s)//訪問狀態(tài)sBeginif邊界thenbegin

判斷是否為目標(biāo)狀態(tài)；exit;end;fori：=狀態(tài)變換規(guī)則數(shù)begin si=s+規(guī)則I

保存局面 dfs（si）

還原局面end；End;【例1】設(shè)有n個整數(shù)的集合｛1,2,…,n｝，從中取出任意r個數(shù)（r<n），試列出所有的可能的情況。例如{1,2,3}，r=2。那么有3種可能，（1,2），（1,3），（2,3）【例2】任何一個大于1的自然數(shù)n，總可以拆分成若干個小于n的自然數(shù)之和。當(dāng)n=7共14種拆分方法：7=1+1+1+1+1+1+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個數(shù)擺成一個環(huán)，要求相鄰的兩個數(shù)的和是一個素?cái)?shù)?！舅惴ǚ治觥?/p>

非常明顯，這是一道回溯的題目。從1開始，每個空位有20種可能，只要填進(jìn)去的數(shù)合法：與前面的數(shù)不相同；與左邊相鄰的數(shù)的和是一個素?cái)?shù)。第20個數(shù)還要判斷和第1個數(shù)的和是否素?cái)?shù)?！纠?】八皇后問題：要在國際象棋棋盤中放八個皇后，使任意兩個皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一對角線的任意棋子。）１２３４５６７８１２３４５６７８

｜

／＼

｜

／

＼

｜

／

＼｜／

－－－▲－－－－

／｜＼

／

｜

＼

／

｜

＼

【例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,下面三種分法被認(rèn)為是相同的。

1，1，5；1，5，1；5，1，1；問有多少種不同的分法?！据斎敫袷健縩,k(6<n≤200，2≤k≤6)【輸出格式】

一個整數(shù)，即不同的分法。【輸入樣例】73【輸出樣例】4{4種分法為：1,1,5；1,2,4；1,3,3;2,2,3說明部分不必輸出}【例7】跳馬問題。在5*5格的棋盤上，有一只中國象棋的馬，從（1,1）點(diǎn)出發(fā)，按日字跳馬，它可以朝8個方向跳，但不允許出界或跳到已跳過的格子上，要求在跳遍整個棋盤。輸出前5個方案及總方案數(shù)。輸出格式示例：1

16

21

10

2520

11

24

15

2217

2

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<n)Search(i+1);elseprint();b[j]=true;}}2、找出n個自然數(shù)(1,2,3,…,n)中r個數(shù)的組合。例如，當(dāng)n=５,r=3時，所有組合為：123124125134135145234235245345total=10//組合的總數(shù)【分析】：設(shè)在b[1],b[2],…,b[i-1]中已固定地取了某一組值且b[i-1]=k的前提下，過程Search(i,k)能夠列出所有可能的組合。由于此時b[i]只能取k+1至n-r+i，對j=k+1,k+2,…,n-r+i，使b[i]:=j，再調(diào)用過程Search(i+1,j)，形成遞歸調(diào)用。直至i的值大于r時，就可以在b中構(gòu)成一種組合并輸出。3、輸出字母a、b、c、d，4個元素全排列的每一種排列。4、顯示從前m個大寫英文字母中取n個不同字母的所有種排列。5、有A、B、C、D、E五本書，要分給張、王、劉、趙、錢五位同學(xué)，每人只能選一本，事先讓每人把自已喜愛的書填于下表，編程找出讓每人都滿意的所有方案。【答案】四種方案張王劉趙錢①CABDE②DACBE③DBCAE④DECAB6、有紅球4個，白球3個，黃球3個，將它們排成一排共有多少種排法？【分析】：可以用回溯法來生成所有的排法。用數(shù)組b[1..3]表示尚未排列的這3種顏色球的個數(shù)。設(shè)共有I-1個球已參加排列，用子程序Search(i)生成由第I個位置開始的以后n-I+1位置上的各種排列。對于第I個位置，我們對3種顏色的球逐一試探，看每種顏色是否還有未加入排序的球。若有，則選取一個放在第I個位置上，且將這種球所剩的個數(shù)減1，然后調(diào)用Search(I+1),直至形成一種排列后出。對第I個位置上的所有顏色全部試探完后，則回溯至前一位置?！旧蠙C(jī)練習(xí)】1、全排列問題(Form.cpp)【問題描述】輸出自然數(shù)1到n所有不重復(fù)的排列，即n的全排列，要求所產(chǎn)生的任一數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字?！据斎敫袷健縩(1≤n≤9)【輸出格式】由1～n組成的所有不重復(fù)的數(shù)字序列，每行一個序列?！据斎霕永縁orm.in3【輸出樣例】Form.out1231322132313123212、組合的輸出(Compages.cpp)【問題描述】排列與組合是常用的數(shù)學(xué)方法，其中組合就是從n個元素中抽出r個元素(不分順序且r<＝n)，我們可以簡單地將n個元素理解為自然數(shù)1，2，…，n，從中任取r個數(shù)?，F(xiàn)要求你用遞歸的方法輸出所有組合。例如n＝5，r＝3，所有組合為：l23l24125l34l35145234235245345【輸入】一行兩個自然數(shù)n、r(1<n<21，1<＝r<＝n)?！据敵觥克械慕M合，每一個組合占一行且其中的元素按由小到大的順序排列，每個元素占三個字符的位置，所有的組合也按字典順序?！緲永縞ompages.in compages.out53123 124 125 134 135 145 234 235 245 3453、N皇后問題(Queen.cpp)【問題描述】在N*N的棋盤上放置N個皇后（n<=10）而彼此不受攻擊（即在棋盤的任一行，任一列和任一對角線上不能放置2個皇后），編程求解所有的擺放方法。八皇后的兩組解【輸入格式】

輸入：n【輸出格式】每行輸出一種方案，每種方案順序輸出皇后所在的列號，各個數(shù)之間有空格隔開。若無方案，則輸出nosolute!【輸入樣例】Queen.in4【輸出樣例】Queen.out241331424、有重復(fù)元素的排列問題【問題描述】

設(shè)R={r1,r2,…,rn}是要進(jìn)行排列的n個元素。其中元素r1,r2,…,rn可能相同。試設(shè)計(jì)一個算法，列出R的所有不同排列。【編程任務(wù)】

給定n以及待排列的n個元素。計(jì)算出這n個元素的所有不同排列?！据斎敫袷健?/p>

由perm.in輸入數(shù)據(jù)。文件的第1行是元素個數(shù)n，1≤n≤500。接下來的1行是待排列的n個元素?！据敵龈袷健?/p>

計(jì)算出的n個元素的所有不同排列輸出到文件perm.out中。文件最后1行中的數(shù)是排列總數(shù)?！据斎霕永?aacc【輸出樣例】多解aaccacacaccacaaccacaccaa65、子集和問題【問題描述】

子集和問題的一個實(shí)例為〈S,t〉。其中，S={x1，x2，…，xn}是一個正整數(shù)的集合，c是一個正整數(shù)。子集和問題判定是否存在S的一個子集S1，使得子集S1和等于c?！揪幊倘蝿?wù)】

對于給定的正整數(shù)的集合S={x1，x2，…，xn}和正整數(shù)c，編程計(jì)算S的一個子集S1，使得子集S1和等于c。【輸入格式】

由文件subsum.in提供輸入數(shù)據(jù)。文件第1行有2個正整數(shù)n和c，n表示S的個數(shù)，c是子集和的目標(biāo)值。接下來的1行中，有n個正整數(shù)，表示集合S中的元素?！据敵龈袷健?/p>

程序運(yùn)行結(jié)束時，將子集和問題的解輸出到文件subsum.out中。當(dāng)問題無解時，輸出“Nosolution!”。【輸入樣例】51022654【輸出樣例】2266、工作分配問題【問題描述】

設(shè)有n件工作分配給n個人。將工作i分配給第j個人所需的費(fèi)用為cij。試設(shè)計(jì)一個算法，為每一個人都分配一件不同的工作，并使總費(fèi)用達(dá)到最小?！揪幊倘蝿?wù)】

設(shè)計(jì)一個算法，對于給定的工作費(fèi)用，計(jì)算最佳工作分配方案，使總費(fèi)用達(dá)到最小?！据斎敫袷健?/p>

由文件job.in給出輸入數(shù)據(jù)。第一行有1個正整數(shù)n(1≤n≤20)。接下來的n行，每行n個數(shù)，第i行表示第i個人各項(xiàng)工作費(fèi)用。【輸出格式】

將計(jì)算出的最小總費(fèi)用輸出到文件job.out?！据斎霕永?425236345【輸出樣例】97、裝載問題【問題描述】

有一批共n個集裝箱要裝上艘載重量為c的輪船，其中集裝箱i的重量為wi。找出一種最優(yōu)裝載方案，將輪船盡可能裝滿，即在裝載體積不受限制的情況下，將盡可能重的集裝箱裝上輪船。【輸入格式】

由文件load.in給出輸入數(shù)據(jù)。第一行有2個正整數(shù)n和c。n是集裝箱數(shù)，c是輪船的載重量。接下來的1行中有n個正整數(shù)，表示集裝箱的重量?！据敵龈袷健?/p>

將計(jì)算出的最大裝載重量輸出到文件load.out?！据斎霕永?1072654【輸出樣例】108、字符序列(characts)【問題描述】從三個元素的集合[A，B，C]中選取元素生成一個N個字符組成的序列，使得沒有兩個相鄰字的子序列（子序列長度=2）相同。例：N=5時ABCBA是合格的，而序列ABCBC與ABABC是不合格的，因?yàn)槠渲凶有蛄蠦C，AB是相同的。對于由鍵盤輸入的N(1<=N<=12)，求出滿足條件的N個字符的所有序列和其總數(shù)。【輸入樣例】4【輸出樣例】729、試卷批分(grade)【問題描述】某學(xué)校進(jìn)行了一次英語考試，共有10道是非題，每題為10分，解答用1表示“是”，用0表示“非”的方式。但老師批完卷后，發(fā)現(xiàn)漏批了一張?jiān)嚲?，而且?biāo)準(zhǔn)答案也丟失了，手頭只剩下了3張標(biāo)有分?jǐn)?shù)的試卷。試卷一：①②③④⑤⑥⑦⑧⑨⑩0010100100得分：70試卷二：①②③④⑤⑥⑦⑧⑨⑩0111010111得分：50試卷三：①②③④⑤⑥⑦⑧⑨⑩0111000101得分：30待批試卷：①②③④⑤⑥⑦⑧⑨⑩0011100111得分：？【問題求解】：請編一程序依據(jù)這三張?jiān)嚲?，算出漏批的那張?jiān)嚲淼姆謹(jǐn)?shù)。10、迷宮問題(migong)【問題描述】設(shè)有一個N*N(2<=N<10)方格的迷宮，入口和出口分別在左上角和右上角。迷宮格子中分別放0和1，0表示可通，1表示不能，入口和出口處肯定是0。迷宮走的規(guī)則如下所示：即從某點(diǎn)開始，有八個方向可走，前進(jìn)方格中數(shù)字為0時表示可通過，為1時表示不可通過，要另找路徑。找出所有從入口（左上角）到出口（右上角）的路徑(不能重復(fù))，輸出路徑總數(shù)，如果無法到達(dá)，則輸出0?！据斎霕永?000011100【輸出樣例】2//路徑總數(shù)11、部落衛(wèi)隊(duì)【問題描述】

原始部落byteland中的居民們?yōu)榱藸帄Z有限的資源，經(jīng)常發(fā)生沖突。幾乎每個居民都有他的仇敵。部落酋長為了組織一支保衛(wèi)部落的隊(duì)伍，希望從部落的居民中選出最多的居民入伍，并保證隊(duì)伍中任何2個人都不是仇敵。【編程任務(wù)】

給定byteland部落中居民間的仇敵關(guān)系，編程計(jì)算組成部落衛(wèi)隊(duì)的最佳方案?！据斎敫袷健康?行有2個正整數(shù)n和m，表示byteland部落中有n個居民，居民間有m個仇敵關(guān)系。居民編號為1，2，…，n。接下來的m行中，每行有2個正整數(shù)u和v，表示居民u與居民v是仇敵?！据敵龈袷健康?行是部落衛(wèi)隊(duì)的頂人數(shù)；文件的第2行是衛(wèi)隊(duì)組成xi，1≤i≤n，xi=0表示居民i不在衛(wèi)隊(duì)中，xi=1表示居民i在衛(wèi)隊(duì)中?！据斎霕永?1012142423252635364556【輸出樣例】3101000112、最佳調(diào)度問題【問題描述】

假設(shè)有n個任務(wù)由k個可并