第六章回溯法

NorthChinaElectricPowerUniversity计算机算法设计与分析NorthChinaElectricPowerUniversityComputerAlgorithmsDesign&Analysis华北电力大学计算机科学与工程系Dept.ofComputerScience&EngineeringofNorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity第六章回溯算法(BacktrackingAlgorithm)★回溯法的算法框架★自然数的排列问题★婚姻搭配问题★n后问题★图的着色问题NorthChinaElectricPowerUniversity★旅行售货员问题★符号三角形问题NorthChinaElectricPowerUniversity§1回溯法的算法框架NorthChinaElectricPowerUniversity回溯法是一个既带有系统性又带有跳跃性的的搜索算法。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任何一个结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树搜索。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可结束。NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity1.问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个最优解。例如，对于有n种可选择的物品的0-1背包问题，其解空间由长度为n的0-1向量组成。该解空间包含了对变量的所有可能的0-1赋值。例如，当n=3时，其解空间{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}。ABCDEFGHIJLKMNO10101010101010通常将问题的解空间组织成树或图的形式。例如，对于n=3的0-1背包问题，其解空间树可用下面的完全二叉树表示。NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity2.回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点(根结点)出发，以深度优先搜索的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。在用回溯法搜索解空间树时，通常采用两种策略来避免无效搜索，提高回溯法的搜索效率。其一是用约束函数在扩展结点处剪去不满足约束条件的子树；其二是用限界法剪去不能得到最优解的子树。这两类方法统称为剪枝函数。NorthChinaElectricPowerUniversityABCDEFGILKMNOx1=1x1=0x2=1x2=0Hx3=1x3=0Jx3=1x3=0x2=1x2=0x3=1x3=0x3=1x3=0例：0-1背包问题n=3，C=20，(p1,p2,p3)=(20,15,25)(w1,w2,w3)=(10,5,15)，求X=(x1,x2,x3)使背包价值最大？(10,20)(15,35)(15,35)(10,20)(10,20)(5,15)(20,40)(15,35)(5,15)(20,40)(0,0)(0,0)(15,25)(20,40)(20,40)(0,0)(20,40)当前最优解可行解中间计算结果NorthChinaElectricPowerUniversity综上所述，运用回溯法解问题通常包含以下三个步骤：1)针对所给问题，定义问题的解空间；2)确定易于搜索的解空间结构3)以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。3.递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：voidBacktrack(intt){if(tn)Output(x);elsefor(inti=f(n,t);i=g(n,t);i++)//f(n,t)和g(n,t):在当前扩展结点处未搜索过的子树//的起始编号和终止编号{x[t]=h(i);if(Constraint(t)&&Bound(t))Backtrack(t+1);}}//Constraint(t)和Bound(t):在当前扩展结点处的约束函数和限界函数NorthChinaElectricPowerUniversity4.子集树和排列树背包问题和旅行售货员问题的解空间树是两种典型的解空间树。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树为子集树。这类子集树常有2n个叶结点，其结点个数为2n+1-1。遍历子集树的任何算法均需Ω(2n)的计算时间。当所给问题是确定n个元素的满足某种性质的排列时，相应的解空间树为排列树。排列树通常有n!各叶结点。因此遍历排列树所需的计算时间需要Ω(n!)的计算时间。用回溯法搜索子集树的一般算法可描述为：voidBacktrack(intt){if(tn)Output(x);elsefor(inti=0;i=1;i++){x[t]=i;if(Constraint(t)&&Bound(t))Backtrack(t+1);}}NorthChinaElectricPowerUniversity用回溯法搜索排列树的算法框架可描述如下：voidBacktrack(intt){if(tn)Output(x);elsefor(inti=t;i=n;i++){Swap(x[t],x[i]);if(Constraint(t)&&Bound(t))Backtrack(t+1);Swap(x[t],x[i]);}}在调用Backtrack(1)执行回溯调用之前，先将变量数组x初始化单位排列(1,2,…,n)。NorthChinaElectricPowerUniversity§2自然数的排列问题给定正整数n,使设计一个算法，列举出1,2,…,n的所有排列。问题描述：分析与解答：问题的解空间显然为一棵排列树，可用回溯法求解，算法描述如下：voidpailie(intx[],intt,intn){if(tn){for(inti=1;i=n;i++)coutx[i];coutendl;}elsefor(inti=t;i=n;i++){swap(x,t,i);pailie(x,t+1,n);swap(x,t,i);}}NorthChinaElectricPowerUniversity§3婚姻搭配问题问题描述：有n对男女要配成n对夫妇，其中第i位男士对第j位女士的爱恋程度为p[i][j]，第i位女士对第j位男士的爱恋程度为q[i][j],显然p[i][j]不一定等于q[j][i]，设计一个算法，确定各对夫妇的最佳婚配，使方案中各对夫妇的婚姻最满意。分析与解答：刻划n对夫妇婚姻总体的满意程度的标准：S=Σp[i][i’]*q[i’][i]i=1i=n其中第i位男士的配偶为第i’位女士不同的婚配方案共有n!种，采用回溯算法找出各种婚配方案，计算不同方案的婚姻满意度，使S取值最大的方案即为所求解。NorthChinaElectricPowerUniversityvoidperference(ints[],intk,intn){if(k=n){for(inti=k;i=n;i++){swap(b[k],b[i]);perference(k+1,n);swap(b[k],b[i]);}}else{floattmp=0;for(inti=1;i=n;i++)tmp=tmp+p[i][b[i]]*q[b[i]][i];if(tmppref){pref=tmp;for(i=1;i=n;i++){c[i]=b[i];d[c[i]]=i;}}}}NorthChinaElectricPowerUniversityij12310.40.60.520.50.70.830.70.60.5ij12310.60.70.520.70.80.930.90.80.7例：设X={x1,x2,x3},Y={y1,y2,y3}，矩阵P和Q分别如下，计算其最佳匹配方案。矩阵P矩阵QNorthChinaElectricPowerUniversity§4n后问题1.问题描述：2.算法设计：要求在一个n*n的棋盘上放置n个皇后，使得它们彼此不受攻击。一个皇后可以攻击与之处在同一行或同一列或同一斜线上的任何其他棋子。问题的解可表示为x[1:n]，表示皇后i放在棋盘的第i行的第x[i]列。a)x[i]≠x[j],i≠j：不允许将任何两个皇后放在同一列上；b)|j-i|≠|x[j]-x[i]|:不允许两个皇后位于同一条斜线上。NorthChinaElectricPowerUniversity问题的解空间的形式为：要找出”四皇后”问题的解，最可靠的方法就是把各种情况全部检核一遍，将符合条件A的解找出来。但这样做，你要有相当耐心才行，这是很费时的。采用回溯算法进行求解，在搜索的过程中，将不满足条件要求的分支树减去，可以有效的降低算法的时间复杂性。NorthChinaElectricPowerUniversity(a)(b)(c)(d)四皇后问题的两个解NorthChinaElectricPowerUniversity皇后的个数问题的解n=1X=(1)n=2无解n=3无解n=4X1=(2,4,1,3);X2=(3,1,4,2)n=5X1=(1,3,5,2,4);X2=(1,4,2,5,3);X3=(2,4,1,3,5);X4=(2,5,3,1,4)X5=(3,1,4,2,5);X6=(3,5,2,4,1);X7=(4,1,3,5,2);X8=(4,2,5,3,1)X9=(5,2,4,1,3);X10=(5,3,1,4,2)n=6X1=(2,4,6,1,3,5);X2=(3,6,2,5,1,4);X3=(4,1,5,2,6,3);X4=(5,3,1,6,4,2)n=740个解n=892个解n=9352个解n=10724个解N皇后问题解的情况NorthChinaElectricPowerUniversity解n后问题的算法描述如下：classQueen{friendintnQueen(int);private:boolPlace(k);voidBacktrack(intt);intn;//皇后个数int*x;//当前解longsum;//当前已找到的可行方案数};NorthChinaElectricPowerUniversityvoidQueen::Backtrack(intt){if(tn)sum++;elsefor(inti=1;i=n;i++){x[t]=i;if(Place(t))Backtrack(t+1);}}intnQueen(intn){Queenx;x.n=n;x.sum=0;int*p=newint[n+1];for(inti=0;i=n;i++)p[i]=0;x.x=p;x.Backtrack(1);delete[]p;returnx.sum;}boolQueen::Place(intk){for(intj=1;jk;j++)if(abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]