王鳳紅

回溯算法

王鳳紅

回溯算法是程序設(shè)計中最重要的基礎(chǔ)算法之一，也是搜索算法中的一種控制策略，回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，選擇另外一條路再走。它是從初始狀態(tài)出發(fā)，運用題目給出的條件、規(guī)則，按照深度優(yōu)先搜索的順序擴展所有可能情況，從中找出滿足題意要求的解答?；厮莘ㄊ乔蠼馓厥庑陀嫈?shù)題或較復(fù)雜的枚舉題中使用頻率最高的一種算法。

一、回溯算法說明

1.算法定義

回溯算法是搜索算法中的一種控制策略。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解，如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索?；厮菟惴ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。回溯算法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯算法。

2.算法描述

回溯算法描述如下：

二、經(jīng)典例題分析

[問題描述]

八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題由19世紀著名的數(shù)學(xué)家高斯于1850年提出：在8×8格的國際象棋上擺放8個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結(jié)果?？梢杂没厮莸乃惴ㄇ蟪鲞@92種結(jié)果。圖1是其中的一種結(jié)果。（Q表示皇后的位置）

圖1

1.算法分析

(1)具體設(shè)計思路：任意2個皇后都不能處于同一行、同一列或同一斜線上，所以我們從第一列開始放，看看每一列的皇后都放在哪一行上就可以了。所有可能的情況全部試驗一遍，找出滿足條件的92種結(jié)果。

(2)定義狀態(tài)：即如何描述問題求解過程中每一步的狀況。在八皇后問題中，將行位置作為狀態(tài)。

(3)邊界條件：即在什么情況下程序不再遞歸下去。在八皇后問題中，將等于n+1（產(chǎn)生一種成功放法）作為邊界條件。如果是求滿足某個特定條件的一條最佳路徑，則當(dāng)前狀態(tài)到達邊界時并非一定意味著此時就是最佳目標狀態(tài)。因此還須增加判別最優(yōu)目標狀態(tài)的條件。

(4)搜索范圍：在當(dāng)前狀態(tài)不滿足邊界條件的情況下，應(yīng)如何設(shè)計算符值的范圍。換句話說，如何設(shè)定for語句中循環(huán)變量的初值和終值。在八皇后問題中，每列的行位置i作為搜索范圍，即1≤i≤n。

(5)約束條件和最優(yōu)性要求：所謂約束條件是指，當(dāng)前擴展出一個子結(jié)點后應(yīng)滿足什么條件方可繼續(xù)遞歸下去；如果是求滿足某個特定條件的一條最佳路徑，那么在擴展出某個子狀態(tài)后是否繼續(xù)遞歸搜索下去，不僅取決于子狀態(tài)是否滿足約束條件，而且還取決于子狀態(tài)是否滿足最優(yōu)性要求。在八皇后問題中，將k列的皇后放在第i行上，不產(chǎn)生攻擊（place=true）作為約束條件。

(6)參與遞歸運算的參數(shù)：將參與遞歸運算的參數(shù)設(shè)為遞歸子程序的值參或局部變量。若這些參數(shù)的存儲量大（例如數(shù)組）且初始值需由主程序傳入，為避免內(nèi)存溢出，則必須將其設(shè)為全局變量，且回溯前需恢復(fù)其遞歸前的值。在八皇后問題中，將皇后的列作為參與遞歸運算的參數(shù)。

2.程序清單

[問題描述]

九宮格問題：九宮格游戲規(guī)則，1～9這九個數(shù)字，思考怎么填入三行三列的方格中，要求使每行、每列、兩條對角線上的數(shù)字之和都相等。

九宮格這個游戲不僅僅考驗人的數(shù)字推理能力，也同時考驗了人的思維邏輯能力，對人們的思維鍛煉有著極大的作用，從古時起人們便意識到九宮的教育意義。千百年來影響巨大，在文學(xué)、影視中都曾出現(xiàn)過。九宮格最早叫“洛書”，現(xiàn)在也叫“幻方”。

在《射雕英雄傳》中黃蓉曾破解九宮格，口訣：戴九履一，左三右七，二四有肩，八六為足，五居中央，如圖2所示。

圖2

1.算法分析

列出所有可能的情況從中找出符合條件的解。從第一行第一列開始，找一個還沒有填過的數(shù)填上，然后就填下一個。當(dāng)所有可能的填法都試驗完了以后就回溯到上一個數(shù)，試驗還沒有填過的數(shù)。直到九個格全部填完之后，驗證是不是符合條件。第一種填法是圖3中的a，然后變換到b，再變換到c……最后一種填法是e。

一共有9×8×7×6×5×4×3×2×1=362880種填法，對于每一種填法都驗證每行、每列、對角線上的和是不是等于15，其中有8種填法符合每行、每列、對角線之和都等于15。

(1)定義狀態(tài)：填的第h行，第l列作為狀態(tài)。

(2)邊界條件：當(dāng)h=3，l=4說明已經(jīng)填完一種方案；

(3)搜索范圍：這9個數(shù)：l≤i≤9；

(4)約束條件和最優(yōu)性要求：約束條件是這個數(shù)沒有被填過,找到一個就填上，然后填下一個位置(h,l+1)；

(5)參與遞歸運算的參數(shù)：填寫的第h行，第l列(h，l)。

2.程序清單

三、結(jié)束語

利用這兩個經(jīng)典例題，能很好地訓(xùn)練與掌握回溯算法，回溯算法可以解決很多的問題，是必須要掌握的算法之一。

[1] 吳文虎,王建德.全國信息學(xué)奧林匹克聯(lián)賽培訓(xùn)教程[M].北京：清華大學(xué)出版社，2005

[2] 曹文仙.奧賽題型精解 高中信息學(xué)[M].北京：中國時代經(jīng)濟出版社，2010

稿件編號：P1103127

王鳳紅，本科，中教一級。

山東省北鎮(zhèn)中學(xué)電教中心。