回溯算法

王凤红

回溯算法

王凤红

回溯算法是程序设计中最重要的基础算法之一，也是搜索算法中的一种控制策略，回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，选择另外一条路再走。它是从初始状态出发，运用题目给出的条件、规则，按照深度优先搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。

一、回溯算法说明

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

王凤红，本科，中教一级。

山东省北镇中学电教中心。