一 回溯：框架和例子
呵呵，第一次接触搜索了吧。这里我不想讲理论，只是说一说，举个例子。我们使用回溯的法，是搜索的一种控制策略。
搜索可以看成是在解答树中找一条从初始节点到目标节点的路径，因此，我们要先选择一种表示求解过程中的状况的变量。
这就是"状态"(state)。

状态举例：
八皇后问题：当前的棋盘B和当前要放皇后的行号i
经典走迷宫问题：当前走到的位置

另一个概念是算符(operator)
是状态转化的方法代号。例如八皇后问题，因为一行只能放一个皇后，故
算符是选择的列号。即：

选择算符j
状态B1,i --------------->状态B2,i+1
放置皇后在(i,j)

又如：走迷宫问题，算符就是上，下，左，右，因为由一个位置(状态1)选择了上，下，左，右之一的时候到达了另外
一个位置（状态2）。

把状态和算符合在一起，就是节点。
当然，有时候算符是永远不会变的，或者变动很少的，我们可以不存储算符，仅在程序中完成算符枚举。

另一种描述方法是把解变量说成是N元组(x1,x2,x3,x4..xn)，回溯就是依次确定x1,x2,x3..xn。
下面程序中的k就是当前有待确定的xk的下标。当然，下标是多维的情况也是类似处理
（二维变成 procedure search(k1,k2:integer)）

这里我采用递归实现，因为程序很清楚，也不用堆栈，容易编程。

递归回溯法算法框架
procedure search(k:integer);
begin
if k=n+1 then (1)
begin
输出解
exit (2)
end;
保存：使用算符之前的状态
for i:=1 to 算符种数 (3)
begin
使用算符i
search(k+1);
恢复：使用算符之前的状态
end;
end;

注释：
(1)如果n不确定，这里改成一个判断是否到达目标节点的方法。
(2)如果只求一个解，改为halt;
(3)应该去掉不能导致解的算符,也就是剪枝。

下面是求解八皇后问题的程序，我会尽量做到程序容易懂。
var
total:integer;
board:array[1..8] of 1..8;

procedure search(k:integer);
var
i,j:integer;
ok:boolean;
begin
if k=9 then
begin
for i:=1 to 8 do
write(board[i],' ');
writeln;
inc(total);
exit;
end;

for i:=1 to 8 do
begin
ok:=true;
for j:=1 to k-1 do
if (board[j]=i)or(abs(board[j]-i)=abs(j-k)) then
begin
ok:=false;
break;
end;
if ok then
begin
board[k]:=i;
search(k+1);
end;
end;
end;

begin
total:=0;
search(1);
writeln('Total=',total);
end.

想一想，我为什么不保存和恢复状态呢？
对了，在这里没有必要，因为以后根本不可能改变当前的状态的。
但有时候就必须保存。
例如：
如果用一个数组记录第j列是否有皇后，就应该：
if ok then
begin
board[k]:=i;
used[i]:=true;

search(k+1);

used[i]:=false; {恢复状态}
end;

以后遇到更复杂的例子，你才会体会到保护“现场”的重要性。

回溯的好处是编程容易，空间需求相对较小，但是速度比较慢，常需要剪枝。

二 剪枝
应该说，搜索的题目比以前少了不少，但是仍然是一种十分基本的题型，在分区联赛中几乎每年都有，
IOI2000也出了一道。搜索考查什么呢？主要有两点：搜索空间的建立和搜索的优化。
这里我们讨论优化中的剪枝。

剪枝的英文是prune,这个说法源于“搜索树”的概念。搜索可以看成是在状态空间中找起始节点到目标
节点的路径，构造部分/全部搜索树。当然，构造整个搜索树十分费时，因此需要“剪枝”。
甚至有时会为了追求时间效率会采取有可能丢失解的“过度剪枝”，但它不属于本文讨论范围。

下面推荐一篇论文，是IOI99国家集训队的齐鑫同学的《搜索中的剪枝优化》。
齐鑫是我们IOI2001国家集训队的辅导员，这里我就不罗嗦了。:) (我真懒，呵呵)