回溯算法
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
与穷举的联系
回溯法简单来说就是按照深度优先的顺序，穷举所有可能性的算法，但是回溯算法比暴力穷举法更高明的地方就是回溯算法可以随时判断当前状态是否符合问题的条件。
一旦不符合条件，那么就退回到上一个状态，省去了继续往下探索的时间。
回溯法的特点是深度优先遍历，也就是该问题的遍历顺序是1->2->3，然后从子节点3返回，从子节点2返回，再到1->3->2，以此类推。
状态的返回只有当前的节点不再满足问题的条件或者我们已经找到了问题的一个解时，才会返回，否则会以深度优先一直在解空间树内遍历下去。
当然，对于某些问题如果其解空间过大，即使用回溯法进行计算也有很高的时间复杂度，因为回溯法会尝试解空间树中所有的分支。
所以根据这类问题，我们有一些优化剪枝策略以及启发式搜索策略。
所谓优化剪枝策略，就是判断当前的分支树是否符合问题的条件，如果当前分支树不符合条件，那么就不再遍历这个分支里的所有路径。
所谓启发式搜索策略指的是，给回溯法搜索子节点的顺序设定一个优先级，从该子节点往下遍历更有可能找到问题的解。
来源
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。
用回溯算法解决问题的一般步骤：
1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
2、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
3、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。
这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。
这个新结点就成为一个新的活结点，并成为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。
此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。
回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
基本思想
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。
回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。
回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达 最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。
它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。
如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。
否则，进入该子树，继续按深度优先的策略进行搜索。
回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。
而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。
这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
8 皇后问题
问题
在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
解法
int g_number = 0;
void EightQueen()
{
const int queens = 8;
int ColumnIndex[queens];
for(int i = 0; i < queens; ++ i)
ColumnIndex[i] = i;
Permutation(ColumnIndex, queens, 0);
}
void Permutation(int ColumnIndex[], int length, int index)
{
if(index == length)
{
if(Check(ColumnIndex, length))
{
++ g_number;
PrintQueen(ColumnIndex, length);
}
}
else
{
for(int i = index; i < length; ++ i)
{
int temp = ColumnIndex[i];
ColumnIndex[i] = ColumnIndex[index];
ColumnIndex[index] = temp;
Permutation(ColumnIndex, length, index + 1);
temp = ColumnIndex[index];
ColumnIndex[index] = ColumnIndex[i];
ColumnIndex[i] = temp;
}
}
}
bool Check(int ColumnIndex[], int length)
{
for(int i = 0; i < length; ++ i)
{
for(int j = i + 1; j < length; ++ j)
{
if((i - j == ColumnIndex[i] - ColumnIndex[j])
|| (j - i == ColumnIndex[i] - ColumnIndex[j]))
return false;
}
}
return true;
}
void PrintQueen(int ColumnIndex[], int length)
{
printf("Solution %d\n", g_number);
for(int i = 0; i < length; ++i)
printf("%d\t", ColumnIndex[i]);
printf("\n");
}
背包问题
有N件物品和一个容量为V的背包。
第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这是最基础的背包问题，总的来说就是：选还是不选，这是个问题
相当于用f[i][j]表示前i个物品装入容量为v的背包中所可以获得的最大价值。
对于一个物品，只有两种情况
情况一: 第i件不放进去，这时所得价值为:f[i-1][v]
情况二: 第i件放进去，这时所得价值为：f[i-1][v-c[i]]+w[i]
接下来的实例属于算法进阶，可做了解
提两点，
-
与上期贪婪法所解决的背包问题相比，回溯法将能更能顾及寻找全局最优。
-
背包问题与八皇后问题所用的算法虽然都是回溯法，但是他们的目的不一样，八皇后只要求把所有的棋子放在棋盘上（即只需解决深度最优）。
而背包问题不仅需要让物品都放进背包，而且要使得物品质量最大，在八皇后问题上多提出了一个限制。
问题的解空间
用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个(最优)解。
对于 n=3 时的 0/1 背包问题，可用一棵完全二叉树表示解空间，如图所示：
|  |
求解步骤
1) 针对所给问题，定义问题的解空间；
2) 确定易于搜索的解空间结构；
3) 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
常用的剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。
回溯法对解空间做深度优先搜索时，有递归回溯和迭代回溯（非递归）两种方法，但一般情况下用递归方法实现回溯法。
算法描述
解 0/1 背包问题的回溯法在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。
当右子树中有可能包含最优解时才进入右子树搜索。
否则将右子树剪去。
void dfs(int i,int cv,int cw)
{
//cw当前包内物品重量，cv当前包内物品价值
if(i>n)
{
if(cv>bestval) //是否超过了最大价值
{
bestval=cv; //得到最大价值
for(i=1;i<=n;i++)
bestx[i]=x[i]; //得到选中的物品
}
}
else
for(int j=0;j<=1;j++) //枚举物体i所有可能的路径，
{
x[i]=j;
if(cw+x[i]*w[i]<=TotCap) //满足约束,继续向子节点探索
{
cw+=w[i]*x[i];
cv+=val[i]*x[i];
dfs(i+1,cv,cw);
cw-=w[i]*x[i]; //回溯上一层物体的选择情况
cv-=val[i]*x[i];
}
}
}
这里其实是：穷举+剪枝+回溯
