回溯算法
搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。
递归回溯法算法框架[一]
procedure Try(k:integer);
begin
for i:=1 to 算符种数 Do
if 满足条件 then
begin
保存结果
if 到目的地 then 输出解
else Try(k+1);
恢复：保存结果之前的状态{回溯一步}
end;
end;
递归回溯法算法框架[二]
procedure Try(k:integer);
begin
if 到目的地 then 输出解
else
for i:=1 to 算符种数 Do
if 满足条件 then
begin
保存结果
Try(k+1);
end;
end;
例 1：素数环：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。【算法分析】非常明显，这是一道回溯的题目。从1 开始，每个空位有 20（19）种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第 20个数还要判断和第1个数的和是否素数。
〖算法流程〗1、数据初始化； 2、递归填数：
判断第J种可能是否合法；
A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；
B、如果不合法：选择下一种可能；
【参考程序】
program z74;框架[一]
var a:array[0..20]of byte;
b:array[0..20]of boolean;
total:integer;
function pd(x,y:byte):boolean;
var k,i:byte;
begin
k:=2; i:=x+y; pd:=false;
while (k<=trunc(sqrt(i)))and(i mod k<>0) do inc(k);
if k>trunc(sqrt(i)) then pd:=true;
end;
procedure print;
var j:byte;
begin
inc(total);write('<',total,'>:');
for j:=1 to 20 do write(a[j],' ');
writeln;
end;
procedure try(t:byte);
var i:byte;
begin
for i:=1 to 20 do
if pd(a[t-1],i)and b[i] then
begin
a[t]:=i; b[i]:=false;
if t=20 then begin if pd(a[20],a[1]) then print;end
b[i]:=true;
end;
end;
BEGIN
fillchar(b,sizeof(b),#1);
total:=0;
try(1);
write('total:',total);
END.
通过观察，我们可以发现实现回溯算法的特性：在解决过程中首先必须要先为问题定义一个解的空间．这个空间必须包含问题的一个解。在搜索路的同时也就产生了新的解空间。在搜索期间的任何时刻．仅保留从起始点到当前点的路径。
例 2：设有 n 个整数的集合｛1,2,…,n｝，从中取出任意 r 个数进行排列（r解法一：
program it15; 框架[一]
type se=set of 1..100;
VAR s:se;n,r,num:integer;
b:array [1..100] of integer;
PROCEDURE print;
var i:integer;
begin
num:=num+1;
for i:=1 to r do
write(b[i]:3);
writeln;
end;
PROCEDURE try(k:integer);
VAR i:integer;
begin
for i:=1 to n do
if i in s then
begin
b[k]:=i;
s:=s-[i];
if k=r then print
s:=s+[i];
end;
end;
BEGIN
write('Input n,r:');readln(n,r); s:=[1..n];num:=0;
try(1);
writeln('number=',num);
END.
解法二：
program it15; 框架[二]
type se=set of 1..100;
VAR
s:se;
n,r,num,k:integer;
b:array [1..100] of integer;
PROCEDURE print;
var i:integer;
begin
num:=num+1;
for i:=1 to r do
write(b[i]:3);
writeln;
end;
PROCEDURE try(s:se;k:integer); VAR i:integer;
begin
if k>r then print
else
for i:=1 to n do
if i in s then
begin
b[k]:=i;
