暴力回溯算法图解

1. 回溯法的用回溯法解题的一般步骤

（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
回溯法C语言举例
八皇后问题是能用回溯法解决的一个经典问题。
八皇后问题是一个古老而着名的问题。该问题是十九世纪着名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。引入一个整型一维数组col[]来存放最终结果，col[i]就表示在棋盘第i列、col[i]行有一个皇后，为了使程序再找完了全部解后回到最初位置，设定col[0]的初值为0，即当回溯到第0列时，说明以求得全部解，结束程序运行。为了方便算法的实现，引入三个整型数组来表示当前列在三个方向上的状态 ：
a[] a[i]=0表示第i行上还没有皇后；
b[] b[i]=0表示第i列反斜线/上没有皇后；
c[] c[i]=0表示第i列正斜线上没有皇后。
棋盘中同一反斜线/上的方格的行号与列号之和相同；同一正斜线上的方格的行号与列号之差均相同，这就是判断斜线的依据。
初始时，所有行和斜线上都没有皇后，从第1列的第1行配置第一个皇后开始，在第m列，col[m]行放置了一个合理的皇后，准备考察第m+1列时，在数组a[]，b[]和c[]中为第m列，col[m]行的位置设定有皇后的标志；当从第m列回溯到m-1列时，并准备调整第m-1列的皇后配置时，清除在数组a[],b[]和c[]对应位置的值都为1来确定。 #include<stdio.h>
#include<stdlib.h>
#define Queens 8
int a[Queens+1]; //八皇后问题的皇后所在每一行位置，从1开始算
int main()
{
int i,k,flag,not_finish=1,count=0;
i=1;//初始
a[1]=1;
printf(the possible configuration of 8 queesns are: );
while(not_finish) //not_finsh=1:处理未结束
{
while(not_finish && i<Queens+1) //处理未结束
{
for(flag=1,k=1;flag && k<i;k++)//判断是否有多个皇后在同一行
if(a[k]==a[i])
flag=0;
for(k=1;flag && k<i;k++) //判断是否有多个皇后在对角线
if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))
flag=0;
if(!flag) //若存在矛盾 重设第i个元素
{
if(a[i]==a[i-1]) //若a[i]的值已经已经一圈追上a[i-1]的值
{
i--; //退回一步 重新试探处理前一个元素
if(i>1 && a[i]==Queens)
a[i]=1; // 当a[i]为 Queens时 将a[i]的值重置
else
if(i==1 && a[i]==Queens)//当第一未位的值达到Queens时结束
not_finish=0;
else
a[i]++;
}
else
if(a[i]==Queens)
a[i]=1;
else
a[i]++;
}
else
if(++i<=Queens) //若前一个元素的值为Queens
if(a[i-1]==Queens)
a[i]=1;
else //否则元素为前一个元素的下一个值
a[i]=a[i-1]+1;
}
if (not_finish)
{
++count;
printf((count-1)%3?[%2d]:: [%2d]:,count);
for(k=1;k<=Queens;k++) //输出结果
printf(%d,a[k]);
if(a[Queens-1]<Queens)
a[Queens-1]++;
else
a[Queens-1]=1;
i=Queens-1;
}
}
system(pause);
} var
n,k,t,i:longint;
x:array[1..100] of integer;
function pa(k:integer):boolean;
begin
pa:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then pa:=false;
end;
procere try(k:integer);
var
i:integer;
begin
if k>n then
begin
t:=t+1;
exit;
end;
for i:=1 to n do
begin
x[k]:=i;
if pa(k) then try(k+1);
end;
end;
begin
read(n);
t:=0;
try(1);
write(t);
end. #include
#include
#define m 5
#define n 6
int sf=0;
int mase[m][n]={{0,0,0,1,0,0},{0,1,0,0,0,0},{0,1,1,1,1,0},{0,0,0,0,0,1},{1,0,1,1,0,0}};
void search(int x,int y)
{
if((x==m-1)&&(y==n-1))
sf=1;
else
{
mase[x][y]=1;
if((sf!=1)&&(y!=n-1)&&mase[x][y+1]==0)
search(x,y+1);
if((sf!=1)&&(x!=m-1)&&mase[x+1][y]==0)
search(x+1,y);
if((sf!=1)&&(y!=0)&&mase[x][y-1]==0)
search(x,y-1);
if((sf!=1)&&(x!=0)&&mase[x-1][y]==0)
search(x-1,y);
}
mase[x][y]=0;
if(sf==1)
mase[x][y]=5;//通过路径用数字的表示
}
int main()
{
int i=0,j=0;
//clrscr();
search(0,0);
for(i=0;i<m;i++) p=></m;i++)>
{
for(j=0;j<n;j++) p=></n;j++)>
printf(%d,mase[i][j]);
printf( );
}
system(pause);
return 0;
}
回溯法解决迷宫问题PASCAL语言
program migong;
var
n,k,j,x,y:integer;
a:array[0..10000,0..10000] of integer;
b:array[0..1000000,0..2] of integer;
procere search(x,y,i:integer);
begin
a[x,y]:=1;
if (x=n) and (y=n) then
begin
for j:=1 to i-1 do
writeln(j,':(',b[j,1],',',b[j,2],')');
writeln(i,':(',x,',',y,')');
halt;
end;
if a[x-1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x-1,y,i+1);end;
if a[x+1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x+1,y,i+1);end;
if a[x,y-1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y-1,i+1);end;
if a[x,y+1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y+1,i+1);end;
a[x,y]:=0;
end;
begin
read(n);
for k:=1 to n do
for j:=1 to n do
read(a[k,j]);
for k:=0 to n+1 do
begin
a[k,0]:=-1;
a[k,n+1]:=-1;
a[n+1,k]:=-1;
a[0,k]:=-1;
end;
x:=1;y:=1;
if a[x+1,y]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x+1,y,1);a[x,y]:=0;end;
if a[x,y+1]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x,y+1,1);a[x,y]:=0;end;
end.

2. 常见算法思想6：回溯法

回溯法也叫试探法，试探的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。

（1）针对所给问题，定义问题的解空间。
（2）确定易于搜索的解空间结构。
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯法为了求得问题的正确解，会先委婉地试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，马上会自觉地退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心。

下面是回溯的3个要素。
（1）解空间：表示要解决问题的范围，不知道范围的搜索是不可能找到结果的。
（2）约束条件：包括隐性的和显性的，题目中的要求以及题目描述隐含的约束条件，是搜索有解的保证。
（3）状态树：是构造深搜过程的依据，整个搜索以此树展开。

下面是影响算法效率的因素：

回溯法搜索解空间时，通常采用两种策略避免无效搜索，提高回溯的搜索效率:

为缩小规模，我们用显示的国际象棋8*8的八皇后来分析。按照国际象棋的规则，皇后的攻击方式是横，竖和斜向。
皇后可以攻击到同一列所有其它棋子，因此可推导出每1列只能存在1个皇后，即每个皇后分别占据一列。棋盘一共8列，刚好放置8个皇后。

为了摆放出满足条件的8个皇后的布局，可以按如下方式逐步操作：

把规模放大到N行N列也一样，下面用回溯法解决N皇后问题：

执行：

3. 9.2 回溯算法的例子

在4 * 4的方格棋盘上放置4个皇后棋子，使得没有两个皇后在同一行、同一列，也不在同一条45度的斜线上， 问有多少种布局?
回溯算法的解一般是向量，而这个题也不例外，设4维向量的<x1,x2,x3,x4>，Xi中i表示第几个皇后，Xi表示在棋盘第i行的位置，比如其中一个解是<2,4,1,3>，如下图

1.四皇后问题中，叶节点就是一个解。
2.四皇后每一个节点的子树代表着下一个皇后可以放的列数，因为都是n，所以子树都是n叉树，故四皇后是一颗 n叉树
3.四皇后的解至少有两个，因为棋盘可以沿着中心线翻折

有n种物品，每种物品只有1个。第i种物品价值为vi，重量为wi，i=1，2，3...n. 问如何选择放入背包的物品，使得总重量不超过B，而价值达到最大?
同样，此问题的解可用一个向量来表示，该向量就代表了所有的物品，如果对应物品为1，则表示装入背包，反之，没有被装入。
因此，回溯的每层可以表示为对应的物品，分支左右可以表示取或者不取（向量中表示为1或0）
总而言之，每一个节点也就是物品只有0和1两种状态，因此该树一棵二叉树，或者为 子集树

1.选择第一个物品，目前总重量为8，总价值为12。
2.再选择第二个物品，总重量为14 > 13，触发回溯。
3.不选择第二个物品，选择第三个商品，总重量是12，总价值为21。
4.再选择第四个物品，总重量为15 > 13，触发回溯。
5.不选择第四个物品，总重量为12，总价值为21，与目前最优解价值进行比较，如果最优解价值大于21则替换目前的最优解向量和最优解价值。

1.背包问题只有在叶节点才能生成一个满足条件的解，而之后将该解和最优解比较。
2.背包问题必须遍历完所有的分支，才能够获得最终的解。
3.背包问题是一颗子集树。

有n个城市，已知任两个城市之间的距离， 求一条每个城市恰好经过一次的回路，使得总长度最小 。
货郎问题中主要的一点就是每一个点（除了第一个点）其他点必须经过且只能经过1次，这就很像数学中的排列。
因此，我们采用一个向量来表示货郎问题的城市排列

1.货郎问题是一颗分支不断减少的排列数（和数学的排列类似）
2.货郎问题也得遍历完所有的情况，比较后得出最优解。

1.解都是用向量表示
2.搜索空间都是树
3.搜索策略多种，有深度优先、宽度优先和跳跃式遍历搜索树。

4. 五大基本算法——回溯法

回溯法是一种选优搜索法（试探法）。

基本思想：将问题P的状态空间E表示成一棵高为n的带全有序树T，把求解问题简化为搜索树T。搜索过程采用 深度优先搜索 。搜索到某一结点时判断该结点是否包含原问题的解，如果包含则继续往下搜索，如果不包含则向祖先回溯。

通俗来说，就是利用一个树结构来表示解空间,然后从树的根开始深度优先遍历该树，到不满足要求的叶子结点时向上回溯继续遍历。

几个结点：
扩展结点：一个正在产生子结点的结点称为扩展结点
活结点：一个自身已生成但未全部生成子结点的结点
死结点：一个所有子结点已全部生成的结点

1、分析问题，定义问题解空间。

2、根据解空间，确定解空间结构，得 搜索树 。

3、从根节点开始深度优先搜索解空间（利用 剪枝 避免无效搜索）。

4、递归搜索，直到找到所要求的的解。

1、子集树
当问题是：从n个元素的集合S中找出满足某种性质的子集时，用子集树。
子集树必然是一个二叉树。常见问题：0/1背包问题、装载问题。

遍历子集树时间复杂度：O（2^n）

2、排列树
当问题是：确定n个元素满足某种排列时，用排列数。常见问题：TSP旅行商问题，N皇后问题。

遍历排列树时间复杂度：O（n!）

通俗地讲，结合Java集合的概念，选择哪种树其实就是看最后所得结果是放入一个List（有序）里，还是放入一个Set（无序）里。

剪枝函数能极大提高搜索效率，遍历解空间树时，对于不满足条件的分支进行剪枝，因为这些分支一定不会在最后所求解中。

常见剪枝函数：

约束函数（对解加入约束条件）、限界函数（对解进行上界或下界的限定）

满足约束函数的解才是可行解。

1、0/1背包问题

2、TSP旅行商问题

3、最优装载问题

4、N-皇后问题

具体问题可网络详细内容。

5. 什么是回溯算法

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为： 1、定义一个解空间，它包含问题的解。 2、利用适于搜索的方法组织解空间。 3、利用深度优先法搜索解空间。 4、利用限界函数避免移动到不可能产生解的子空间。 问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。 1.跳棋问题： 33个方格顶点摆放着32枚棋子，仅中央的顶点空着未摆放棋子。下棋的规则是任一棋子可以沿水平或成垂直方向跳过与其相邻的棋子，进入空着的顶点并吃掉被跳过的棋子。试设计一个算法找出一种下棋方法，使得最终棋盘上只剩下一个棋子在棋盘中央。 算法实现提示 利用回溯算法，每次找到一个可以走的棋子走动，并吃掉。若走到无子可走还是剩余多颗，则回溯，走下一颗可以走动的棋子。当吃掉31颗时说明只剩一颗，程序结束。 2.中国象棋马行线问题： 中国象棋半张棋盘如图1(a)所示。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。比如 图4（a）中所示为一种跳行路线，并将所经路线打印出来。打印格式为： 0，0->2,1->3,3->1,4->3,5->2,7->4,8… 算法分析： 如图1(b),马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为： 1: （i,j）→（i+2,j+1）； (i<3,j<8) 2: （i,j）→（i+1,j+2）； (i<4,j<7) 3: （i,j）→（i-1,j+2）； (i>0,j<7) 4: （i,j）→（i-2,j+1）； (i>1,j<8) 搜索策略： S1:Ａ[１]:=(0,0); S2:从Ａ[1]出发，按移动规则依次选定某个方向，如果达到的是（4,8）则转向S3,否则继续搜索下 一个到达的顶点； S3:打印路径。 算法设计： procere try(i:integer); {搜索} var j:integer; begin for j:=1 to 4 do {试遍4个方向} if 新坐标满足条件 then begin 记录新坐标; if 到达目的地 then print {统计方案，输出结果} else try(i+1); {试探下一步} 退回到上一个坐标，即回溯; end; end;

6. 跪求算法大牛解释一下青蛙跳，也就是绿色和褐色青蛙互换问题的回溯算法！！！

Frog[191] ：初始化游戏中的n只青蛙，以1-n/2代表左边的青蛙，n/2+1-n代表右边的青蛙，
Frog[]初始化即为青蛙最初的位置，如果输入n=7，Frog[]={1,2,3,0,4,5,6}
Done[191] ：该数组值只取0或1，其中1代表用于表示此刻，在第i(1-n) 墩上的青蛙已换位成功。反之，取0。
DO[1926] ：该数组用于记录空墩移位的状况，元素的取值范围为0-n-1(在计算机中的表示)。根据在第i步，可以根据元素值DO[i-1] 进行回溯操作。
这个算法中DO[ ]记录的是石头的移动步骤，回溯的其实是回溯DO[ ]，返回上一步的操作

7. 暴力穷举和回溯法（八皇后问题）

以前每次遇到算法问题都是直接暴力求解，一直以为自己用的是暴力穷举法，现在学了回溯法，发现部分问题其实使用的是回溯法，而不是单纯的暴力穷举。

例如求解一个n皇后问题：

1.使用暴力穷举，由于没有两个皇后能够放在一列上，激尘樱那么解向量一定是数1，2，····，n的一个排列（第一行n种放法，第二行n-1种，以此类推）。时间复杂度O(n!).

为什么是一维而不是两维？因为没有两个皇后能在同一列，所以只用行标志就可以表示出皇后的位置，简化了问题

2.回溯法，就等于是一个一个的试，从1到n，时间复杂度O(n^n),每一行n种放法，总共n行。

看起来回溯法要比暴力穷举差很多，但是实际上回溯法很多时候实际算法复杂度并没有暴力穷举高。比如4皇后问题中，仅需要341个可能节点中的27个节点就可以找到解，但是暴力穷举实际会慢很多。

换一个思路，比如第一个皇后放在了0位置，暴力穷举第二个皇后放在1位置，那么之后的皇后无论怎么放都是错误的，也就是(n-2)!个向量全部都是错误的，而回溯法面对这种问题，会在之前就直接抛弃这种兄塌情况，速度会快很多。不要问为什么暴力穷举为什么不学回溯法那样提前抛弃，因为它是 暴力穷举 （这还算优化过一次，不然直接O(n^n)）。

总而言之，回溯法并不明丛需要得到所有情况，而且运行过程中会提前抛弃不合要求的情况，所以算法复杂度一般不会到最差的情况。