深方向移动,则当前的扩展顶点就成为死顶点。此时应往回移动(回 溯)至最近一个活顶点处,并使这个活顶点成为当前扩展顶点。回溯 法即以这种工作方式递归地在解空间中搜索,直至找到要求的解或解 空间中已无活结点时为止。事实上,当我们将问题的有关数据以一定 的方式存储好以后(例如,旅行商问题存储赋权图的邻接矩阵、定和 子集问题是存储已知的n+1个数、4皇后问题用整数对(i,j)表示棋 盘上各个位置),不必先建立一个解空间树,然后再搜索该树寻找所 需要的解。回溯法实际上在搜索的同时逐步生成解空间树(实际只需 要一部分)。也就是说,对于实际问题我们不必要搜索整个解空间。 为了使搜索更加有效,我们常常在搜索过程中加一些判断以决定搜索 是否该终止或改变路线。通常采用两种策略来避免无效的搜索,提高 回溯法的搜索效率。其一是使用约束函数在扩展顶点处剪去不满足约 束的子树;其二是用限界函数(后面将阐述)剪去不能得到最优解的 子树。这两种函数统称为剪枝函数。 运用回溯法解题通常包括以下三个步骤: 1).针对所给问题,定义问题的解空间 2).确定易于搜索的解空间结构; 3).以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函 数避免无效的搜索 §2定和子集问题和0/1背包问题 定和子集问题可以描述成下列的数学问题:确定所有向量 x=(x1,x2,…,xn)满足深方向移动，则当前的扩展顶点就成为死顶点。此时应往回移动（回 溯）至最近一个活顶点处，并使这个活顶点成为当前扩展顶点。回溯 法即以这种工作方式递归地在解空间中搜索，直至找到要求的解或解 空间中已无活结点时为止。事实上，当我们将问题的有关数据以一定 的方式存储好以后（例如，旅行商问题存储赋权图的邻接矩阵、定和 子集问题是存储已知的 n+1 个数、4 皇后问题用整数对(i,j)表示棋 盘上各个位置），不必先建立一个解空间树，然后再搜索该树寻找所 需要的解。回溯法实际上在搜索的同时逐步生成解空间树（实际只需 要一部分）。也就是说，对于实际问题我们不必要搜索整个解空间。 为了使搜索更加有效，我们常常在搜索过程中加一些判断以决定搜索 是否该终止或改变路线。通常采用两种策略来避免无效的搜索，提高 回溯法的搜索效率。其一是使用约束函数在扩展顶点处剪去不满足约 束的子树；其二是用限界函数（后面将阐述）剪去不能得到最优解的 子树。这两种函数统称为剪枝函数。 运用回溯法解题通常包括以下三个步骤： 1).针对所给问题，定义问题的解空间； 2).确定易于搜索的解空间结构； 3).以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函 数避免无效的搜索。 §2.定和子集问题和 0/1 背包问题 定和子集问题可以描述成下列的数学问题：确定所有向量 ( , , , ) 1 2 n x = x x L x 满足：