递归回溯算法比较

⑴ 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.

⑵ Pasca算法中的动态规划、递归、回溯、枚举、贪心有什么区别最好举个例子!!速度点！！急啊

我记得以前有一篇180页的pascal算法，我用delphi实现了其中一部分，这些算法都相当有用，但是也是超难，我啃回溯啃了5天。动态规划在分类步骤比较小的情况下用，递归太常用了，回溯就是循环的递归（解决回路嵌套问题），枚举只有情况有限的时候一个个列举出来，贪心就是不求最佳，找一个满足添加的结果就行

⑶ 递推算法和递归算法有什么区别

1、算法的过程不同

递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。

递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。

⑷ 如何理解递归，回溯，动态规划等算法

递归比较简单的，就是递推的逆向算法。例如已知a(10)且a(n)=f(a(n+1))，让你求a(1)。回溯是深度优先搜索必须要用到的方法，推荐你看下“八皇后问题”，看完就应该明白了。动态规划是一种以空间换时间的算法，也就是占用内存较大，但是时间效率比较高的分阶段算法。推荐你看看“拦截导弹”问题，“0/1背包问题”。动态规划先多看看题，然后再去理解概念比较好

⑸ 六、递归与回溯算法

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

递归算法的本质还是将原来的问题转化为了更小的同一问题，进行解决。一般注意两点：
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、

⑹ 回溯 递归的区别是什么

区别就是回溯具有多向选择，设有解决方案集合为{a1,a2,a3,...,an},当a1解决方案不能得到预期的结果时，则退回到a1后面的解决方案继续执行。类似于迷宫求解，当右侧不通时退回上格执行左侧等，以及KMP算法，当模式串失配时，nextValue数组将指示尾指针应退到哪个位置继续匹配。

⑺ java回溯和递归的区别，主要什么回溯怎么用，有代码最好

N皇后问题的非递归迭代回溯法java代码实现
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class NQueen {

static int n; // 皇后个数
static int[] x; // 当前解如{0，2，4，1，3}分别代表第1、2、3、4列的行值
static int totle; // 可行方案个数
public static void main(String[] args) {
int input = 0; //输入n值
int sum = 0; //可行方案个数
String temp; //临时存储输入值
System.out.println("请输入N后问题的N值：");

try {
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
temp = br.readLine();
input = Integer.parseInt(temp); //将输入值转换为int保存
if(input<=0){
throw new IOException("别输负数好不？");
}
System.out.println("输入的数是：" + input);

sum = nQueen(input); //调用nqueen方法

System.out.println("可行方案个数为：" + sum); //输出sum

} catch (IOException e) {
System.out.println(e.getMessage());

}catch (NumberFormatException e){
System.out.println("请输入数字。。。");
}
}
private static int nQueen(int input) {
n = input; //把输入给全局变量n
totle = 0; //初始化totle
x = new int[n + 1];
for (int i = 0; i <= n; i++)
x[i] = 0; //初始化x
backtrack(); //调用回溯算法
return totle;
}
private static void backtrack() {
int k = 1;
while (k > 0) {
x[k] += 1; //第k列皇后向下移一行
while ((x[k] <= n) && !(place(k))){ //如果当前第k列皇后未出界或者和其他皇后冲突
x[k] += 1; //第k列皇后向下移一行继续寻找
System.out.println("在第"+k+"行 "+"第"+x[k]+"列放置皇后");
System.out.print("当前方案为 ");
for(int i=1;i<=k;i++) //打印寻找策略
System.out.print(x[i]+" ");
System.out.println();
}
if (x[k] <= n) //找到一个值并且未出界
if (k == n) { //已是最后一列说明已找到一个方案
totle++;
System.out.print("可行方案为： ");
for (int i = 1; i <= n; i++)
System.out.print(x[i] + " ");
System.out.println();
} else { //不是最后一列故寻找下一列
k++;
x[k] = 0;
}
else //找到的值已经出界，回退到上一列
k--;
}
}
//判断皇后是否冲突
private static boolean place(int k) {
for (int j = 1; j < k; j++)
if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k]))
return false;
return true;
}
}

⑻ 结合骑士问题，说说递归算法和回溯算法的异同点

《我的老师》《我和老师》《我爱老师》
共同点：说的是我、老师
不同点：1.重点是讲诉老师的事2.我和老师之间发生的事3.老师做了哪些事值得我敬爱
《这件事教育了我》《我总想着这件事》《我们班上新事多》
共同点：讲诉一件事或多件事
不同点：1.这件事从哪方面教育了我2.这件事哪方面值得我思考3.我们班上发生的新事多.

⑼ 怎样才能深刻理解递归和回溯

递归是一种算法结构，回溯是一种算法思想，一个递归就是在函数中调用函数本身来解决问题，回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思就是对已经知道错误的结果没必要再枚举接下来的答案了，比如一个有序数列1,2,3,4,5，要找和为5的所有集合，从前往后搜索我选了1，然后2，然后选3 的时候发现和已经大于预期，那么4,5肯定也不行，这就是一种对搜索过程的优化。
回溯分析是追踪决策的特性之一。 是指对原始决策的产生机制、决策内容、主客观环境等进行分析．从起点开始，按顺序考察导致决策失误的原因、问题的性质、失误的程度等。
[算法分析]
为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自已来定义自己的方法，称为递归定义。例如：定义函数f(n)为：
f(n)=n*f(n－1) (n>0)
f(n)=1 (n=0)
则当0时，须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……当n=0时，f(n)=1。
由上例我们可看出，递归定义有两个要素：
（1）递归边界条件。也就是所描述问题的最简单情况，它本身不再使用递归的定义。
如上例，当n=0时，f(n)=1，不使用f(n-1)来定义。
（2）递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。
如上例：f(n)由f(n-1)定义，越来越靠近f(0),也即边界条件。最简单的情况是f(0)=1。
递归算法的效率往往很低, 费时和费内存空间. 但是递归也有其长处, 它能使一个蕴含递归关系且结构复杂的程序简介精炼, 增加可读性. 特别是在难于找到从边界到解的全过程的情况下, 如果把问题推进一步,其结果仍维持原问题的关系, 则采用递归算法编程比较合适.
递归按其调用方式分为: 1. 直接递归, 递归过程P直接自己调用自己; 2. 间接递归, 即P包含另一过程D, 而D又调用P.
递归算法适用的一般场合为:
1. 数据的定义形式按递归定义.
如裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2.
对应的递归程序为:
Function fib(n : integer) : integer;
Begin
if n = 0 then fib := 1 { 递归边界 }
else if n = 1 then fib := 2
else fib := fib(n-2) + fib(n-1) { 递归 }
End;
这类递归问题可转化为递推算法, 递归边界作为递推的边界条件.
2. 数据之间的关系(即数据结构)按递归定义. 如树的遍历, 图的搜索等.
3. 问题解法按递归算法实现. 例如回溯法等.
从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到" 尽头 "
的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断" 回溯 "寻找解的方法, 称作
" 回溯法 ".

[参考程序]
下面给出用回溯法求所有路径的算法框架. 注释已经写得非常清楚, 请读者仔细理解.
Const maxdepth = ????;
Type statetype = ??????; { 状态类型定义 }
operatertype = ??????; { 算符类型定义 }
node = Record { 结点类型 }
state : statetype; { 状态域 }
operater :operatertype { 算符域 }
End;
{ 注: 结点的数据类型可以根据试题需要简化 }
Var
stack : Array [1..maxdepth] of node; { 存当前路径 }
total : integer; { 路径数 }
Procere make(l : integer);
Var i : integer;
Begin
if stack[L-1]是目标结点 then
Begin
total := total+1; { 路径数+1 }
打印当前路径[1..L-1];
Exit
End;
for i := 1 to 解答树次数 do
Begin
生成 stack[l].operater;
stack[l].operater 作用于 stack[l-1].state, 产生新状态 stack[l].state;
if stack[l].state 满足约束条件 then make(k+1);
{ 若不满足约束条件, 则通过for循环换一个算符扩展 }
{ 递归返回该处时, 系统自动恢复调用前的栈指针和算符, 再通过for循环换一个算符扩展 }
{ 注: 若在扩展stack[l].state时曾使用过全局变量, 则应插入若干语句, 恢复全局变量在
stack[l-1].state时的值. }
End;
{ 再无算符可用, 回溯 }
End;
Begin
total := 0; { 路径数初始化为0 }
初始化处理;
make(l);
打印路径数total
End.

⑽ 用递归回溯法设计旅行售货员问题的算法

一、回溯法：
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

二、算法框架：
1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。

2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
运用回溯法解题通常包含以下三个步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；

3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：
procere try(i:integer);
var
begin
if i>n then 输出结果
else for j:=下界 to 上界 do
begin
x[i]:=h[j];
if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end;
end;
end;

说明：
i是递归深度；
n是深度控制，即解空间树的的高度；
可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；

搜索：全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式的搜索。
回溯即是较简单、较常用的搜索策略。
基本思路：若已有满足约束条件的部分解，不妨设为（x1,x2,x3,……xi），I<n,则添加x(i+1)属于s(i+2)，检查(x1,x2,……,xi,x(i+1))是否满足条件，满足了就继续添加x(i+2)、s(i+2)，若所有的x(i+1)属于s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。