回溯算法结果分析

Ⅰ 什么是回溯算法

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为： 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;

Ⅱ 谁能解释一下回溯算法

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
初识回溯算法是在解决8皇后问题时候，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有符合位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了
回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。

Ⅲ 回溯算法与贪心算法

回溯是递归的副产品，只要有递归就会有回溯 ，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。

回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。

回溯算法能解决如下问题：

组合问题：N个数里面按一定规则找出k个数的集合

排列问题：N个数按一定规则全排列，有几种排列方式

切割问题：一个字符串按一定规则有几种切割方式

子集问题：一个N个数的集合里有多少符合条件的子集

棋盘问题：N皇后，解数独等等

回溯算法的本质是纵向遍历

回溯算法模板为

贪心的本质是选择每一阶段的局部最优，从而达到全局最优

贪心算法一般分为如下四步：

将问题分解为若干个子问题

找出适合的贪心策略

求解每一个子问题的最优解

将局部最优解堆叠成全局最优解

eg：摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]

输出: 7

解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

Ⅳ 六、递归与回溯算法

在计算机领域里面，很多问题都可以要采用递归算法来解决。递归中，最长用到的方法就是回溯法。我们具体分析问题的时候，可以发现这类问题本质是一个树的形状。

递归算法的本质还是将原来的问题转化为了更小的同一问题，进行解决。一般注意两点：
1、递归终止的条件。对应到了递归算法中最基本的问题，也是最最简单的问题。
2、递归过程。递归过程需要将原问题一步一步的推到更小的 同一 问题，更小的意思就是子问题解决起来就更加的简单。有写情况是能够找到一个递推的公式的。这个过程中就需要透彻的去理解递归函数的意义。明确这个函数的输入和输出是什么，这样来写的话，就清晰多了。

因为有了这样的递归公式，那么我们就很容易的能看出来递归的终止条件就是我们知道的f(0)和f(1)了。有了f(0)和f(1)之后，我们就能够继续的递推出f(3)一直到f(n)了。

但是我们现在才用一个递归算法的思想来解决这个问题:

像我们常见的数据结构如链表、树、图等都是有着天然的递归结构的，链表由于是一个线性的结构，那么通常我们也是能够直接循环遍历就能解决问题的，但是这里我们用递归法来解决一下LeetCode上面的问题
LeetCode 203 移除链表元素
分析：链表的结构可以理解成一个节点连接这一个更短的链表，这样依次一直看下去，直到最后一个节点None，那么我们这个时候的递归终止条件就是head指向None了，返回的就是None

深入的理解递归算法之后，我们就开始进行回溯法的学习。通过LeetCode上面的几道题，我们来深入的探讨一下递归与回溯法的应用。

持续更新中...
数据结构与算法系列博客：
一、数据结构与算法概述
二、数组及LeetCode典型题目分析
三、链表（Linked list）以及LeetCode题
四、栈与队列（Stack and Queue
五、树（Trees）
六、递归与回溯算法
七、动态规划
八、排序与搜索
九、哈希表

参考资料
1、
2、
3、

Ⅳ Pascal算法之回溯及递推详细介绍、

递归 递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能是程序变得简洁和清晰.2.1 递归的概念
1.概念一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).如:procere a; begin . . . a; . . .end;这种方式是直接调用.又如: procere b; procere c; begin begin . . . . . . c; b; . . . . . .end; end;这种方式是间接调用.例1计算n!可用递归公式如下: 1 当 n=0 时 fac(n)={n*fac(n-1) 当n>0时可编写程序如下:program fac2;varn:integer;function fac(n:integer):real;beginif n=0 then fac:=1 else fac:=n*fac(n-1)end;beginwrite('n=');readln(n);writeln('fac(',n,')=',fac(n):6:0);end.例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.设n阶台阶的走法数为f(n)显然有 1 n=1 f(n)={2 n=2 f(n-1)+f(n-2) n>2可编程序如下：program louti;var n:integer;function f(x:integer):integer;beginif x=1 then f:=1 elseif x=2 then f:=2 else f:=f(x-1)+f(x-2);end;beginwrite('n=');read(n);writeln('f(',n,')=',f(n))end.2.2 如何设计递归算法
1.确定递归公式2.确定边界(终了)条件练习:用递归的方法完成下列问题1.求数组中的最大数2.1+2+3+...+n3.求n个整数的积4.求n个整数的平均值5.求n个自然数的最大公约数与最小公倍数6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项. 2.3典型例题例3 梵塔问题 如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子 从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上不能出现大盘压小盘.找出移动次数最小的方案. 程序如下:program fanta;varn:integer;procere move(n,a,b,c:integer);beginif n=1 then writeln(a,'--->',c)else beginmove(n-1,a,c,b);writeln(a,'--->',c);move(n-1,b,a,c);end;end;beginwrite('Enter n=');read(n);move(n,1,2,3);end.例4 快速排序快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.程序如下:program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.练习:1.计算ackerman函数值: n+1 m=0 ack(m,n)={ ack(m-1,1) m<>0 ,n=0 ack(m-1,ack(m,n-1)) m<>0,n<>0 求ack(5,4)
回溯 回溯是按照某种条件往前试探搜索,若前进中遭到失败,则回过头来另择通路继续搜索.3.1 回溯的设计 1.用栈保存好前进中的某些状态.2.制定好约束条件例1由键盘上输入任意n个符号;输出它的全排列.program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;
end;
begin
input;
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.例2.n个皇后问题:program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
begin
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;end.回溯算法的公式如下:3.2 回溯算法的递归实现由于回溯算法用一栈数组实现的,用到栈一般可用递归实现。上述例1的递归方法实现如下：program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;readln;
end;
procere try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
begin
x[k]:=i;
if place(k) then try(k+1)
end
end;
begin
input;
try(1);
end.例2：n皇后问题的递归算法如下：程序1：program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procere try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.程序2：说明:当n=8 时有30条对角线分别用了l和r数组控制，用c数组控制列.当(i,j)点放好皇后后相应的对角线和列都为false.递归程序如下:program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procere output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procere try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if i<n then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c[i]:=true;
for i:=1-n to n-1 do l[i]:=true;
for i:=2 to 2*n do r[i]:=true;
s:=0;try(1);
writeln;
end.练习：1.找出所有从m个元素中选取n(n<=m)元素的组合。2.设有A,B,C,D,E 5人从事j1,j2,j3,j4,j5 5项工作每人只能从事一项,它们的效益表如下:求最佳安排,使效益最高.3.N个数中找出M个数(从键盘上输入正整数N,M后再输入N个正数),要求从N个数中找出若干个数,使它们的和为M,把满足条件的数组找出来,并统计组数.4.地图着色。如下图12个区域用4种颜色着色要求相邻的区域着不同的颜色5.将任意一正整数(1<n<100)分解成若干正整数的和. 如:4=1+1+1+1 =2+1+1 =2+2 =3+1.

Ⅵ 谁能解释一下回溯算法

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
初识回溯算法是在解决8皇后问题时候，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有符合位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了
回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。

Ⅶ 24点问题，回溯算法

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为： 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;beginfor j:=1 to 4 do if 新坐标满足条件 thenbegin记录新坐标;if 到达目的地 then print else try(i+1); 退回到上一个坐标，即回溯;end;end;

Ⅷ 回溯算法的介绍

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：1、定义一个解空间，它包含问题的解。2、利用适于搜索的方法组织解空间。3、利用深度优先法搜索解空间。4、利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

Ⅸ 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.搜索策略多种，有深度优先、宽度优先和跳跃式遍历搜索树。