回溯算法(一)

回溯算法(一)重庆教育学院杨华千回溯算法：一般方法基本要求：问题的解必须能表示成一个n-元组(x1,x2,…xn)，其中xi是取自某个有穷集合Si。通常，所求解的问题需要求取一个使某一规范函数P(x1,…,xn)取极大值(或取极小值或满足该规范函数条件)的向量。回溯算法：一般方法基本思想：(假定集合Si的大小是mi)不断地用修改过的规范函数Pi(x1,…,xi)去测试正在构造中的n-元组的部分向量(x1,…,xi)，看其是否可能导致最优解。如果判定(x1,…,xi)不可能导致最优解，那么就将可能要测试的mi+1…mn个向量略去。回溯算法：一般方法约束条件：(1)显式约束：限定每一个xi只能从给定的集合Si上取值。(2)解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。(3)隐式约束：规定解空间中实际上满足规范函数的元组，描述了xi必须彼此相关的情况。回溯算法：一般方法基本做法：在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯算法：0-1背包问题问题描述：iijixp1jiwxxxwiiiiji1,0}1,0{,1回溯算法：0-1背包问题解空间：n=3时的0-1背包问题用完全二叉树表示的解空间回溯算法：0-1背包问题例子：n=3,M=30,w={16,15,15},p={45,25,25}回溯算法：0-1背包问题ACr=C=30，V=0Bw1=16，v1=45Cr=14，V=45CCr=30，V=0DCrw2不可行解JCrw3不可行解KCr=14V=45x=(1,0,0)HIECr=14V=45Lw3=15，v3=25Cr=0，V=505045x=(0,1,1)Fw2=15，v2=25Cr=15，V=25M2550不是最优解回溯算法：8-皇后问题问题描述：在一个8×8棋盘上放置8个皇后，且使得每两个之间都不能互相“攻击”，也就是使得每两个都不在同一行、同一列及同一条斜角线上。回溯算法：8-皇后问题解示例：QQQQQQQQ1287654312345678回溯算法：子集和数问题问题描述：已知n+1个正数：wi(1≤i≤n)，和M。要求找出wi的和数是M的所有子集。回溯算法：n-皇后问题问题描述：n个皇后将被放置在一个n×n的棋盘上且使得没有两个皇后可以互相攻击。解空间由n-元组(1,2,…,n)的n!种排列所组成。由i级到i+1级的边用xi的值标记。回溯算法：n-皇后问题n=4时的解空间树结构2022192527243032291836383541434046484534463911814161325254515759566264615021232628313337394244474957101215175355586063651x1=1x1=2x1=3x1=4x2=2x2=3x2=4x2=1x2=3x2=4x2=1x2=2x2=4x2=1x2=2x2=3342423341413241412231312434232434131424121323121回溯算法：n-皇后问题一些解空间树结构的术语：问题状态：树中的每一个结点确定所求解问题的一个状态。状态空间：由根结点到其它结点的所有路径则确定了这个问题的状态空间。解状态：是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。答案状态：是这样一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这个问题的一个解。状态空间树：解空间的树结构。回溯算法：n-皇后问题问题求解过程：状态空间树→问题状态→解状态→答案状态回溯算法：n-皇后问题回溯法－－术语：活结点：已生成一个结点而它的所有儿子结点还没有全部生成的结点称为活结点。E-结点：当前正在生成其儿子结点的活结点叫E-结点。死结点：不再进一步扩展或其儿子结点已全部生成的结点称为死结点。回溯算法：n-皇后问题回溯法－－过程：当前的E-结点R一旦生成一个新的儿子C（开始时，把根结点作为唯一的活结点，这个活结点就成为E-结点），这个儿子结点就变成一个新的E-结点，当完全检测了子树C之后，R结点就再次成为E-结点。这相当于问题状态的深度优先生成。在这个过程中，将用限界函数去杀死还没有全部生成其儿子结点的那些活结点。使用限界函数的深度优先结点生成方法称为回溯法。回溯算法：n-皇后问题回溯法－－过程：（n=4）11..212....12.3123....11...2123..4(a)(b)(c)(d)(e)(f)(g)(h)回溯算法：n-皇后问题n=8，隐式条件：(1)没有两个xi可以相同。所有解是8-元组(1,2,3,4,5,6,7,8)的置换(2)没有两个皇后可以在同一条斜角线上。(假设有两个皇后被放置在(i,j)和(k,l)位置上，则要求|j-l|≠|i-k|)回溯算法：n-皇后问题限界函数intplace(intk,intX[N+1]){inti;i=1;while(ik){if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))return0;i++;}return1;}回溯算法：n-皇后问题回溯过程voidNqueens(intX[N+1]){intk,i;X[1]=0;k=1;while(k0){X[k]=X[k]+1;while((X[k]=N)&&(!place(k,X)))/*移向下一列，即生成下一个儿子*/X[k]=X[k]+1;if(X[k]=N)if(k==N){for(i=1;i=N;i++)printf(%3d,X[i]);printf(\n);}else{k=k+1;/*移动到下一行*/X[k]=0;}elsek=k-1;/*回溯到上一行*/}}回溯算法：n-皇后问题#includestdio.h#includemath.h#defineN4intplace(intk,intX[N+1]){inti;i=1;while(ik){if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))return0;i++;}return1;}voidNqueens(intX[N+1]){intk,i;X[1]=0;k=1;while(k0){X[k]=X[k]+1;while((X[k]=N)&&(!place(k,X)))X[k]=X[k]+1;if(X[k]=N)if(k==N){for(i=1;i=N;i++)printf(%3d,X[i]);printf(\n);}else{k=k+1;X[k]=0;}elsek=k-1;}}voidmain(){intn,i;intX[N+1]={0};clrscr();Nqueens(X);printf(Theend!);}