第五部分克服困难性第十三章回溯法和分支限界法(一)*******@(一)*******@,即思想——方法——应用为主线安排内容。*******@,最笨的办法是穷举搜索,对于有些问题穷举搜索可以有效的解决,但是对于复杂问题穷举搜索法就不能很好地解决了。因此,在穷举搜索的基础上,提出了一些启发式的搜索方法。 回溯法的本质就是搜索,但是其搜索过程采用了一些“剪枝”的策略,可以一定程度上提高搜索的效率。回溯法也称为试探法,该方法在搜索过程中会向前试探搜索,也会在当前搜索路径走不通时,向后回溯。*******@,通常要能表达为:对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)∣xi∈Si,i=1,2,…,n},状态空间E成为问题的解空间;给定关于n元组中的一个分量的一个约束集D,要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域,且|Si|有限,i=1,2,…,n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。注意,同一问题的解空间可能会有多种定义方式,要选择更简单,效率更高的方式。*******@ 问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。 例如n=5,r=3的所有组合为: (1)1、2、3 (2)1、2、4 (3)1、2、5 (4)1、3、4 (5)1、3、5 (6)1、4、5 (7)2、3、4 (8)2、3、5 (9)2、4、5(10)3、4、5 则该问题的状态空间为: E={(x1,x2,x3)∣xi∈S,i=1,2,3} 其中:S={1,2,3,4,5} 约束集为: x1<x2<x3*******@:(1)针对所给问题,定义问题的解空间;(2)确定易于搜索的解空间结构;(3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数:用约束函数在扩展结点处剪去不满足约束的子树;用目标函数剪去得不到最优解的子树。(优化问题)*******@●对于许多问题,所给定的约束集D具有完备性,即i元组(x1,x2,…,xi)满足D中仅涉及到x1,x2,…,xi的所有约束意味着j(j<i)元组(x1,x2,…,xj)一定也满足D中仅涉及到x1,x2,…,xj的所有约束,i=1,2,…,n。●换句话说,只要存在0≤j≤n-1,使得(x1,x2,…,xj)违反D中仅涉及到x1,x2,…,xj的约束之一,则以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)一定也违反D中仅涉及到x1,x2,…,xi的一个约束,n≥i>j。*******@sjzue.●因此,对于约束集D具有完备性的问题P,一旦检测断定某个j元组(x1,x2,…,xj)违反D中仅涉及x1,x2,…,xj的一个约束,就可以肯定,以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)都不会是问题P的解,因而就不必去搜索它们、检测它们。●回溯法正是针对这类问题,利用这类问题的上述性质而提出来的比枚举法效率更高的算法。*******@●回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T,把在E中求问题P的所有解转化为在T中深度优先搜索问题P的所有解。树T类似于检索树,被称为状态空间树。●树T上任意一个结点被称为问题P的状态结点;●树T上的任意一个叶子结点被称为问题P的一个解状态结点;●树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点,它对应于问题P的一个解。*******@sjzue.
回溯法幻灯片 来自淘豆网m.daumloan.com转载请标明出处.
