回溯算法

王鳳紅

回溯算法

王鳳紅

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

一、回溯算法說(shuō)明

1.算法定義

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

2.算法描述

回溯算法描述如下：

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

[問(wèn)題描述]

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

圖1

1.算法分析

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

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

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

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

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

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

2.程序清單

[問(wèn)題描述]

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

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

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

圖2

1.算法分析

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

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

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

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

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

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

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

2.程序清單

三、結(jié)束語(yǔ)

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

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

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

稿件編號(hào)：P1103127

王鳳紅，本科，中教一級(jí)。

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