回溯法一.搜索方法和状态空间树5.各种搜索方法枚举法（穷举法）：搜索整棵状态空间树的每个结点的蛮力方法。容易实现，但效率低，时间复杂性一般为指数阶或更高阶。例.n皇后问题：枚举算法的时间复杂性为Θ(nn)或Θ(n!)。回溯法分枝限界法回溯法二.回溯法的基本思想和基本步骤1.回溯法的基本思想：DFS+剪枝（在状态空间树上作带剪枝的DFS搜索）剪枝：若搜索到某结点，其对应的部分解不满足解的约束条件且可断定以其为根的子树上不包含答案结点，则不搜索该子树，直接回到其父结点，继续DFS。例.四皇后问题的回溯搜索过程：（图13.4P222）四皇后问题.ppt利用回溯法可求问题的一个解，多个解，所有解，最优解，还可判断解的存在性。回溯法二.回溯法的基本思想和基本步骤1.回溯法的基本思想：回溯法通常包含以下3个步骤：定义给定问题的解空间；确定并表示解的约束条件和其它的剪枝条件；结合剪枝深度优先搜索相应的状态空间树。注意：回溯法的一个特征是在搜索过程中动态的产生问题的状态空间树，任何时候只存根到当前搜索的结点的路径。。回溯法二.回溯法的基本思想和基本步骤2.用回溯法解n皇后问题(13.3P221)解空间：其中，xi表示第i行皇后所放置的位置。解的约束条件：对于第i行与第j行皇后(i≠j):不同行：根据解空间的定义自然满足。不同列：xi≠xj不同斜线：i-xi≠j-xj(\)且i+xi≠j+xj(/)等价于|i-j|≠|xi-xj|n皇后问题的回溯算法：回溯法二.回溯法的基本思想和基本步骤3.回溯的形式算法（13.4P223）设问题的解空间为形式迭代算法形式递归算法回溯法二.回溯法的基本思想和基本步骤4.回溯算法的时间复杂性回溯算法的时间复杂性主要取决于以下因素：解空间的大小；产生解空间元素的一个分量的时间；解的约束条件的判断时间；剪枝的范围大小。在状态空间树确定的情况下，1)～3)与具体的实例无关，4)则与具体的实例相关。回溯法三.回溯算法设计示例1.图的着色问题问题背景：四色定理：任何平面图都是可以4着色的。图例：问题描述(图的m着色问题)：给定一个无向连通图G和m种颜色，给图G的所有顶点着色，使得任何两相邻顶点的颜色不同。(G可以是平面图，也可以是非平面图。)回溯法三.回溯算法设计示例1.图的着色问题解空间和状态空间树：设图G有n个顶点，编号为1,2,…,n,m种颜色编号为1,2,…,m。解空间：其中，xi表示顶点i所着的颜色编号。状态空间树：（图13.1P218）解的约束条件：（设图G用邻接矩阵graph表示graph[k,j]*xk≠xj,1=k,j=n，k≠j回溯算法：(非递归算法，求一个解)回溯法三.回溯算法设计示例2.哈密顿回路问题问题描述：设G是一个n个顶点的连通图，求G的所有哈密顿回路。哈密顿回路：图G的哈密顿回路是一条经过G的所有顶点恰好一次的回路。图例：回溯法三.回溯算法设计示例2.哈密顿回路问题解空间:A={(x1,x2,…,xn)|x1=1,2=xi=n,i=2,…,n}其中，x1,x2,…,xn表示G中的顶点序列。解的约束条件：（设图G用邻接矩阵graph表示）(x1,x2,…,xn)为哈密顿回路当且仅当graph[xk-1,xk]=1,k=2,3,…,n且grapg[xn,x1]=1且xi≠xj(i≠j)回溯算法：回溯算法回溯法三.回溯算法设计示例3.迷宫问题问题描述：给出一个迷宫和入口、出口位置，找出从入口至出口的一条通路。设迷宫用一个二维数组M[1..m,1..n]表示:M[x,y]=0,位置(x,y)可走M[x,y]=1,位置(x,y)不可走入口位置为(ix,iy),出口位置为(ox,oy)，在每个位置只能向东南西北四个方向搜索。回溯法三.回溯算法设计示例3.迷宫问题解空间:其中，ki表示搜索方向,方向编号为：1—东，2—南，3—西，4—北。约束条件