初识回溯算法

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

一、定义一个解空间，它包含问题的解。

二、利用适于搜索的方法组织解空间。

三、利用深度优先法搜索解空间。

四、利用限界函数避免移动到不可能产生解的子空间。

问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

下面通过一个具体实例加深大家对回溯算法的认识。

例：骑士游历（ 1997 年全国青少年信息学（计算机）奥林匹克分区联赛高中组复赛试题第三题）

设有一个 n × m 的棋盘 (2<=n<=50,2<=m<=50), 如图 1, 在棋盘上任一点有一个中国象棋马，

图 1

马走的规则为：

1 、马走日字 2 、马只能向右走

即如图 2 所示：

图 2

图 3

图 4

任务 1 ：当 n ， m 输入之后 , 找出一条从左下角到右上角的路径。

例如：输入 n=4 ， m =4 。

输出：路径的格式： (1,1)->(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

如果用树形结构来组织问题的解空间（如图5），那么寻找从起点到终点的路径的过程 , 实际上就是从根结点开始，使用深度优先方法对这棵树的一次搜索过程。

对于任务一，要寻找一条从起点到终点的路径，为了确保路径上的点不被丢失，我们可以在程序中设置一个栈，用它来保存搜索过程中象棋马移动到的每一个点。

算法程序如下：
将起点作为当前位置
do while 不是终点
是否有可以移动的相邻位置？
if 有可以移动的相邻位置 then

将当前位置入栈

移动到相邻位置
else

若栈空，结束寻找过程，并返回0

回溯到栈顶中的位置

endif

loop

在求精以上算法程序的过程中，还存在这样一个问题：怎样从当前位置herep移动到它的相邻位置？题目规定，象棋马有四种移动方法，如图2。从左到右，我们分别给四种移动方法编号为0、1、2、3；对每种移动方法，可以用横坐标和纵坐标从起点到终点的偏移值来表示，并将这些表示移动方法的偏移值保存在一个数组pyz中，如下表

编号 (i)	pyz(i).xzb	pyz(i).yzb	方向
0	2	1	右上
1	2	-1	右下
2	1	2	右上
3	1	-2	右下

从当前位置搜索它的相邻位置的时候，为了便于程序的实现，我们可以按照移动编号的固定顺序来进行，比如，首先尝试第0种移动方法，其次尝试第1种移动方法，再次尝试第2种移动方法，最后尝试第3种移动方法。

任务一参考程序如下：

cls

type dian
xzb as integer
yzb as integer
end type
dim pyz(3) as dian, lj(50) as dian
dim herep as dian, nextp as dian
dim m as integer, n as integer
rem初始化偏移值
pyz(0).xzb = 2: pyz(0).yzb = 1
pyz(1).xzb = 2: pyz(1).yzb = -1
pyz(2).xzb = 1: pyz(2).yzb = 2
pyz(3).xzb = 1: pyz(3).yzb = -2
rem初始化当前位置
herep.xzb = 1: herep.yzb = 1
input "please input m and n:", m, n
rem在m×n的棋盘上寻找从左下角到右上角的一条路径
def fnfind (m, n)
rem初始化变量opti（用来标识是哪种移动方法）和栈顶元素指针k
opti = 0: k = 0
rem是否可以向下一位置移动
do while not (herep.xzb = m and herep.yzb = n)
do while opti <= 3
r = herep.xzb + pyz(opti).xzb
c = herep.yzb + pyz(opti).yzb
if r <= m and c <= n and c >= 1 then exit do
opti = opti + 1
loop
rem若可以向下一位置移动，就移动到下一位置
if opti <= 3 then
k = k + 1: lj(k).xzb = herep.xzb
lj(k).yzb = herep.yzb
herep.xzb = r: herep.yzb = c
opti = 0
rem若不能再向下移动，就回溯
else
rem若栈空，则返回0，并结束寻找
if k = 0 then
fnfind = 0
exit def
end if
rem栈顶元素出栈，并存入nextp
nextp.xzb = lj(k).xzb
nextp.yzb = lj(k).yzb
k = k – 1
rem确定下一种移动方法
if herep.xzb - nextp.xzb = 2 then
if herep.yzb > nextp.yzb then
opti = 1
else pti = 2
end if
elseif herep.yzb > nextp.yzb then
opti = 3
end if
rem产生新的当前位置herep
herep.xzb = nextp.xzb
herep.yzb = nextp.yzb
end if
loop
fnfind = 1
end def
zd = fnfind(m, n)
if zd = 1 then
for i = 1 to k
print "("; lj(i).xzb; ","; lj(i).yzb; ")->";
next i
print "("; m; ","; n; ")"
else print "No"
end if
end
对于任务二，要找出从起点到终点的所有路径的数目。我们可以设置一个统计变量ljs。在搜索解空间的过程中，每当搜索到一条从起点到终点的路径，就让统计变量ljs的值增1。这样，当对解空间的搜索过程结束之后，统计变量ljs的值就是问题的答案。
算法程序如下：
1．初始化统计变量
2．寻找从起点到终点的所有路径
3．输出答案（统计变量ljs的值）
其中第2步需要求精。
回溯是实现递归过程的一种有效方法，利用递归过程的层层调用及层层返回，每次返回，都返回到调用语句的下一条语句继续执行的特点，从当前位置通往终点的所有路径的寻找过程，我们使用递归回溯很容易得以实现。
任务二参考程序如下：
declare sub try (x as integer, y as integer)
cls
type dian
xzb as integer
yzb as integer
end type
dim shared pyz(3) as dian
dim shared qidian as dian, zhongdian as dian
dim shared ljs as integer, m as integer, n as integer
input "please input m and n:", m, n
input "starting point:", qidian.xzb, qidian.yzb
input "end point:", zhongdian.xzb, zhongdian.yzb
rem初始化偏移值
pyz(0).xzb = 2: pyz(0).yzb = 1
pyz(1).xzb = 2: pyz(1).yzb = -1
pyz(2).xzb = 1: pyz(2).yzb = 2
pyz(3).xzb = 1: pyz(3).yzb = -2
rem初始化变量ljs（用来统计路径的数目）
ljs = 0
rem寻找从起点到终点的所有路径
call try(qidian.xzb, qidian.yzb)
print ljs
end
rem寻找从当前位置(x,y)通往终点的所有路径
sub try (x as integer, y as integer)
for i = 0 TO 3
rem保存当前位置
x0 = x: y0 = y
rem移动到相邻位置
x = x + pyz(i).xzb: y = y + pyz(i).yzb
rem若已经走到终点（即找到一条路径），就让路径数加1
if x = zhongdian.xzb and y = zhongdian.yzb then
ljs = ljs + 1
else
rem若可以继续向下移动，则递归调用过程try
if x <= zhongdian.xzb and y <= n and y >= 1 then
call try(x, y)
end if
end if
rem释放当前位置
x = x0: y = y0
next i
end sub