王凤红

回溯算法

王凤红

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

一、回溯算法说明

1.算法定义

回溯算法是搜索算法中的一种控制策略。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则进入该子树，继续按深度优先的策略进行搜索。回溯算法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。回溯算法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯算法。

2.算法描述

回溯算法描述如下：

二、经典例题分析

[问题描述]

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题由19世纪著名的数学家高斯于1850年提出：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。……