02年05月09日回溯策略與遞歸

1、第七章簡(jiǎn)單的回溯與遞歸回溯需要用計(jì)算機(jī)解決的問題一般有兩種類型：(1) 可以用精確的數(shù)學(xué)公式或明確的算法語(yǔ)言來描述的問題。(2) 在完成一件事情的過程中，要經(jīng)過若干個(gè)步驟，而每一個(gè)步驟都有若干種可能的分支，為了圓滿地完成任務(wù)，須遵守一些規(guī)則，而這些規(guī)則又無法精確地用數(shù)學(xué)公式來描述。對(duì)于第二類問題，一般采用搜索的方法來解決。回溯是搜索算法中的一種控制策略。它的基本過程中，由于求解失敗。為擺脫當(dāng)前是：在搜索狀態(tài)，返回搜索步驟中的上一個(gè)結(jié)點(diǎn)，并重新尋求解答。以闖迷宮為例，進(jìn)入迷宮后，先隨意選擇一個(gè)前進(jìn)方向，一步步向前試探前進(jìn)，如果碰到死胡同，說明前進(jìn)方向已無路可走，這時(shí)，首先看其它方向是否還有路可走

2、，如果有路可走，則沿該方向再向前試探；如果無路可走，則回撤一步，再看其他方向是否還有路可走。如果有路可走，則沿該方向再向前試探；如果無路可走，則回撤一步，再看其他方向是否有路可走。按此原則不斷搜索，直到找到新的出路或從原路返回處。探索迷宮時(shí)，為都要設(shè)置一些標(biāo)記，了不迷失方向，例如，在走過的進(jìn)與回撤的鋪一條線，遇到死胡同返回時(shí)再鋪上一條線。這樣，就可以判斷哪條路是已經(jīng)過過的，哪條路是沒走過的，哪條路是死胡同。根據(jù)這些信息，就能正確的找到迷宮的出口，在搜索過程中也能正確地找到應(yīng)返回的位置，并避免重新進(jìn)入死胡同。見圖 71。回溯是計(jì)算機(jī)的重要算法之一。許多涉及搜索問題的求解過程都要用到回溯探索的控制

3、策略。如：八皇后問題，馬的環(huán)游問題以及穩(wěn)定的實(shí)例來介紹回溯的例 1八皇后問題。問題等。下面，通過一些具體與在計(jì)算機(jī)上實(shí)現(xiàn)的基本方法。問題的由來：國(guó)際象棋是人發(fā)明的一種二人對(duì)弈棋，它的棋盤是由 8×8 個(gè)黑白相間的方格組成。雙方各有一個(gè)國(guó)王、一個(gè)皇后、兩個(gè)車、兩個(gè)馬、兩今象、八個(gè)兵，共個(gè)棋子。皇后是所有棋子中最大的一個(gè)子，根據(jù)國(guó)際象棋的規(guī)則，她橫走、豎走、斜走均可，且格數(shù)不限。因此，若在某二方格內(nèi)放置了一個(gè)皇后，那么，她所在的行、列以及斜線上的子都可以被她。八皇后問題是一個(gè)有趣的獨(dú)弈問題，是由德國(guó)大數(shù)學(xué)家高斯(Gauss，17771855 年)于 1850 年首先。要求在國(guó)際象棋的棋盤

4、上放置八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后不能處在同一行、同一列、同一條斜線上。問有多少種擺法?請(qǐng)找出所有的擺法。當(dāng)時(shí)，高斯本人并未能完全解決這一問題，他只找到了一部分解答。由于這個(gè)問題的求解需要大量的試驗(yàn)和計(jì)算，因此，用手工求解是難以勝任的。圖 72 即為滿足上述條件的一組布局。請(qǐng)你設(shè)計(jì)一個(gè)程序，由計(jì)算機(jī)自動(dòng)尋找并按如下格式打印所有滿足條件的擺法。算法一：?jiǎn)栴}分析:(1)滿足上述條件的八個(gè)皇后，必然是每行一個(gè)、每列一個(gè)(2)棋盤上任意一行、任意一列、任意一條斜線上都不能有兩個(gè)皇后。如果把 8×8 的棋盤看作一個(gè)平面直角坐標(biāo)系，則八皇后問題就可以用數(shù)學(xué)語(yǔ)言來描述：任意兩個(gè)皇后在

5、QQQQQQQQ平面上的坐標(biāo)應(yīng)同時(shí)滿足以下三個(gè)條件： 橫坐標(biāo)不相等； 縱坐標(biāo)不相等； 兩橫坐標(biāo)之差的絕對(duì)值不等于兩縱坐標(biāo)之差的絕對(duì)值。為了在計(jì)算機(jī)上解決八皇后問題，可以用一個(gè)一維數(shù)組 A(1)來描述八個(gè)皇后在棋盤上的狀態(tài)。其中，數(shù)組的下標(biāo)表示皇后所在的行，數(shù)組元素的值表示皇后所在的列。即 A(1)J 表示在第 I 行、第 J 列放置了一個(gè)皇后。經(jīng)過這樣的定義后，八皇后問題的三個(gè)條件可分別表示如下：(1) 橫坐標(biāo)不相等：IK(K 表示與I 不同的另一個(gè)下標(biāo))；(2) 縱坐標(biāo)不相等：當(dāng) IK 時(shí)，A(I)A(K)；(3) 兩橫坐標(biāo)之差的絕對(duì)值不等于兩縱坐標(biāo)之差的絕對(duì)值：當(dāng) IK 時(shí)，|I-K|A(

6、I)-A(K)|。算法設(shè)計(jì)：首先考慮用回溯法來解決八皇后問題。(1)在棋盤的第一行、第一列放置一個(gè)皇后。(2)從第二行第一列開始，每放置一個(gè)皇后就判斷一下是否滿足條件。如果滿足條件，則從下一行的第一列開始繼續(xù)放置皇后；如果不滿足條件，則將剛剛放置好的皇后向右移動(dòng)一列后再判斷是否滿足條件。(3)若第 1 個(gè)皇后擺到第八列后仍不能滿足條件，說明可能是上一行的皇后的位置不合適，則退回到上一行，將上一行的皇后向右移動(dòng)一列后再作判斷。(4)當(dāng)已擺夠 8 個(gè)皇后時(shí)，即可將這一布局打印出來。流程圖見圖 73。為下一個(gè)皇后找合適的位置：返回判斷是否與前面皇后：返回FtrueKI-1 downto 1Ai=ak

7、 or abs(ai-ak)=abs(I-k)ynFfalseFlagFAinext ; Flagfalse ;只要flag<>trueyAi>8nII-1 ; ai ai+1;判斷是否與前面y？nAiai+1yAi>8nII-1 ; aiai+1Ai0 ; a11 ; I2 ; next1 ; total0為下一個(gè)皇后找合適的位置；yI=8ntotaltotal+1;II+1 ;Next1打印一組解；yAi<>8nAiai+1II-1;Aiai+1;NextaiI=1輸出total的值算法二：國(guó)際象棋的棋盤上共有 30 條斜線，15 條?方向，15 條?方

8、向(見圖 74)。用一維數(shù)組 A(1)-A(30)來表示這 30 條斜線。其中，處在?方向上的 15 條斜線用 A(1)-A(15)表示，處在?方向上的 15 條斜線用 A(16)-A(30)表示。若某一列或某一條斜線上放置了一個(gè)皇后，則在相應(yīng)的數(shù)組單元中置 l，否則置 0。再用一個(gè)一維數(shù)組 C皇后的位置。由對(duì)角線的性質(zhì)可知：若A，B 兩個(gè)皇后處在?方向上的同一條斜線上時(shí)，則應(yīng)有 A 皇后的坐標(biāo)之和等于 B 皇后的坐標(biāo)之和。即 Il 十 JlI2 十 J2, 若 A，B 兩個(gè)皇后處在?方向上的同一條斜線上時(shí)，則應(yīng)有 A 皇后的坐標(biāo)之差的絕對(duì)值等于 B 皇后的坐標(biāo)之差的絕對(duì)值。即|Il-Jl|I2-J2|在第 J 列擺放皇后應(yīng)滿足的條件為：第J 列及兩個(gè)方向的斜線