回溯法
| [日期：2014-05-19] | 作者：信息技术 次浏览 | [字体：大 中 小] |
1、 回溯法的描述
（1）、基本思想：
回溯法有“通用的解题法”之称，它实际是应用穷举法的一种方式。许多涉及搜索问题的求解过程都要利用回溯策略。它主要应用在解决一些过程完成中要经过若干个步骤，而每个步骤都有若干种可能的分支，为了完成这一过程，又须遵守一些规则，但这些规则又无法精确地用数学公式或语言来描述的一类问题中。在那些涉及到寻找一组解的问题或者求满足某些约束条件的最优解问题中，有许多可以用回溯法来求解。
它的基本思路是：在含问题所有解的一棵状态树中，按照深度优先的策略，从根出发进行搜索，每到达一个结点就判断以该结点为根的子树是否包含问题的解，如果可以肯定没有，则放弃对该子系统接点的搜索，而向上一层结点回溯，寻找未被搜索过的其他儿子结点，对新的一棵树做同样的判断，可能有解就进入继续搜索，直到找到解或所有结点均被搜索。
（2）、算法过程表达
设问题P的每个状态结点n个元x1，x2，…，xn，假设对于任意的1≤k≤n，在状态结点（x1，x2，…，xk-1）已经过所有约束条件检验后，满足部分约束（包括定义域）的xk的全体记为Tk（x1，x2，…，xk-1）。回溯法的过程可以表达如下：
FUNCTION BACKTRACK（n）
K=1
LOOP
IF Tk（x1，x2，…，xk-1）中的值未取遍 THEN
Xk= Tk（x1，x2，…，xk-1）中未取过的一个值；
IF （x1，x2，…，xk）满足约束条件 THEN
IF K=n THEN
PRINT（x1，x2，…，xk）“输出一个回答结点”
ELSE
K=K+1
END IF
ELSE
K=K-1
END IF
UNTIL （K=0）
END FUNCTION
回溯算法递归表述为：
FUNCTION BACKTRACK（K）
IF K>N THEN
退出
ELSE
FOR 每一个属于TK（x1，x2，…，xk）且使得（x1，x2，…，xk-1）满足约束条件的XK
IF K=N THEN
输出（x1，x2，…，xk）“输出一个回答结点”
END IF
BACKTRACK（K+1）
NEXT
END IF
END FUNCTION
例题：见信息学奥赛程序设计P143：例9-12和9-13；P147：例9-14
练习：
1、 要求用递归回溯解决四皇后问题：要求在4*4的棋盘上放上四个皇后，使得每一个皇后既攻击不到另外三个皇后，也不能被另外三个皇后所攻击。按照国际象棋的规则，一个皇后可以攻击与其处在同一行或同一列或同一斜线上的其他任何棋手，因此，四皇后问题等于要求四个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。（用递归回溯法解决）
2、 数字组合：键盘输入一个仅由数字（1到9）组成的字符串，输出以该串中任取M个数字的所有组合及组合总数。（输如数据均不需要判错）。
3、 求n（n是2的幂（n>=2））个元素中的最大元与最小元。（要求用分治法处理）
4、 背包问题：设有一个背包，可以放入重量为S。现有n件物品，重量分别为S1，S2，S3，…，Sn，并假设Si（1<=i<=n）均为正数，从这n件物品中选择若干件物品放入此背包，使得放入得总重量恰好为S，请输出一种解，若无解输出“NO ANSWER”。