回溯法“>算法—>回溯法

设问：某人要从a路口经过4个路口（含起始路口和目的路口）到达b路口，已知该地区的道路有一个特点：除起点和终点外，每个路口都有三条叉路。请找出一条可行的路线。
首先，我们应该分析出我们所能找到的有关信息：
1、从起始地到目的地一共有4个路口；
2、除起点和终点外，每个路口都有三条叉路；
要解决这一问题，首先我们应该将地形图转换为较规范的路径图，其中路径图中的结点对应地图的路口，路径图中的连线对应地图的路；然后尝试着找出某种规则进行路的探求。当在某个路口走不通时就回头另找一条新的路，当发现了目标地址就可以停止寻找。
从问题的某一种可能情况出发, 搜索所有能达到的可能情况，然后再以其中的一种可能情况为新的出发点，继续向下探求，这样就走出了一条“路”。当这一条路走到“ 尽头”的时候, 再倒回上个出发点, 从另一个可能情况出发, 继续搜索。这种不断“回溯”寻找目标的方法, 称作“回溯法”。
回溯法的基本思想是穷举搜索。一般适用于寻找解集或找出满足某些约束条件的最优解的问题。这些问题所具有的共性是顺序性，即必须先探求第一个步，确定第一步采取的可能值，再探求第二个步采取的可能值，然后是第三步，……，直到达到目标状态。
结合设问，我们很容易找出问题所涉及到的数据与路径图之间的对应关系：路口所在的层数表示探求步数对应的编号，每个路口的分叉表示从该情况出发所有可能的情况。
在数据的具体描述中，为体现探求步骤的顺序性，可以将层数用整数来表示；为表示每个出发点的规律性，我们通常将情况归纳一下，并用顺序出现的整数表示。
对于每个路口而言，其分叉的形式应是一致的。因此通常情况下我们用整数来表示，由于每个路口都有三个分叉，那么我们可以根据分叉出现的顺序从左向右依次用整数1，2，3进行编号就可以了。
在程序中我们可以用数组a存放路径，其中下标表示探求的步数编号，数组元素a[k]的值表示在第k步所采取的可能值的编号。这样对路的探求方法都可以用以下的代码表示：
procedure find (k:integer)； {找第k步的可能性}
begin
if 到目的地 {表示一条路已找出}
then
begin
输出路线；
结束探求
end
else
if k<=4
then
for i:=1 to 3 do {穷举三种可能的方向并记录下来}
begin
　　　 a[k]:=i；
find(k+1)
end
end；
由此可知，根据每个结点探求具有共性这个特点，在实现中我们通常采用递归的算法来实现回溯策略。下面给出的是对于该递归算法的非递归代码:
begin
a[1]:=1；k:=1； {确定起步的路口号及寻找的初始方向}
while 未到目的地 do
begin
while a[k] 无路可走 do {回溯，返回第K-1个路口，另找一条路}
begin
k:=k-1；
a[k]:=a[k]+1
end；
k:=k+1；a[k]:=1； {设定从K+1个路口开始寻找的初始方向}
end；
输出路线；
end；
通过观察，我们可以发现实现回溯算法的特性：在解决过程中首先必须要先为问题定义一个解的空间，这个空间必须包含问题的一个解。在搜索路的同时也就产生了新的解空间。在搜索期间的任何时刻，仅保留从起始点到当前点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。
回溯的策略是一种常见的策略。它可以避免对规模很大的候选解进行一次性检查，因此适用于一些求解规模很大的问题。在具体实现过程中我们应该以找出解题方法与路径图对应的数据关系为切入口，使用递归的算法加以实现。使用回溯策略，我们通常解决自然数的排列、n皇后问题、迷宫问题、数的拆分、0/1背包问题、旅行商问题、货船装货和图形覆盖正方形等问题。