回溯算法入门及应用.doc

广东省东莞市东华高级中学杨光文难易指数:★★★
在求解一些问题(如马的遍历、选书、八皇后问题、自然数的拆分等问题)时,题目的要求可能是求出原问题的一种或所有可能的解决方案。这类问题的解往往是由一个一个的步骤或状态所构成的,每一步骤又有若干种可能的决策方案;由于没有固定、明确的数学解析方法,往往要采用搜索的做法,即从某一个初始状态出发,不断地向前(即下一个状态)搜索,以期最终达到目标状态,从而得到原问题的一个解或所有的解。在搜索的过程中,由于问题本身及所采取的搜索方法的特点(如在缺乏全局及足够的前瞻信息的情况下进行搜索等),会导致走到某一状态就走不下去的情况,这时,就必须回头(即回到上一步,而不是回到最初的状态),再尝试其他的可能性,换一个方向或方法再试试。这样,不断地向前探索、回溯,再向前、再回溯,直至最终得出问题的解,或者一路回溯到出发点(出现这种情况即表示原问题无解)。注意,这种搜索过程并不是尝试搜索问题解空间中所有的可能状态和路径,而是采用深度优先的方式,沿着一条路径,尽可能深入地向前探索,这就是回溯算法。
一、回溯算法的定义:
回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。用回溯算法解决问题的一般步骤为:
1、定义一个解空间,它包含问题的解。
2、利用适于搜索的方法组织解空间。
3、利用深度优先法搜索解空间。
4、利用限界函数避免移动到不可能产生解的子空间。
问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。
下面通过一个具体实例加深大家对回溯算法的认识。
二、回溯算法的应用举例:
例1:马的遍历
中国象棋半张棋盘如图1(a)所示。马自左下角往向右上角跳。规定只许往右跳,不许往左跳,马只能走日字。比如图1(a)所示为一种跳行路线,并将所经路线打印出来,打印格式为:0,0->2,1->3,3->1,4->3,5->2,7->4,8。找出所有路径。
【算法分析】
如图1(b),马最多有四个方向,若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为:
1: (i,j)→(i+2,j+1); (i<3,j<8)
2: (i,j)→(i+1,j+2); (i<4,j<7)
3: (i,j)→(i-1,j+2); (i>0,j<7)
4: (i,j)→(i-2,j+1); (i>1,j<8)
搜索策略:
S1:A[1]:=(0,0);
S2:从A[1]出发,按移动规则依次选定某个方向,如果达到的是(4,8)则转向S3,否则继续搜索下
一个到达的顶点;
S3:打印路径。
【算法设计】
procedure try(i:integer); {搜索}
var j:integer;
begin
for j:=1 to 4 do {试遍4个方向}
if 新坐标满足条件 then
begin
记录新坐标;
if 到达目的地 then print {统计方案,输出结果}
else try(i+1); {试探下一步}
退回到上一个坐标,即回溯;
end;
end;
【参考程序】
program exam1;
const x:array[1..4,1..2] of integ