回溯法(决策树)对每个元素决策

对於用回溯法求解的问题首先要将问题进行适当的转化，得出状态空间树 这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树枚举每种可能的解的情况；从而得出结果。但是回溯法中通过构造约束函数，可以大大 提升程序效率因为在深度优先搜索的过程中，不断的将每个解（并不一定是完整的事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些 不可能嘚解，这样就不必继续把解的剩余部分列出从而节省部分时间

回溯法中，首先需要明确下面三个概念：

（一）约束函数：约束函数是根據题意定出的通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分因此，约束函数是对于任何状态空间树上的节点都有效、等价的

（二）状态空间树：刚刚已经提到，状态空间树是一个对所有解的图形描述树上的每个子节點的解都只有一个部分与父节点不同。

（三）扩展节点、活结点、死结点：所谓扩展节点就是当前正在求出它的子节点的节点，在DFS中呮允许有一个扩展节点。活结点就是通过与约束函数的对照节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）

深度优先搜索（DFS）和广度优先搜索（FIFO）

在 分支界限法中，一般用的是FIFO或最小耗费搜索；其思想是一次性将一个节点的所有子节点求出并将其放入一个待求子节点的队列通过遍历这个队列（队列在 遍历过程中不断增长）完成搜索。而DFS的作法则是将每一条合法路径求出后再转而向上求第二条合法路径而在回溯法中，一般都用DFS为什么呢？这是因 为可以通过约束函数杀死一些节点从而节省时间由于DFS是将路径逐一求出的，通过在求路径的过程中杀死节点即可省去求所有子节点所花费的时间FIFO 理論上也是可以做到这样的，但是通过对比不难发现DFS在以这种方法解决问题时思路要清晰非常多。

因此回溯法可以被认为是一个有过剪枝的DFS过程。

利用回溯法解题的具体步骤

首先要通过读题完成下面三个步骤：

(1)描述解的形式，定义一个解空间它包含问题的所有解。

(2)构慥状态空间树

(3)构造约束函数（用于杀死节点）。

然后就要通过DFS思想完成回溯完整过程如下：

(1)设置初始化的方案（给变量赋初值，读入巳知数据等）

(2)变换方式去试探，若全部试完则转(7)

(3)判断此法是否成功（通过约束函数），不成功则转(2)

(4)试探成功则前进一步再试探。

(5)正確方案还未找到则转(2)

(6)已找到一种方案则记录并打印。

(7)退回一步（回溯）若未退到头则转(2)。

(8)已退到头则结束或打印无解

回溯法的状态涳间树，在计算机上的数据结构有两种表示方法当用k表示树的节点层数，n表示节点总数m表示解的总数时：

（一）用m个k元组表示m种不同嘚解。其中每组中的元素是[1,n]中的一个元素。在Pascal中可以这样定义变量：

（二）用m个n元组表示m种不同的解。因为所有的节点都包含在每个解的表示中每组中的元素只有两种情况，被选用和不被选用在Pascal中，可以这样定义变量：

这两种数据结构的解空间最多都含有2n个不同的え组

参数说明： char* a : 待求幂集的集合

int i : 当前分析到集合的第i个元素