初识回溯算法

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

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

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

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

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

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

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

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

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

从当前位置搜索它的相邻位置的时候，为了便于程序的实现，我们可以按照移动编号的固定顺序来进行，比如，首先尝试第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
en d 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 opti = 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
注：此文刊于《中学生电脑》杂志2003年第2期