试探与回溯
忒修斯法宝
[! note] 忒修斯的法宝与回溯策略 古希腊神话中半人半牛的怪物弥诺陶洛斯（Minotaur），藏身于一个精心设计、结构极其复杂的迷宫之中。因此，找到并消灭它绝非易事，而此后如何顺利返回而不致困死更是一个难题。不过，在公主阿里阿德涅（Ariadne）的帮助下，英雄忒修斯（Theseus）还是想出了个好办法，他最终消灭了怪物，并带着公主轻松地走出迷宫。 实际上，忒修斯所使用的法宝，只不过是一团普通的线绳。他将线绳的一端系在迷宫的入口处，而在此后不断检查各个角落的过程中，线团始终握在他的手中。线团或收或放，跟随着忒修斯穿梭于蜿蜒曲折的迷宫之中，确保他不致迷路。
旅行商问题 traveling salesman problem
其目标是计算出由给定的 n 个城市构成的一个序列，使得按此序列对这些城市的环游成本（比如机票价格）最低。
尽管此类问题本身的描述并不复杂，但遗憾的是，由于所涉及元素（比如城市）的每一排列都是一个候选解，它们往往构成一个极大的搜索空间。通常，其搜索空间的规模与全排列总数大体相当，为 n! = O (n^n)。因此若采用蛮力策略，逐一生成可能的候选解并检查其是否合理，则必然无法将运行时间控制在多项式的范围以内。
剪枝
为此，必须基于对应用问题的深刻理解，利用问题本身具有的某些规律尽可能多、尽可能早地排除搜索空间中的候选解。其中一种重要的技巧就是，根据候选解的某些局部特征，以候选解子集为单位批量地排除。通常如图所示，搜索空间多呈树状结构，而被排除的候选解往往隶属于同一分支，故这一技巧也可以形象地称作剪枝（pruning）：
与之对应的算法多呈现为如下模式：
- 从零开始，尝试逐步增加候选解的长度。
- 更准确地，这一过程是在成批地考查具有特定前缀的所有候选解。
这种从长度上逐步向目标解靠近的尝试，称作试探（probing）。作为解的局部特 征，特征前缀在试探的过程中一旦被发现与目标解不合，则收缩到此前一步的长度，然后继续试探下一可能的组合。特征前缀长度缩减的这类操作，称作回溯（backtracking），其效果等同于剪枝。
如此，只要目标解的确存在就迟早会被发现，而且只要剪枝所依据的特征 设计得当，计算的效率就会大大提高。
线绳与粉笔
回到开头的传说故事。不难看出，忒修斯藉以探索迷宫的正是试探回溯法。当然，这一方法的真正兑现还依赖于有形的物质基础——忒修斯的线绳。忒修斯之所以能够在迷宫中有条不紊地进行搜索，首先是得益于这团收放自如的线绳。这一点不难理解，所有算法的实现都必须建立在特定的数据结构之上。
以下两个实例，将介绍如何借助适当的数据结构以高效地实现试探回溯策略。我们将看到，栈结构在此过程中所扮演的正是忒修斯手中线绳的角色。当然，这里还需解决故事中隐含的另一技术难点：如何保证搜索过的部分不被重复搜索。办法之一就是，在剪枝的位置留下某种标记。同样地，这类标记也需兑现为具体的数据结构。倘若建议忒修斯在回溯时不妨用粉笔就地做个记号，那么我们的算法也应配有以数据结构形式实现的“粉笔”。
八皇后问题
问题描述
国际象棋中皇后的势力范围覆盖其所在的水平线、垂直线以及两条对角线。现考查如下问题：在 n x n 的棋盘上放置 n 个皇后，如何使得她们彼此互不攻击——此时称她们构成一个可行的棋局。对于任何整数 n >= 4，这就是 n 皇后问题。
由鸽巢原理可知，在 n 行 n 列的棋盘上至多只能放置 n 个皇后。反之，n 个皇后在 n x n 棋盘上的可行棋局通常也存在，比如图 b 即为在 8 x 8 棋盘上，由 8 个皇后构成的一个可行棋局。
皇后的实现
struct Queen { //皇后类
int x, y; //皇后在棋盘上的位置坐标
Queen ( int xx = 0, int yy = 0 ) : x ( xx ), y ( yy ) {};
bool operator== ( Queen const& q ) const { //重载判等操作符，以检测不同皇后之间可能的冲突
return ( x == q.x ) //行冲突（这一情况其实并不会发生，可省略）
|| ( y == q.y ) //列冲突
|| ( x + y == q.x + q.y ) //沿正对角线冲突
|| ( x - y == q.x - q.y ); //沿反对角线冲突
}
bool operator!= ( Queen const& q ) const {
return ! ( *this == q ); } //重载不等操作符
};
算法实现
基于试探回溯策略，可如代码所示，实现通用的 N 皇后算法：
void placeQueens ( int N ) { //N皇后算法（迭代版）：采用试探/回溯策略，借助栈记录查找的结果
Stack<Queen> solu; //存放（部分）解的栈
Queen q ( 0, 0 ); //从原点位置出发
do { //反复试探、回溯
if ( N <= solu.size() || N <= q.y ) { //若已出界，则
q = solu.pop(); q.y++; //回溯一行，并继续试探下一列
} else { //否则，试探下一行
while ( ( q.y < N ) && ( 0 <= solu.find ( q ) ) ) //通过与已有皇后的比对
{ q.y++; nCheck++; } //尝试找到可摆放下一皇后的列
if ( N > q.y ) { //若存在可摆放的列，则
solu.push ( q ); //摆上当前皁后，并
if ( N <= solu.size() ) nSolu++; //若部分解已成为全局解，则通过全局变量nSolu计数
q.x++; q.y = 0; //转入下一行，从第0列开始，试探下一皇后
}
}
} while ( ( 0 < q.x ) || ( q.y < N ) ); //所有分支均已或穷举或剪枝后，算法结束
}
既然每行能且仅能放置一个皇后，故不妨首先将各皇后分配至每一行。然后，从空棋盘开始，逐个尝试着将她们放置到无冲突的某列。每放置好一个皇后，才继续试探下一个。若当前皇后在 任何列都会造成冲突，则后续皇后的试探都必将是徒劳的，故此时应该回溯到上一皇后。
这里借助栈 solu 来动态地记录各皇后的列号。当该栈的规模增至 N 时，即得到全局解。该栈即可依次给出各皇后在可行棋局中所处的位置。
实例
首先试探第一行皇后，如图 (a)所示将其暂置于第 0 列，同时列号入栈。接下来试探再第二行皇后，如图 (b)所示在排除前两列后，将其暂置于第 2 列，同时列号入栈。然而此后试探第三行皇后时，如图 (c)所示发现所有列均有冲突。于是回溯到第二行，并如图 (d)所示将第二行皇后调整到第 3 列，同时更新栈顶列号。后续各步原理相同，直至图 (l)栈满时得到一个全局解。
如此不断地试探和回溯，即可得到所有可行棋局。可见，通过剪枝我们对原规模为 4! = 24 的搜索空间实现了有效的筛选。随着问题规模的增加，这一技巧的优化效果将更为明显。
迷宫寻径
问题描述
路径规划是人工智能的基本问题之一，要求依照约定的行进规则，在具有特定几何结构的空间区域内，找到从起点到终点的一条通路。以下考查该问题的一个简化版本：空间区域限定为由 n x n 个方格组成的迷宫，除了四周的围墙，还有分布其间的若干障碍物；只能水平或垂直移动。我们的任务是，在任意指定的起始格点与目标格点之间，找出一条通路（如果的确存在）。
迷宫格点实现
typedef enum { AVAILABLE, ROUTE, BACKTRACKED, WALL } Status; //迷宫单元状态
//原始可用的、在当前路径上的、所有转向均尝试失败后回溯过的、不可使用的（墙）
typedef enum { UNKNOWN, EAST, SOUTH, WEST, NORTH, NO_WAY } ESWN; //单元的相对邻接方向
//未定、东、南、西、北、无路可通
inline ESWN nextESWN ( ESWN eswn ) { return ESWN ( eswn + 1 ); } //依次转至下一邻接方向
struct Cell { //迷宫格点
int x, y; Status status; //x坐标、y坐标、类型
ESWN incoming, outgoing; //进入、走出方向
};
#define LABY_MAX 24 //最大迷宫尺寸
Cell laby[LABY_MAX][LABY_MAX]; //迷宫
可见，除了记录其位置坐标外，格点还需记录其所处的状态。共有四种可能的状态：
- 原始可用的（AVAILABLE）、
- 在当前路径上的（ROUTE）、
- 所有方向均尝试失败后回溯过的（BACKTRACKED）、
- 不可穿越的（WALL）。
属于当前路径的格点，还需记录其前驱和后继格点的方向。既然只有上、下、左、右四个连通方向，故以 EAST、SOUTH、WEST 和 NORTH 区分。特别地，
- 因尚未搜索到而处于初始 AVAILABLE 状态的格点，邻格的方向都是未知的（UNKNOWN）；
- 经过回溯后处于 BACKTRACKED 状态的格点，与邻格之间的连通关系均已关闭，故标记为 NO_WAY。
邻格查询
在路径试探过程中需反复确定当前位置的相邻格点，可如代码所示实现查询功能。
inline Cell* neighbor ( Cell* cell ) { //查询当前位置的相邻格点
switch ( cell->outgoing ) {
case EAST : return cell + LABY_MAX; //向东
case SOUTH : return cell + 1; //向南
case WEST : return cell - LABY_MAX; //向西
case NORTH : return cell - 1; //向北
default : exit ( -1 );
}
}
邻格转入
在确认某一相邻格点可用之后，算法将朝对应的方向向前试探一步，同时路径延长一个单元。 为此，需如代码所示实现相应的格点转入功能。
inline Cell* advance ( Cell* cell ) { //从当前位置转入相邻格点
Cell* next;
switch ( cell->outgoing ) {
case EAST: next = cell + LABY_MAX; next->incoming = WEST; break; //向东
case SOUTH: next = cell + 1; next->incoming = NORTH; break; //向南
case WEST: next = cell - LABY_MAX; next->incoming = EAST; break; //向西
case NORTH: next = cell - 1; next->incoming = SOUTH; break; //向北
default : exit ( -1 );
}
return next;
}
寻径算法
// 迷宫寻径算法：在格单元s至t之间规划一条通路（如果的确存在）
bool labyrinth ( Cell Laby[LABY_MAX][LABY_MAX], Cell* s, Cell* t ) {
if ( ( AVAILABLE != s->status ) || ( AVAILABLE != t->status ) ) return false; //退化情况
Stack<Cell*> path; //用栈记录通路（Theseus的线绳）
s->incoming = UNKNOWN; s->status = ROUTE; path.push ( s ); //起点
do { //从起点出发不断试探、回溯，直到抵达终点，或者穷尽所有可能
Cell* c = path.top(); //检查当前位置（栈顶）
if ( c == t ) return true; //若已抵达终点，则找到了一条通路；否则，沿尚未试探的方向继续试探
while ( NO_WAY > ( c->outgoing = nextESWN ( c->outgoing ) ) ) //逐一检查所有方向
if ( AVAILABLE == neighbor ( c )->status ) break; //试图找到尚未试探的方向
if ( NO_WAY <= c->outgoing ) //若所有方向都已尝试过
{ c->status = BACKTRACKED; c = path.pop(); }//则向后回溯一步
else //否则，向前试探一步
{ path.push ( c = advance ( c ) ); c->outgoing = UNKNOWN; c->status = ROUTE; }
} while ( !path.empty() );
return false;
}
该问题的搜索过程中，局部解是一条源自起始格点的路径，它随着试探、回溯相应地伸长、 缩短。因此，这里借助栈 path 按次序记录组成当前路径的所有格点，并动态地随着试探、回溯 做入栈、出栈操作。路径的起始格点、当前的末端格点分别对应于 path 的栈底和栈顶，当后者 抵达目标格点时搜索成功，此时 path 所对应的路径即可作为全局解返回。
实例
左侧为随机生成的 13 x 13 迷宫。算法启动时，其中格点分为可用（AVAILABLE，白色）与障碍（WALL，黑色）两种状态。在前一类中，随机指定了起始格点（+）和目标格点（$)。 中图为算法执行过程的某一时刻，可见原先为可用状态的一些格点已经转换为新的状态：转入 ROUTE 状态的格点，依次联接构成一条（尚未完成的）通路；曾参与构成通路但后因所有前进方向均已尝试完毕而回溯的格点，则进而从 ROUTE 转入 TRIED 状态（以圆圈注明）。如右图所示，经过 48 步试探和 6 步回溯，最终找到一条长度为 42 的通路。通过这一实例亦可看出，在起点与终点之间的确彼此连通时，尽管这一算法可保证能够找出一条通路，但却未必是最短的。
正确性和复杂度
该算法会尝试当前格点的所有相邻格点，因此通过数学归纳可知，若在找到全局解后依然继续查找，则该算法可以抵达与起始格点连通的所有格点。因此，只要目标格点与起始格点的确相互连通，则这一算法必将如右图所示找出一条联接于二者之间的通路。
从算法的中间过程及最终结果都可清晰地看出，这里用以记录通路的栈结构的确相当于忒修斯手中的线绳，它确保了算法可沿着正确地方向回溯。另外，这里给所有回溯格点所做的状态标记则等效于用粉笔做的记号，正是这些标记确保了格点不致被重复搜索，从而有效地避免了沿环路的死循环现象。
算法的每一步迭代仅需常数时间，故总体时间复杂度线性正比于试探、回溯操作的总数。由 于每个格点至多参与试探和回溯各一次，故亦可度量为所有被访问过的格点总数——在图 4.10 中，也就是最终路径的总长度再加上圆圈标记的数目。