回溯算法入门及应用 广东省东莞市东华高级中学 杨光文 难易指数:在求解一些问题（如马的遍历、选书、八皇后问题、自然数的拆分等问题）时，题目的要求可能是求出原问题的一种或所有可能的解决方案。这类问题的解往往是由一个一个的步骤或状态所构成的，每一步骤又有若干种可能的决策方案；由于没有固定、明确的数学解析方法，往往要采用搜索的做法，即从某一个初始状态出发，不断地向前（即下一个状态）搜索，以期最终达到目标状态，从而得到原问题的一个解或所有的解。在搜索的过程中，由于问题本身及所采取的搜索方法的特点（如在缺乏全局及足够的前瞻信息的情况下进行搜索等），会导致走到某一状态就走不下去的情况，这时，就必须回头（即回到上一步，而不是回到最初的状态），再尝试其他的可能性，换一个方向或方法再试试。这样，不断地向前探索、回溯，再向前、再回溯，直至最终得出问题的解，或者一路回溯到出发点（出现这种情况即表示原问题无解）。注意，这种搜索过程并不是尝试搜索问题解空间中所有的可能状态和路径，而是采用深度优先的方式，沿着一条路径，尽可能深入地向前探索，这就是回溯算法。一、回溯算法的定义：回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为： 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）； (i3,j8)2: （i,j）（i+1,j+2）； (i4,j0,j1,j); writeln(4,8,t:5); end;procedure try(i:integer); 搜索 var j:integer; begin a1,1:=0;a1,2:=0; for j:=1 to 4 do if (ai-1,1+xj,1=0) and (ai-1,1+xj,1=0) and (ai-1,2+xj,20) then begin flag:=flag+j;booki:=j; if i=5 then print else try(i+1); flag:=flag-j;booki:=0; end; end;begin flag:=; c:=0; try(1); readlnend.例3：八皇后问题【问题描述】在一个的棋盘里放置个皇后，要求每个皇后两两之间不相冲（在每一横列竖列斜列只有一个皇后）。【问题分析】这道题可以用回溯算法来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：1、冲突。包括行、列、两条对角线：（1）列：规定每一列放一个皇后，不会造成列上的冲突；（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2、数据结构。（1）解数组A。AI表示第I个皇后放置的列；范围：1.8（2）行冲突标记数组B。BI=0表示第I行空闲；BI=1表示第I行被占领；范围：1.8（3）对角线冲突标记数组C、D。CI-J=0表示第（I-J）条对角线空闲；CI-J=1表示第（I-J）条对角线被占领；范围：-7.7DI+J=0表示第（I+J）条对角线空闲；DI+J=1表示第（I+J）条对角线被占领；范围：2.16【算法流程】、数据初始化。、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于（未被占领），如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当n8时，便一一打印出结果。【参考程序】program exam3;var a:array 1.