一、回溯法：
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
二、什么样的问题用回溯法?
这个问题与集合有关.也就是该问题的解是一个集合.满足一个条件D的集合.来看下面百度百科的定义:
"可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。"
三、算法框架：
1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。
2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
运用回溯法解题通常包含以下三个步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；
四. 设计回溯算法.
设计如下几点:
1. 设定数据结构.
2. 将约束条件整合了约束函数,用于检验当前解状态是否合法(Islegal).
3. 一组解的出口:若找到一组解了,则打印输出或记录解的个数.
4. 循环,穷举当前结点值,深度搜索其子树是否有解,此处相当于递归.
5. 回溯函数的参数: 结点共有且变化的数据.
例:
1.(Target Practice )求解,10次射击,打中90环的可能性有多少?分析:有限集合,条件是10击中90环的一组集合,即为解.
约束条件:1)10环打完,不足90环 2)10环未打完,剩下的已不能满足90环的要求.
if(nScore < 0 || nScore > nTimes * 10)出口: 10次打完或90分已拿到
if(nTimes == 0 || nScore == 0 )
当前结点可能的值:
for(int i = 0; i <= 10; i++)
{
TargetPractice(nTimes - 1, nScore - i);
}
参数设计:当前局, 当前分数
void TargetPractice(int nTimes, int nScore )
完整解:
void TargetPractice(int score, int num)
{
if (score < 0 || score > num * 10) return ;
if (num == 0 || score == 0) {
store[num-1] = score;
Output();
++sum;
return ;
}
for (int i = 0; i <= 10; i++)//one scene have just 11 status
{
store[num - 1] = i;
TargetPractice(score - i, num - 1);
}
}
int main()
{
TargetPractice(90, 10);
return 0;
}
2.八皇后问题.
完整解:
//数据结构:
static char Queen[8][8];//棋盘矩阵
static int a[8]; //标记:列冲突
static int b[15]; //标记:主对角线冲突
static int c[15]; //标记:从对角线冲突
static int iQueeNum = 0;//统计解的个数
void qu(int i);//i代表行,棋子所在行
int main()
{
int iLine, iColumn;
for (iLine = 0; iLine < 8; iLine++)
{
a[iLine] = 0;//列标记初始化
for (iColumn = 0; iColumn < 8; iColumn++)
{
Queen[iLine][iColumn] = '*';
}
}
//主,从对角线标记初始化,表示没有冲突
for (iLine = 0; iLine < 15; iLine++)
{
b[iLine] = c[iLine] = 0;
}
qu(0);
return 0;
}
void qu(int i) //参数:行
{
int iColumn;
for (iColumn = 0; iColumn < 8; iColumn++)//该行共有八种情况
{
if (a[iColumn] == 0 && b[i - iColumn + 7] == 0 && c[i + iColumn] == 0 )
{
Queen[i][iColumn] = '@'; //放皇后
a[iColumn] = 1; //标记,该列已不能放皇后
b[i - iColumn + 7] = 1; //标记,该主对角线不能放皇后
c[i + iColumn] = 1; //标记,该从对角线不能放皇后
if (i < 7)
{
qu(i + 1);//求解下一行
}
else //否则输出
{
//输出棋盘状态
int iLine, iColumn;
printf("第%d种状态为 \n", ++iQueeNum);
for (iLine = 0; iLine < 8; iLine++)
{
for (iColumn = 0; iColumn < 8; iColumn++)
{
printf("%c", Queen[iLine][iColumn]);
}
printf("\n");
}
printf("\n\n");
}
//本次回溯完, 重置标记
Queen[i][iColumn] = '*';
a[iColumn] = 0;
b[i - iColumn + 7] = 0;
c[i + iColumn] = 0;
}
}
}
拿来主义:
本文中引用其它参考文包括
http://blog.csdn.net/adcxf/archive/2008/03/20/2201039.aspx