算法分析与 及设计[回溯法].pptVIP

第六章 回溯法;什么是回溯法;可用回溯法求解的问题;问题求解的方法;回溯法概述;约束条件;回溯法求解的经典问题（1）8-皇后问题;;回溯法求解的经典问题（2）子集和数问题;子集和数问题解的另一种表达;解空间的树结构;组织解空间（1）;组织解空间（2）;组织解空间（3）;状态空间树;生成问题状态的两种方法;4-皇后问题-回溯解;4-皇后问题回溯期间生成的树;回溯法的算法;　回溯算法的形式描述;回溯的一般方法－算法;回溯算法的递归表示;效率分析应考虑的因素;效率分析;Monte Carlo效率估计（1）;Monte Carlo效率估计（2）;Monte Carlo效率估计算法;6.2 8-皇后问题;6.2 8-皇后问题;6.2 8-皇后问题;算法6.4：可以放置一个新皇后吗？;算法6.5：n-皇后问题的所有解;6.3 子集和数问题;6.3 子集和数问题;算法6.6：子集和数问题的递归算法;算法6.6：子集和数问题的递归算法;例6.6;6.4 图的着色;6.4 图的着色; 一幅地图和它的平面表示;6.4 图的着色;6.4 图的着色;6.4 图的着色;算法6.7 找一个图的所有m-着色方案 Procedure MCOLORING(k) //这是图着色的一个递归回溯算法。图G用它的布尔邻接矩阵GRAPH(1:n,1:n)表示。// //它计算并打印出符合以下要求的全部解，把整数1,2,…,m分配给图中// //各个结点且使相邻近的结点的有不同的整数。K是下一个要着色结点的下标 Global integer m,n,X(1:n) boolean GRAPH(1:n,1:n) Integer k Loop //产生对X(k)所有的合法赋值。// call NEXTVALUE(k) //将一种合法的颜色分配给X(k)// if X(k)=0 then exit endif //没有可用的颜色了// if k=n then print(X) //至多用了m种颜色分配给n个结点// else call MCOLORING(k+1) //所有m-着色方案均在此反复递归调用中产生// endif repeat End MCOLORING;算法6.8 生成下一种颜色 Procedure NEXTVALURE(k) // 进入此过程前X(1),X(2),…,X(k-1)已分得了区域[1,m]中的整数且相邻近的结点有不同的整数。本过程在区域[0,m]中给X(k)确定一个值：如果还剩下一些颜色，它们与结点k邻接的结点分配的颜色不同，那么就将其中最高标值的颜色分配给结点k ;如果没剩下可用的颜色，则置X(k)为0 // global integer m,n,X(1:n) boolean GRAPH(1:n,1:n) integer j,k loop X(k)=(X(k)+1) mod (m+1) //试验下一个最高标值的颜色// if X(k)=0 then return endif //全部颜色用完// for j=1 to n do //检查此颜色是否与邻近结点的那些颜色不同// if GRAPH(k, j) and X(k)=X(j) // 如果(k,j) 是一条边, 并且邻近的结点有相同的颜色// then exit endif repeat if j=n+1 then return endif //找到一种新颜色// repeat //否则试着找另一种颜色// end NEXTVALURE;X1 X2 X3 X4;6.5 哈密顿环;算法: 生成下一个结点;算法: 找所有的哈密顿环;6.6 0/1背包问题;算法: 限界函数;算法: 0/1背包问题的回溯法求解;例6.7;0;算法说明;算法说明;算法 有边界效应的限界函数;算法 改进的背包算法;用动态状态空间树解0/1背包问题;用动态状态空间树解0/1背包问题;用动态状态空间树解0/1背包问题;用动态状态空间树解0/1背包问题;实例;用动态状态空间树解0/1背包问题