lec_6 回溯法(修改)

1、回溯法回溯法 对于大部分问题来说，其解空间的规模为输入规模的指数函数甚至更高。 显然，在如此巨大的解空间实施穷举将是费时费力、低效率的。 因此，寻找更加有效的搜索手段就是算法不断推进的源动力。 我们要介绍的回溯法属于一种智能穷举搜索。 智能穷举的核心思想，顾名思义，有两个：穷举（在最坏情况下要对整个解空间进行指数级搜索）+智能（利用各种途径减少搜索量）。解空间树的动态搜索（解空间树的动态搜索（1） 回溯法从根结点出发，按照回溯法从根结点出发，按照深度优先策略遍历深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点对应的

2、任一结点时，先判断该结点对应的部分解部分解是否满足是否满足约束条件约束条件，或者是否超出，或者是否超出评估函数评估函数的界，也就是判的界，也就是判断该结点是否断该结点是否包含包含问题的（最优）解，如果肯定不问题的（最优）解，如果肯定不包含，包含，则跳过对以该结点为根的子树的搜索则跳过对以该结点为根的子树的搜索，即所，即所谓谓剪枝剪枝（PruningPruning）；否则，进入以该结点为根的）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。子树，继续按照深度优先策略搜索。例如，对于n=3的0/1背包问题，三个物品的重量为20, 15, 10，价值为20, 30, 25，背包容量为25，

3、从图8.2所示的解空间树的根结点开始搜索，搜索过程如下： 1不可行解不可行解价值价值=20价值价值=55 价值价值=30 价值价值=25价值价值=01111000000112811121415131069不可行解不可行解 再如，对于n=4的TSP问题，其代价矩阵如图8.5所示， C= 3 6 712 2 8 8 6 2 3 7 6 图图8.5 TSP问题的代价矩阵问题的代价矩阵2344221231341313123212142414322434123124134图图8.6 TSP问题的搜索空间问题的搜索空间5475441127464851 535838132429354045505560218

4、342412341C= 3 6 712 2 8 8 6 2 3 7 6 TSP问题的代价矩阵问题的代价矩阵 回溯法的搜索过程涉及的结点（称为搜索空间）回溯法的搜索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通常只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：采用两种策略避免无效搜索：（1）用）用约束条件约束条件剪去得不到剪去得不到可行解可行解的子树；的子树；（2）用）用评估函数评估函数剪去得不到剪去得不到最优解最优解的子树。的子树。这两类函数统称为这两类函数统称为剪枝函数剪枝函数（Pruning Function）。）。v 需要注意的是，问题的解

5、空间树是虚拟的，并不需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要需要在算法运行时构造一棵真正的树结构，只需要存储从根结点到当前结点的路径。存储从根结点到当前结点的路径。组合问题中的回溯法组合问题中的回溯法 八皇后问题八皇后问题 八皇后问题八皇后问题 八皇后问题是十九世纪著名的数学家高斯于八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在年提出的。问题是：在88的棋盘上摆放八的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把不能处于同一行、同一列或同

6、一斜线上。可以把八皇后问题扩展到八皇后问题扩展到n皇后问题，即在皇后问题，即在nn的棋盘的棋盘上摆放上摆放n个皇后，使任意两个皇后都不能处于同个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。一行、同一列或同一斜线上。 若两个皇后摆放的位置分别是若两个皇后摆放的位置分别是(i, xi)和和(j, xj)，在棋盘，在棋盘上上斜率为斜率为-1的斜线上，满足条件的斜线上，满足条件ij= xixj，在棋盘上斜，在棋盘上斜率为率为1的斜线上，满足条件的斜线上，满足条件ij= xixj，综合两种情况，综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量由于两个皇后不能位于同一斜线上，所以，

7、解向量X必须必须满足约束条件：满足约束条件： | |ixi| | |jxj| | （式（式8.2） 显然，棋盘的每一行上可以而且必须摆放一个皇后，显然，棋盘的每一行上可以而且必须摆放一个皇后，所以，所以，n皇后问题的皇后问题的可能解用一个可能解用一个n元向量元向量X=(x1, x2, , xn)表示，其中，表示，其中，1in并且并且1xin，即第，即第i个皇后放在个皇后放在第第i行第行第xi列列上。上。 由于由于两个皇后不能位于同一列上两个皇后不能位于同一列上，所以，解向量，所以，解向量X必必须满足约束条件：须满足约束条件： xixj （式（式8.1）1 2 3 41234皇后1皇后2皇后3皇

8、后4图8.11 四皇后问题 为了简化问题，下面讨论四皇后问题。为了简化问题，下面讨论四皇后问题。 四皇后问题的解空间树是一个完全四皇后问题的解空间树是一个完全4叉树，树的根结叉树，树的根结点表示搜索的初始状态，从根结点到第点表示搜索的初始状态，从根结点到第2层结点对应皇后层结点对应皇后1在棋盘中第在棋盘中第1行的可能摆放位置，从第行的可能摆放位置，从第2层结点到第层结点到第3层结层结点对应皇后点对应皇后2在棋盘中第在棋盘中第2行的可能摆放位置，依此类推。行的可能摆放位置，依此类推。QQ QQ Q QQQQ Q QQ QQQQQQQ Q(a) (b) (c) (d) (e)(f) (g) (h)

9、 (i) (j)QQ Q回溯法求解回溯法求解4皇后问题的搜索过程皇后问题的搜索过程算法算法n皇后问题皇后问题 void Queue(int n) for (i=1; i=1) xk=xk+1; /在下一列放置第在下一列放置第k个皇后个皇后 while (xk=n & !Place(k) xk=xk+1; /搜索下一列搜索下一列 if (xk=n & k= =n) /得到一个解，输出得到一个解，输出 for (i=1; i=n; i+) coutxi; return; else if (xk=n & kn) k=k+1; /放置下一个皇后放置下一个皇后 else xk=0; /重置重置xk，回溯，回溯 k=k-1; bool Place(int k) /考察皇后考察皇后k放置在放置在xk列是否发生冲突列是否发生冲突 for (i=1; ik; i+) if (xk= =xi | | abs(k-i)= =abs(xk-xi) return false; return true; 思考题思考题1.亚瑟王打算请