回溯法是搜索问题解的一种系统方法。回溯法求解首先需要定义一个解空间，这个空间至少包含问题的一个最优解。回溯法的下一步是组织解空间，使空间便于搜索，典型的组织方式是树或者图。
一旦确定了解空间的组织方式，这个空间即可按照深度优先的方式从节点进行搜索。在0-1背包问题中，开始节点为根节点，开始节点为一个活动节点又是一个E-节点。从E-节点试着移动到一个新的节点。如果从当前的E-节点移动到一个新的节点，那么这个新节点就变成一个活动节点和新的E-节点。而原来的E-节点仍然是一个活动节点。若不能移动到一个新的节点，那么当前的E-节点死掉，即不再是活动节点。然后回到最近的活动节点，这个活动节点变成新的E-节点。当已经找到答案或者不再有活动节点的时候，搜索过程结束。
0-1背包问题
考察如下背包问题：n=3,w=[20,15,15],p=[40,25,25],c=30.从根节点开始搜索图20-2中的树，根节点是当前唯一活动的节点，也是E-节点。从这里可以移动到B节点和C节点，假定移动到B，则当前活动节点为A和B，B也是当前E-节点，在节点B，剩余容量为10，而收益为cp=40。从B节点可以移动到D、E节点，但是移动到D节点是不可行的，因为移动到D节点所需要的容量为15. 移动到E是可行的，因为移动到E不需要占据任何容量。E变成新的E-节点，此时活动节点变成A、B、E。在节点E，剩余容量r=10,cp=40。再从E点移动到J和K，很明显，移动到J是不可行的，移动到K是可行的。节点K变成新的E-节点。因为K是叶子节点，所以得到一个可行解。这个解的收益是cp=40。X的值有根节点到K的路径决定（X[i]=1表示装入背包，X[i]=0表示不装入背包）。因为K节点不能进一步扩充，所以K节点死亡，回溯到E节点，而E节点也不能进一步扩充，故E节点也死了。
接着再回溯到B节点，B节点也死亡了。A节点再次变成E-节点，它可以进一步进行扩充，到达节点C，此时剩余容量r=30,cp=0。从C节点可以移动到F、G节点，假定移动到F节点，F变成新的E-节点，活动节点变成A、C、F.。在F节点，r=15,cp=25。从F节点可以移动到L、M节点。假定移动到L，此时r=0,cp=50。既然L为叶子节点，且它代表了目前最优解更好的解，我们将这个解作为最优解。节点L死亡，向上回溯到F节点。再移动到M节点，M节点死亡，再回溯到F节点，F死亡，再回溯到C节点，再移动到G节点...搜索整棵树，在搜索期间发现的最好解即为最优解。
回溯方法的步骤如下：
1.定义一个解空间，它包含对问题实例的解。
2.用适合搜索的方式组织解空间。
3.用深度优先方式搜索解空间，利用界定函数避免进入无解的子空间
回溯算法的实现有一个特性：在搜索的同时产生解空间，在搜索过程的任何节点时刻，仅保留从开始节点到当前E-节点的路径。
下面具体分析一个0-1背包实例：
n=4,c=7,w=[3,5,2,1],p=[9,10,7,4]。对象的收益密度为[3,2,3.5,4]。当以收益密度递减的顺序装包的时候，首选对象4，然后是对象3，然后是对象1。当这三个对象装入背包的时候，剩余容量为1，剩余容量可容纳0.2重量的2对象，可产生收益为2，生成的解为x=[1,0.2,1,1]，相应的收益为22，虽然该解不可行，但是可行的最优解一定少于该解。
该题的解空间树为图20-2再加上一层节点，当位于解空间的节点B时，x[1] = 1,收益cp = 9,该节点所用容量cw=3，剩余容量cleft=c-cw = 4.
当位于节点C时，cp=cw=0，cleft = c = 7.。按密度递减顺序填充剩余容量，先把对象4和3装入背包，然后将对象2的0.8倍装入背包。这样产生的收益为19。
在节点E，cp=9,cw=3,cleft=4。仅剩对象3和4需要考虑，按照密度递减顺序考虑，先将对象4装入背包，然后是对象3.所以在E节点中无节点有多于cp+4+7=20的收益，若已经找到一个收益为20或者更多的解，搜索则不必搜索E子树。
以下是完整的C++程序代码：
// ConsoleApplication3.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
//定义全局变量
int n=4; //物品数量
double c=7; //背包容量
double v[10]; //各个物品的价值
double w[10]; //各个物品的重量
double cw = 0.0; //当前背包重量
double cp = 0.0; //当前背包中物品价值
double bestp = 0.0;//当前最优价值
double perp[10]; //单位物品价值排序后
int order[10]; //物品编号
int put[10]; //设置是否装入
//按单位价值排序
void knapsack()
{
int i, j;
int temporder = 0;
double temp = 0.0;
for (i = 1; i <= n; i++)
perp[i] = v[i] / w[i];
//冒泡排序
for (i = 1; i <= n-1; i++)
{
for (j = i + 1; j < n; j++)
{
if (perp[i] < perp[j])
{
temporder = order[i];
order[i] = order[j];
order[j] = temporder;
temp = perp[i];
perp[i] = perp[j];
perp[j] = perp[i];
temp = v[i];
v[i] = v[j];
v[j] = temp;
temp = w[i];
w[i] = w[j];
w[j] = temp;
}
}
}
return;
}
//计算上界函数
double bound(int i)
{
double leftw = c - cw;
double b = cp;
while (i <= n && w[i] <= leftw)
{
leftw -= w[i];
b += v[i];
i++;
}
if (i <= n)
b += v[i] / w[i] * leftw;
return b;
}
//回溯函数
void backtrack(int i)
{
if (i > n)
{
bestp = cp;
return;
}
if (cw + w[i] <= c)
{
cw += w[i];
cp += v[i];
put[i] = 1;
backtrack(i + 1);
cw -= w[i];
cp -= v[i];
}
//符合条件搜索右子树
if (bound(i + 1) > bestp)
backtrack(i + 1);
return;
}
int main()
{
int i;
w[1] = 3;
w[2] = 5;
w[3] = 2;
w[4] = 1;
v[1] = 9;
v[2] = 10;
v[3] = 7;
v[4] = 4;
for(i=1;i<=n;i++)
{
order[i] = i;
}
//先排序
knapsack();
backtrack(1);
printf("最优价值：%.2f\n", bestp);
for (i = 1; i <= n; i++)
{
if (put[i] == 1)
printf("%d\t", order[i]);
}
getchar();
return 0;
}
八皇后问题-回溯法
基本思路：
1.创建一个全局变量二维数组chess并初始化为0；
2.逐行放皇后，若存在相互攻击现象则向后移动一列，若不存在相互攻击现象，则进行下一行皇后的放置
// ConsoleApplication3.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<stdio.h>
#include<windows.h>
#define N 4 //可以根据N来修改棋盘的格数
int count = 0;//设置一个计数器
int chess[N][N] = { 0 };//用于存放棋盘的二维数组
void print()//打印函数
{
int i = 0;
int j = 0;
printf("*****************************************\n");
for (i = 0; i<N; i++)
{
for (j = 0; j<N; j++)
{
printf("%d ", chess[i][j]);
}
printf("\n");
}
printf("*****************************************\n");
}
//判断是否会互吃
//关键条件
//返回1 表示存在互吃
//返回0 表示正常
int check(int i, int j)//i = 7,j = 4
{
if (i == 0)
return 0;//表示正常
int k = 0;
for (k = 0; k<i; k++)
{
if (chess[k][j] == 1)//(0,4)(1,4)...
return 1;
}
for (int s = 0, k = j + 1; k<N; k++)
{
//(7,4)(6,5),(5,6),(4,7)
if (chess[i - s - 1][k] == 1)//(0,11),(1,10),(2,9),(3,8),(4,7)
return 1;
s++;
}
for (k = 0; k<j; k++)
{
if (chess[i - k - 1][j - k - 1] == 1)//(6,3)(5,2)(4,1)(3,0)
return 1;
}
for (k = 0; k<N; k++)
{
if (chess[k][j] == 1)
return 1;
}
return 0;
}
//判断棋盘上是否有一行存在没有皇后的情况
//返回0 ，表示棋盘正常（每一行都有皇后）
//返回1 ，表示棋盘有错
int check_all()
{
int i = 0;
int j = 0;
int flag = 0;
for (i = 0; i<N; i++)
{
flag = 0;
for (j = 0; j<N; j++)
{
if (chess[i][j] == 1)
{
flag = 1;
break;
}
}
if (flag == 0)
return 1;//有错
}
return 0;
}
//检查某一行是否存在皇后
//返回0 表示存在
//返回1 表示没皇后
int check_line(int line)
{
if (line == 0)
return 0;
int k = 0;
int s = 0;
int flag = 1;
for (s = 0; s<line - 1; s++)
{
flag = 1;
for (k = 0; k<N; k++)
{
if (chess[s][k] == 1)
flag = 0;
}
if (flag == 1)
return 1;
}
return 0;
}
//递归的主要算法
void queen(int i, int j)
{
//符合，置一，进入下一行
if (check_line(i) == 1)//若该行有皇后，返回
return;
if ((i == (N - 1)))//若此时是最后一行
{
if (check(i, j) == 0)//当最后一行的皇后可以放下（表示可以成功放置）
{
chess[i][j] = 1;//将该位置1，表示皇后
print();//打印
count++;//计数器+1
}
}
if (check(i, j) == 0)//当可以放皇后时
{
chess[i][j] = 1;//放入
//print();
//Sleep(1000);
queen(i + 1, 0);//进行下一行的皇后放置
}
if (j == N)//如果j等于列数，表明越界，返回
return;
chess[i][j] = 0;//将该位置0
//print();
//Sleep(500);
//不符合，置零，右诺
queen(i, j + 1);//将该行皇后右移一位
}
int main(void)
{
queen(0, 0);
printf("\ncount = %d\n", count);
getchar();
return 0;
}
![goalng nil interface浅析持续学习[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)