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

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

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

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

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

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

6、I)-A(K)|。算法設(shè)計：首先考慮用回溯法來解決八皇后問題。(1)在棋盤的第一行、第一列放置一個皇后。(2)從第二行第一列開始，每放置一個皇后就判斷一下是否滿足條件。如果滿足條件，則從下一行的第一列開始繼續(xù)放置皇后；如果不滿足條件，則將剛剛放置好的皇后向右移動一列后再判斷是否滿足條件。(3)若第 1 個皇后擺到第八列后仍不能滿足條件，說明可能是上一行的皇后的位置不合適，則退回到上一行，將上一行的皇后向右移動一列后再作判斷。(4)當已擺夠 8 個皇后時，即可將這一布局打印出來。流程圖見圖 73。為下一個皇后找合適的位置：返回判斷是否與前面皇后：返回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為下一個皇后找合適的位置；yI=8ntotaltotal+1;II+1 ;Next1打印一組解；yAi<>8nAiai+1II-1;Aiai+1;NextaiI=1輸出total的值算法二：國際象棋的棋盤上共有 30 條斜線，15 條?方向，15 條?方

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