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

第六章回溯法什么是回溯法可用回溯法求解的问题问题求解的方法回溯法概述回溯法思想回溯法如何提高效率？约束条件回溯法求解的经典问题（1）8-皇后问题回溯法求解的经典问题（2）子集和数问题子集和数问题解的另一种表达解空间的树结构组织解空间（1）组织解空间（2）组织解空间（3）状态空间树生成问题状态的两种方法4-皇后问题-回溯解4-皇后问题回溯期间生成的树回溯法的算法回溯算法的形式描述回溯的一般方法－算法回溯算法的递归表示效率分析应考虑的因素效率分析MonteCarlo效率估计（1）MonteCarlo效率估计（2）MonteCarlo效率估计算法6.28-皇后问题6.28-皇后问题6.28-皇后问题算法6.4：可以放置一个新皇后吗？算法6.5：n-皇后问题的所有解6.3子集和数问题6.3子集和数问题算法6.6：子集和数问题的递归算法算法6.6：子集和数问题的递归算法例6.66.4图的着色6.4图的着色一幅地图和它的平面表示6.4图的着色6.4图的着色6.4图的着色算法6.7找一个图的所有m-着色方案
ProcedureMCOLORING(k)
//这是图着色的一个递归回溯算法。图G用它的布尔邻接矩阵GRAPH(1:n,1:n)表示。//
//它计算并打印出符合以下要求的全部解，把整数1,2,…,m分配给图中//
//各个结点且使相邻近的结点的有不同的整数。K是下一个要着色结点的下标
Globalintegerm,n,X(1:n)booleanGRAPH(1:n,1:n)
Integerk
Loop//产生对X(k)所有的合法赋值。//
callNEXTVALUE(k)//将一种合法的颜色分配给X(k)//
ifX(k)=0thenexitendif//没有可用的颜色了//
ifk=nthenprint(X)//至多用了m种颜色分配给n个结点//
elsecallMCOLORING(k+1)//所有m-着色方案均在此反复递归调用中产生//
endif
repeat
EndMCOLORING算法6.8生成下一种颜色
ProcedureNEXTVALURE(k)
//进入此过程前X(1),X(2),…,X(k-1)已分得了区域[1,m]中的整数且相邻近的结点有不同的整数。本过程在区域[0,m]中给X(k)确定一个值：如果还剩下一些颜色，它们与结点k邻接的结点分配的颜色不同，那么就将其中最高标值的颜色分配给结点k;如果没剩下可用的颜色，则置X(k)为0//
globalintegerm,n,X(1:n)booleanGRAPH(1:n,1:n)
integerj,k
loop
X(k)=(X(k)+1)mod(m+1)//试验下一个最高标值的颜色//
ifX(k)=0thenreturnendif//全部颜色用完//
forj=1tondo//检查此颜色是否与邻近结点的那些颜色不同//
ifGRAPH(k,j)andX(k)=X(j)//如果(k,j)是一条边,并且邻近的结点有相同的颜色//
thenexitendif
repeat
ifj=n+1thenreturnendif//找到一种新颜色//
repeat//否则试着找另一种颜色//
endNEXTVALUREX1

X2

X3

X46.5哈密顿环算法:生成下一个结点算法:找所有的哈密顿环6.60/1背包问题算法:限界函数算法:0/1背包问题的回溯法求解例6.70算法说明算法说明算法有边界效应的限界函数算法改进的背包算法用动态状态空间树解0/1背包问题用动态状态空间树解0/1背包问题用动态状态空间树解0/1背包问题用动态状态空间树解0/1背包问题实例用动态状态空间树解0/1背包问题