回溯

Example:8-皇后问题

图16.1

  • 8皇后问题的解可以表示为一个8-元组(x1,x2,…,x8),其中xi是放在第i行的皇后所在的列号,则8皇后问题可形式化为pow(8,8)个8-元组中找满足以下约束条件的元组:

    对于任意的i≠j,有xi≠xj;|xi-xj|≠|i-j|;

  • 这pow(8,8)个8-元组构成的集合成为8皇后问题的解空间-搜索范围;

  • 如果将约束条件之一,任意两个皇后不在同一列,加入到元组的定义中,这是每个8-元组为(1,2,3,4,5,6,7,8)的一个排列,解空间的大小由pow(8,8)个元组减少到8!个元组;

  • 解空间不是唯一的,取决于算法的设计;

  • 设计解空间时还要考虑生成解空间的算法复杂度;在8皇后问题中,如果加入第二个条件,解空间很难形成。

搜索问题的形式化-解空间

  • 假定问题的解能用n-元组(x1,x2,…,xn)表示,其中xi取自某个有穷集Si;

  • 这些n-元组构成的集合成为问题的解空间;假设|Si|=mi,则解空间的大小为m=m1m2…*mn;

  • 我们考虑两类问题:

    存在性问题:求满足某些条件的一个或全部元组,如果存在返回Yes,否则返回No。这些条件称为约束条件;

    优化问题:给定一组约束条件,在满足约束条件的元组中求使某目标函数达到最大(小)值的元组。满足约束条件的元组成为问题的可行解。

  • 解决这类问题的最一般方法使使用搜索技术,即系统化地搜索解空间地技术。

Example:子集和数问题

  • 已知n+1个整数:wi,1<=i<=n,和M。要求找出{wi|1<=i<=n}的所有子集,使得子集内元素之和等于M;

  • 例如:n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31。则满足要求的子集是(11,13,7)和(24,7);

  • 我们可以用wi的下标i构成的元组表示一个解,则这两个解可表示为(1,2,4)和(3,4);

  • 元组(1,2,4)和(2,1,4)代表同一子集,此为限制元组分量按升序排列,即不考虑元组(2,1,4);

  • 还可用其他方式表示一个解,如下:

解空间的状态空间树

  • 任何搜索算法都可以用建立在解空间上的状态空间树加以描述;
  • 状态空间树是我们尝试选择元组的各个分量时产生的树结构;
  • 搜索算法并非事先将状态空间树存在计算机内再进行遍历,而是通过展开状态空间树来找所求的解;
  • 展开过程中通过使用启发式的限界方法(剪去状态空间树上的某些分支)使搜算算法只展开状态空间树的一部分,从而降低搜索算法的时间和空间复杂度。

Example:n-皇后问题

  • n-皇后问题是8-皇后问题的推广。n个皇后将被放置在n×n的棋盘上且使得没有两个皇后可以互相攻击,其解空间由n-元组(1,2,…,n)的n!个排列组成;
  • 其状态空间树如下图所示(n=4)。树的边由xi的可能的取值标记。由i级到i+1级节点的边给出xi的值,这种树成为排列树;
  • 从根节点到叶节点的一条路径对应解空间的一个元组。

4-皇后问题的状态空间树

子集和数问题的状态空间树

子集和数问题的状态空间树

有关状态空间树的术语

  • 状态空间树的每个节点代表问题求解过程中达到的一个状态,根节点到它的路径代表对一些分量已作出的选择。状态空间树的所有节点构成的集合成为求解该问题的状态空间;
  • 根节点到状态空间树的一个节点X的路径可以表示为(x1,x2,…,xk),其中xi,1<=i<=k,为搜索过程中已经选择的分量。今后我们也用这个元组标识该节点:X=(x1,x2,…,xk);
  • (x1,x2,…,xk)也对应一个子问题,即在后n-k个元组分量所对应的子空间上找满足要求的解。该子空间是状态空间树中以X为根的子树。所以也称节点X为问题节点;
  • 如果从根节点到节点S的那条路径确定了解空间的一个元组,则称S为状态空间树的一个解节点;
  • 如果一个解节点S(代表的元组)满足所有约束条件,则称其为答案节点。

状态空间树的展开方法

  • 每个搜索算法都是一种系统地展开状态空间树地算法;
  • 活节点:已展开了部分节点,但所有子节点尚未全部展开的节点;
  • 死节点:被限界或已展开了所有子节点地节点;
  • E-节点:当前正在展开子节点的活节点。
  • 深度优先展开方法:一个E-节点展开自己的一个子节点后,就让该子节点成为E-节点的展开方法(相当于对状态空间树做深度优先搜索)。
  • 回溯法:加限界的深度优先展开状态空间树的方法;
  • 分枝-限界法:一个节点一旦成为E-节点,它将展开其全部子节点,之后自己变成死节点;
  • 在分枝-限界法中要维持一个活节点表的结构,存放已展开但还未成为E-节点的那些节点。

限界

限界

用回溯法解4-皇后问题

用回溯法解4-皇后问题

回溯的一般方法

  • 每个解用数组X(1,n)来表示;
  • 假定X1,X2,…,X(k-1)的值已确定,T(X1,X2,…,X(k-1))代表xk的所有可能的取值;
  • 限界函数B(X1,X2,…,XK)判断那些Xk的取值不能导致问题的解,从而停止展开该子节点。