回溯法
- 格式：docx
- 大小：19.23 KB
- 文档页数：3
回溯法
一、回溯法：
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
二、算法框架：
1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。
2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
运用回溯法解题通常包含以下三个步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；
3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：
procedure try(i:integer);
var
begin
if i>n then 输出结果
else for j:=下界 to 上界 do
begin
x[i]:=h[j];
if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end;
end; end;
说明：
i是递归深度；
n是深度控制，即解空间树的的高度；
可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；
二、习题：
1、0-1背包：n=3,w=[16,15,15],p=[45,25,25],c=30
2、旅行售货员问题：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅费）最小。
3、括号检验
题目描述：输入一个代数表达式(只含有+,-,*,/,(,),1,2,3,4,5,6,7,8,9,0等字符,每个数字均小于10),设表达式除括号匹配有误外无其他错误.编程对输入的表达式检验,判断括号匹配是否正确.
正确的:
1+2+4
(1+2)+4
(1+2) 错误的:
(1+)2
(1+2(4+3))
(1+2+3*(4+5()))
1+2+3*(4+5))
4、四色问题：
〖问题描述〗
设有如下图所示的地图，每个区域代表一个省，区域中的数字代表省的编号，将每个省涂上红（R），蓝（B），白（W），黄（Y）四种颜色之一，使相邻的省份有不同的颜色。
1 2 3 4
5 6
输入：用邻接矩阵表示地图。从文件中读入，文件格式如下：
N （有N个省）
N行用空格隔开的0/1串 （1表示相邻，0表示不相邻）
输出：RBWY串
三、回溯法
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 ［例］再以前例说明，找n个数中r个数的组合。
［解］将自然数排列在数组A中：
A[1] A[2] A[3]
5 4 3
5 4 2
„
3 2 １
排数时从A[1] A[2] A[3]，后一个至少比前一个数小１，并且应满足ri+A[ri]>r。若ri+A[ri]≤r就要回溯，该关系就是回溯条件。为直观起见，当输出一组组合数后，若最后一位为１，也应作一次回溯（若不回，便由上述回溯条件处理）。
［程序］
program zuhe3;
type tp=array[1..100] of integer;
var n,r:integer;
procedure comb2(n,r:integer;a:tp);
var i,ri:integer;
begin ri:=1;a[1]:=n;
repeat
if ri<>r then {没有搜索到底}
if ri+a[ri]>r then ｛是否回溯｝
begin a[ri+1]:=a[ri]-1;
ri:=ri+1;
end
else
begin ri:=ri-1; a[ri]:=a[ri]-1;end; {回溯}
else
begin for j:=1 to r do write(a[j]:3);writeln; {输出组合数}
if a[r]=1 then {是否回溯}
begin ri:=ri-1; a[ri]:=a[ri]-1;end; {回溯}
else a[ri]:=a[ri]-1; {递推到下一个数｝
end;
until a[1]<>r-1;
end;
begin {MAIN}
write('n,r=');readln(n,r);
if r>n then
begin writeln('Input n,r error!');halt; end
comb2(n,r);
end.
