概念编辑本段回目录
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：
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枚棋子，仅中央的顶点空着未摆放棋子。下棋的规则是任一棋子可以沿水平或成垂直方向跳过与其相邻的棋子，进入空着的顶点并吃掉被跳过的棋子。试设计一个算法找出一种下棋方法，使得最终棋盘上只剩下一个棋子在棋盘中央。
算法实现提示
利用回溯算法，每次找到一个可以走的棋子走动，并吃掉。若走到无子可走还是剩余多颗，则回溯，走下一颗可以走动的棋子。当吃掉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
for j:=1 to 4 do {试遍4个方向}
if 新坐标满足条件 then
begin
记录新坐标;
if 到达目的地 then print {统计方案，输出结果}
else 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.
