1 什么是回溯法

回溯法实际是穷举算法，按问题某种变化趋势穷举下去，如某状态的变化用完还没有得到最优解，则返回上一种状态继续穷举。回溯法有“通用的解题法”之称，其采用了一种“走不通就掉头”思想作为其控制结构，用它可以求出问题的所有解和任意解。

它的应用很广泛，很多算法都用到回溯法，例如，迷宫，八皇后问题，图的m着色总是等都用到回溯法，当然其中还使用了其他策略。

2 解的表示

回溯法搜索一条路径，这条路径的节点都满足约束条件。

既然，回溯法搜索的是路径， 因此可用数组 A[0,1,2，。。。，N-1] 表示。 其中A【i】 表示 第i个节点的取值。

3 基本思想

回溯法从开始结点（根结点）出发，以深度优先的方式搜索整个解空间（一般为树结构空间）。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。

在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。

如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。

回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

运用回溯法解题通常包含以下三个步骤：

（1）针对所给问题，定义问题的解空间；

（2）确定易于搜索的解空间结构；

（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；

算法的关键是 判断节点 （i,j） 是否为解路径上的节点，其判断方法如下所示：

// 判断节点（I,j）是否为解路径上的节点,其中：

//

// i表示解路径上的第i个测试节点、j表示该节点的某个候选值

// A[i] 保存第i个节点选用的值

BOOL TestNode(I ,j)

{

与0—(i-1) 层进行判断，看是否与以遍历的节点有冲突

若有冲突， 则返回FALSE；

若无冲突， 则 将节点i的值j,保存到对应的数组中A[I]=J;

判断I是否为最后一层,

若是最后一层，则成功找到一条解路径，返回TRUE；

若不是最后一层，则判断第i+1层是否有正确的节点。

BOOL bFlag=FALSE;

FOR(k=0;k<CANDIDATE_NUM;k++) //候选值【0，。。。，CANDIDATE_NUM-1】

{

If(TestNode(i+1,k))

{

找到一个解；

bFlag=True;

}

}

RETURN bFlag;

}

4 算法伪代码

1） 求解单个解

// 该函数用来测试 节点i是否是解路径上的节点

BOOL TestNode(int i,int j){

//与之前的0 —（i-1）层的值做比较，看看有无冲突

FOR(int k=0;k<I;k++)

{

If(有冲突)

Return FALSE; //此节点为死节点，不在解路径上

}

//与之前的都无冲突,则选定此候选值

A[i]=j;

//判断第i层是否为最后一层,若是最后一层，则成功找到一个解

If(i==NUM-1)

Retrun TRUE;

//若不是最后一层，则判断第 i+1层上 有无解路径上的节点

BOOL bFlag=FALSE;

FOR(int k=0;k<CANDIDATA_NUM;k++)

{

If(TestNode(i+1,k))

{

bFlag=TRUE;

Break; // 找到一个解

}

}

Return bFlag; //返回这个节点的信息 是否位于解路径上

}

BOOL bExist=FALSE; // 是否存在解

//从最初节点 开始判断

For(int j=0;j<CANDIDATA_NUM;j++)

{

IF(TestNode(0,j))

{

bExist=TRUE;

break; // 找到一个解后，便退出 ，不再找其他解

}

}

Return bExist;

2）所有解

全局变量：

#define NUM 8 //候选值 与 节点个数均为8

Extern int A[NUM]; //保存一个解路径

Extern std::<int> OneResult; // 保存一个解路径

Extern std::<std::vector<int>> AllResult; //保存所有的解路径

// 该函数用来测试 节点i是否是解路径上的节点

BOOL TestNode(int i,int j){

//与之前的0 —（i-1）层的值做比较，看看有无冲突

FOR(int k=0;k<I;k++)

{

If(有冲突)

Return FALSE; //此节点为死节点，不在解路径上

}

//与之前的都无冲突,则选定此候选值

A[i]=j;

//判断第i层是否为最后一层,若是最后一层，则成功找到一个解，将此解添加到容器中 If(i==NUM-1){ OneResult.clear(); For(int k=0;k<NUM;k++) OneResult.push_back(A[k]); //将本次结果保存到容器中 AllResult.push_back(OneResult); Retrun TRUE;}

//若不是最后一层，则判断第 i+1层上 有无解路径上的节点

BOOL bFlag=FALSE;

FOR(int k=0;k<CANDIDATA_NUM;k++)

{

If(TestNode(i+1,k))

{

bFlag=TRUE;

// Break; // 找到一个解找到解后，不退出，再接着尝试下一个候选值

}

}

Return bFlag; //返回这个节点的信息 是否位于解路径上

}

BOOL bExist=FALSE; // 是否存在解

//从最初层 开始判断

For(int j=0;j<CANDIDATA_NUM;j++)

{

IF(TestNode(0,j))

{

bExist=TRUE;

// break; 不退出，接着寻找下一个解

}

}

Return bExist;