回溯算法

王鳳紅

回溯算法

王鳳紅

回溯算法是程序設計中最重要的基礎算法之一，也是搜索算法中的一種控制策略，回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，選擇另外一條路再走。它是從初始狀態出發，運用題目給出的條件、規則，按照深度優先搜索的順序擴展所有可能情況，從中找出滿足題意要求的解答。回溯法是求解特殊型計數題或較復雜的枚舉題中使用頻率最高的一種算法。

一、回溯算法說明

1.算法定義

回溯算法是搜索算法中的一種控制策略。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解，如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則進入該子樹，繼續按深度優先的策略進行搜索。回溯算法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。回溯算法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的算法稱為回溯算法。

2.算法描述

回溯算法描述如下：

二、經典例題分析

[問題描述]

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

圖1

1.算法分析

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

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

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

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

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

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

2.程序清單

[問題描述]

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

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

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

圖2

1.算法分析

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

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

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

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

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

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

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

2.程序清單

三、結束語

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

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

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

稿件編號：P1103127

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

山東省北鎮中學電教中心。