资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,回溯法,对于大部分问题来说，其解空间的规模为输入规模的,指数函数,甚至更高。,显然，在如此巨大的解空间,实施穷举,将是费时费力、,低效率,的。,因此，寻找更加有效的搜索手段就是算法不断推进的源动力。,我们要介绍的回溯法属于一种,智能穷举搜索。,智能穷举的核心思想，顾名思义，有两个：,穷举,（在最坏情况下要对整个解空间进行指数级搜索）,+,智能,（利用各种途径减少搜索量）。,解空间树的动态搜索（,1,）,回溯法从根结点出发，按照,深度优先策略遍历,解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点对应的,部分解,是否满足,约束条件,，或者是否超出,评估函数,的界，也就是判断该结点是否,包含,问题的（最优）解，如果肯定不包含，,则跳过对以该结点为根的子树的搜索,，即所谓,剪枝,（,Pruning,）；,否则，进入以该结点为根的子树，继续按照深度优先策略搜索。,例如，对于,n,=3,的,0/1,背包问题，三个物品的重量为,20, 15, 10,，价值为,20, 30, 25,，背包容量为,25,，从图,8.2,所示的解空间树的根结点开始搜索，搜索过程如下：,1,不可行解,价值,=20,价值,=55,价值,=30,价值,=25,价值,=0,1,1,1,1,0,0,0,0,0,0,1,1,2,8,11,12,14,15,13,10,6,9,不可行解,再如，对于,n,=4,的,TSP,问题，其代价矩阵如图,8.5,所示，,C,=,3 6 7,12 2 8,8 6 2,3 7 6 ,图,8.5 TSP,问题的代价矩阵,2,3,4,4,2,2,1,2,3,1,3,4,1,3,1,3,1,2,3,2,1,2,1,4,2,4,1,4,3,2,2,4,3,4,1,2,3,1,2,4,1,3,4,图,8.6 TSP,问题的搜索空间,5,47,54,4,11,27,46,48,51,53,58,3,8,13,24,29,35,40,45,50,55,60,2,18,34,24,1,2,3,4,1,C,=,3 6 7,12 2 8,8 6 2,3 7 6 ,TSP,问题的代价矩阵,回溯法的搜索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：,（,1,）用,约束条件,剪去得不到,可行解,的子树；,（,2,）用,评估函数,剪去得不到,最优解,的子树。,这两类函数统称为,剪枝函数,（,Pruning Function,）。,需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要存储从根结点到当前结点的路径。,组合问题中的回溯法,八皇后问题,八皇后问题,八皇后问题是十九世纪著名的数学家高斯于,1850,年提出的。问题是：在,88,的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到,n,皇后问题，即在,n,n,的棋盘上摆放,n,个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。,若两个皇后摆放的位置分别是,(,i,x,i,),和,(,j,x,j,),，,在棋盘上,斜率为,-1,的斜线上，满足条件,i,j,=,x,i,x,j,，,在棋盘上斜率为,1,的斜线上，满足条件,i,j,=,x,i,x,j,，,综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量,X,必须满足约束条件：,|,i,x,i,|,|,j,x,j,|,（式,8.2,）,显然，棋盘的每一行上可以而且必须摆放一个皇后，所以，,n,皇后问题的,可能解用一个,n,元向量,X,=(,x,1,x,2, ,x,n,),表示，其中，,1,i,n,并且,1,x,i,n,，,即第,i,个皇后放在,第,i,行第,x,i,列,上。,由于,两个皇后不能位于同一列上,，所以，解向量,X,必须满足约束条件：,x,i,x,j,（式,8.1,）,1 2 3 4,1,2,3,4,皇后,1,皇后,2,皇后,3,皇后,4,图,8.11,四皇后问题,为了简化问题，下面讨论四皇后问题。,四皇后问题的解空间树是一个完全,4,叉树，树的根结点表示搜索的初始状态，从根结点到第,2,层结点对应皇后,1,在棋盘中第,1,行的可能摆放位置，从第,2,层结点到第,3,层结点对应皇后,2,在棋盘中第,2,行的可能摆放位置，依此类推。,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,(a) (b) (c) (d) (e),(f) (g) (h) (i) (j),Q,Q,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+),cout,xi;,return;,C+描述,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.,亚瑟王打算请,150,名骑士参加宴会，但是有些骑士相互间会有口角，而亚瑟王知道谁与谁不和。亚瑟王希望能让他的客人围着一张圆桌坐下，而所有不和的骑士都不会挨着坐。请回答下列问题,:,（,1,）哪一个经典问题能够作为亚瑟王问题的模型？,（,2,）请说明，如果与每个骑士不和的人数不超过,75,，则问题有解；,（,3,）设计回溯算法求解亚瑟王问题。,
展开阅读全文