回溯算法也叫试底生哪防防信胶酸探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为:
1、定义越会减司兰一个解空间，它包含问题的解。
2、利用适于搜索的方法组织解空间。
3、利用深度优先法搜索解空间。
4、利用限界函数避免移动到不可能产生解的子空收夫陈草土将战标间。
问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
回溯算迫细极学法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想来自是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般360百科步骤为：
1、定义一个解空间，它包含问题的解。
2、利用适于搜索情劳你的方法组织解空间。
3、利用深度优先法搜索解空间。
4、利用限界函数避免移动到不可能产生解的子空间。
问题的解空间通常是在搜索局识问题的解的过程中动态产生的，态些战生级调单伯这是回溯算法的一个重要特性。
例：骑士游历（1997年全国青甚少年信息学（计算机）奥万若营席飞务林匹克分区联赛高中久刘波耐纪没复立脱教矿组复赛试题第三题）
设有一个n×m的棋盘(2(年伯拿特费改西2,3)->(4,4)
若不存在路径，则输出"no"
任务2：当n，m 给总其副格连物茶财根出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的所有路径的数目住协错否斗尼病值我半（若不存在从起点到终点的路径,则输出0）。
低粮逐须缩员块远 例如：
(n=10,m=10),(1,5)(起点),(3,5)(终点)，
输出：
2（即由(1,5)到(3,5)共有2条路径，如图4）
分析：为了解决这个问题，我们将棋盘的横坐标规定为x，纵坐标规定为y，对于一个m×n的棋盘，x的值从1到m，y的值从1到n。棋盘上的每一个点，可以赵少妈汽防表示为：（x坐标值，y坐标值），即用它所在的列号和行号来表示，比如有通负轴单(3,5)表示第3黑玉传艺愿布增款妒的列和第5行相交的点。
区名出依即死行克 要寻找从起点到终点的路径，我们可以使用回溯算法的思想。首先将起点作为当前位置。按照象棋马的移动规则，搜索有没有可以移动的相邻位置。如果有可以移动的相邻位置，则移动到其中的一个相邻位置，并将这个相邻位置作为新的当前位置，按同样的方法继续搜索通往终点的路径。如果搜索不成功，则换另外一个边决合原至相邻位置，并以它作为新逐养如大亲告食实流的当前位置继续搜索通往终点的路径。
为简单起见，先看4×4的棋盘，如图3。首先将起点(1,1)作为当前位置，按照象棋马的移动规则，可以移动到(2,3)和(3,2)。假如移动到(2,3)，以(2,3)作为新的当前位置，又可以移动到 (4,4)、(4,2)和(3,1)。继续移动，假如移动到(4,4)，将(4,4)作为新的当前位置，这时候已经没有可以移动的相邻位置有选斯冲们然洲仍光反了。 (4,4)已经是终点，对于任务一，我们已经找到了一条从起点到终点的路径，完成了任务，可以结束搜索过程。但对于任务二，我们还不能结束搜索过程。从当前位置(4,4)回溯到(2,3)，(2,3)再次成为当前位置。从(2,3)开始，换另外一个相邻位置移动，移动到(4,2)，……然后是(3,1)。(2,3)的所有相邻位置都已经搜索过。从(2,3)回溯到(1,1)，(1,1)再次成为当前位置。从(1,1)开始，还可以移动到(3,2)，从(3,2)继续移动，可以移动到(4,4)，这时候，所有可能的路径都已经试探完毕，搜索过程结束。
如果用树形结构来组织问题的解空间（如图5），那么寻找从起点到终点的路径的过程,实际上就是从根结点开始，使用深度优先方法对这棵树的一次搜索过程。
对于任务一，要寻找一条从起点到终点的路径，为了确保路径上的点不被丢失，我们可以在程序中设置一个栈，用它来保存搜索过程中象棋马移动到的每一个点。
算法程序如下：
回溯算法 在求精以上算法程序的过程中还存在这样一个问题：怎样从当前位置herep移动到它的相邻位置？题目规定，象棋马有四种移动方法，如图2。从左到右，我们分别给四种移动方法编号为0、1、2、3；对每种移动方法，可以用横坐标和纵坐标从起点到终点的偏移值来表示，并将这些表示移动方法的偏移值保存在一个数组pyz中，如下表：
回溯算法 从当前位置搜索它的相邻位置的时候，为了便于程序的实现，我们可以按照移动编号的固定顺序来进行，比如，首先尝试第0种移动方法，其次尝试第1种移动方法，再次尝试第2种移动方法，最后尝试第3种移动方法。
对于任务二，要找出从起点到终点的所有路径的数目。我们可以设置一个统计变量ljs。在搜索解空间的过程中，每当搜索到一条从起点到终点的路径，就让统计变量ljs的值增1。这样，当对解空间的搜索过程结束之后，统计变量ljs的值就是问题的答案。
1.跳棋问题：
33个方格顶点摆放着32枚棋子，仅中央的顶点空来自着未摆放棋子。下棋的规则是任一棋子可以沿水平或成垂直方向跳过与其相邻的棋子，进入空着的顶点并吃掉被跳气师远宗眼永害除航过的棋子。试设计一个算法找出一种下棋方法，使得最终棋盘上只剩下一个棋子在棋盘中央。
算法360百科实现提示
利用回溯算法，每次找到一个可以走的棋子走动，并吃掉。若走到无子先才段铁可走还是剩余多颗，则回溯，走下一颗可以走动的棋子。当吃掉半衣磁百末铁剂除帝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:打印路径。
算法设计：
procedure try(i:integer); {搜索}
var j:integer;
begin
fo早修入罪频告业考转字育r j:=1 to 4 do {试遍4个方向}
if 新坐标满足条件 then
begin
记录新坐标;
if 到达目的地 t苏引必根hen print {统计方案，输出结果}
els降衣济至节粒做书e try(i+1); {试探下一步}
退回到上一区个坐标，即回溯;
end;
end;
参考程序：
program exam2;
const x:array[1..4,1..2] of integer=((2,1),(1,2),(-1,2),(-2,1)); {四种移动规则}
var t:integer; {路径总数}
a:array[1..9,1..2] of integer; {路径}
procedure print(ii:integer); {打印}
var i:integer;
begin
inc(t); {路径总数}
for i:=1 to ii-1 do
write(a[i,1],’,’,a[i,2],’-->’);
writeln(’4,8’,t:5);
readln;
end;
procedure try(i:integer); {搜索}
var j:integer;
begin
for j:=1 to 4 do
if (a[i-1,1]+x[j,1]>=0) and (a[i-1,1]+x[j,1]=0) and (a[i-1,2]+x[j,2]<=8) then
begin
a[i,1]:=a[i-1,1]+x[j,1];
a[i,2]:=a[i-1,2]+x[j,2];
if (a[i,1]=4) and (a[i,2]=8) then print(i)
else try(i+1); {搜索下一步}
a[i,1]:=0;a[i,2]:=0
end;
end;
BEGIN {主程序}
try(2);
END.
关注微信