02年05月09日回溯策略与递归

1、第七章简单的回溯与递归回溯需要用计算机解决的问题一般有两种类型：(1) 可以用精确的数学公式或明确的算法语言来描述的问题。(2) 在完成一件事情的过程中，要经过若干个步骤，而每一个步骤都有若干种可能的分支，为了圆满地完成任务，须遵守一些规则，而这些规则又无法精确地用数学公式来描述。对于第二类问题，一般采用搜索的方法来解决。回溯是搜索算法中的一种控制策略。它的基本过程中，由于求解失败。为摆脱当前是：在搜索状态，返回搜索步骤中的上一个结点，并重新寻求解答。以闯迷宫为例，进入迷宫后，先随意选择一个前进方向，一步步向前试探前进，如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走

2、，如果有路可走，则沿该方向再向前试探；如果无路可走，则回撤一步，再看其他方向是否还有路可走。如果有路可走，则沿该方向再向前试探；如果无路可走，则回撤一步，再看其他方向是否有路可走。按此原则不断搜索，直到找到新的出路或从原路返回处。探索迷宫时，为都要设置一些标记，了不迷失方向，例如，在走过的进与回撤的铺一条线，遇到死胡同返回时再铺上一条线。这样，就可以判断哪条路是已经过过的，哪条路是没走过的，哪条路是死胡同。根据这些信息，就能正确的找到迷宫的出口，在搜索过程中也能正确地找到应返回的位置，并避免重新进入死胡同。见图 71。回溯是计算机的重要算法之一。许多涉及搜索问题的求解过程都要用到回溯探索的控制

3、策略。如：八皇后问题，马的环游问题以及稳定的实例来介绍回溯的例 1八皇后问题。问题等。下面，通过一些具体与在计算机上实现的基本方法。问题的由来：国际象棋是人发明的一种二人对弈棋，它的棋盘是由 8×8 个黑白相间的方格组成。双方各有一个国王、一个皇后、两个车、两个马、两今象、八个兵，共个棋子。皇后是所有棋子中最大的一个子，根据国际象棋的规则，她横走、竖走、斜走均可，且格数不限。因此，若在某二方格内放置了一个皇后，那么，她所在的行、列以及斜线上的子都可以被她。八皇后问题是一个有趣的独弈问题，是由德国大数学家高斯(Gauss，17771855 年)于 1850 年首先。要求在国际象棋的棋盘

4、上放置八个皇后，使其不能互相攻击，即任意两个皇后不能处在同一行、同一列、同一条斜线上。问有多少种摆法?请找出所有的摆法。当时，高斯本人并未能完全解决这一问题，他只找到了一部分解答。由于这个问题的求解需要大量的试验和计算，因此，用手工求解是难以胜任的。图 72 即为满足上述条件的一组布局。请你设计一个程序，由计算机自动寻找并按如下格式打印所有满足条件的摆法。算法一：问题分析:(1)满足上述条件的八个皇后，必然是每行一个、每列一个(2)棋盘上任意一行、任意一列、任意一条斜线上都不能有两个皇后。如果把 8×8 的棋盘看作一个平面直角坐标系，则八皇后问题就可以用数学语言来描述：任意两个皇后在

5、QQQQQQQQ平面上的坐标应同时满足以下三个条件： 横坐标不相等； 纵坐标不相等； 两横坐标之差的绝对值不等于两纵坐标之差的绝对值。为了在计算机上解决八皇后问题，可以用一个一维数组 A(1)来描述八个皇后在棋盘上的状态。其中，数组的下标表示皇后所在的行，数组元素的值表示皇后所在的列。即 A(1)J 表示在第 I 行、第 J 列放置了一个皇后。经过这样的定义后，八皇后问题的三个条件可分别表示如下：(1) 横坐标不相等：IK(K 表示与I 不同的另一个下标)；(2) 纵坐标不相等：当 IK 时，A(I)A(K)；(3) 两横坐标之差的绝对值不等于两纵坐标之差的绝对值：当 IK 时，|I-K|A(

6、I)-A(K)|。算法设计：首先考虑用回溯法来解决八皇后问题。(1)在棋盘的第一行、第一列放置一个皇后。(2)从第二行第一列开始，每放置一个皇后就判断一下是否满足条件。如果满足条件，则从下一行的第一列开始继续放置皇后；如果不满足条件，则将刚刚放置好的皇后向右移动一列后再判断是否满足条件。(3)若第 1 个皇后摆到第八列后仍不能满足条件，说明可能是上一行的皇后的位置不合适，则退回到上一行，将上一行的皇后向右移动一列后再作判断。(4)当已摆够 8 个皇后时，即可将这一布局打印出来。流程图见图 73。为下一个皇后找合适的位置：返回判断是否与前面皇后：返回FtrueKI-1 downto 1Ai=ak

7、 or abs(ai-ak)=abs(I-k)ynFfalseFlagFAinext ; Flagfalse ;只要flag<>trueyAi>8nII-1 ; ai ai+1;判断是否与前面y？nAiai+1yAi>8nII-1 ; aiai+1Ai0 ; a11 ; I2 ; next1 ; total0为下一个皇后找合适的位置；yI=8ntotaltotal+1;II+1 ;Next1打印一组解；yAi<>8nAiai+1II-1;Aiai+1;NextaiI=1输出total的值算法二：国际象棋的棋盘上共有 30 条斜线，15 条?方向，15 条?方

8、向(见图 74)。用一维数组 A(1)-A(30)来表示这 30 条斜线。其中，处在?方向上的 15 条斜线用 A(1)-A(15)表示，处在?方向上的 15 条斜线用 A(16)-A(30)表示。若某一列或某一条斜线上放置了一个皇后，则在相应的数组单元中置 l，否则置 0。再用一个一维数组 C皇后的位置。由对角线的性质可知：若A，B 两个皇后处在?方向上的同一条斜线上时，则应有 A 皇后的坐标之和等于 B 皇后的坐标之和。即 Il 十 JlI2 十 J2, 若 A，B 两个皇后处在?方向上的同一条斜线上时，则应有 A 皇后的坐标之差的绝对值等于 B 皇后的坐标之差的绝对值。即|Il-Jl|I2-J2|在第 J 列摆放皇后应满足的条件为：第J 列及两个方向的斜线