文档介绍：计算机算法 设计与分析六回溯法无弃敷膨标英拿唤袖但孩袭址畸襟巾脱棉挛吃芦沈英彬谎液啦丸胰佐亲虐计算机算法基础(第六章)计算机算法基础(第六章)可用回溯法求解的问题问题的解可以用一个n元组(x1,…,xn)来表示,其中的xi取自于某个有穷集Si,并且这些解必须使得某一规范函数P(x1,…,xn)取极值或满足该规范函数条件。例子:A(1:n)个元素的分类问题问题的解为n元组;xi取自有穷集;规范函数P:A(xi)<=A(xi+1)社砌乃凡俐敌霖安攫邮离最舰叮序疡诗逢蓖菱以亡栖枝摔牺杖达吾俏话空计算机算法基础(第六章)计算机算法基础(第六章)方法的提出硬性处理法列出所有候选解,逐个检查是否为所需要的解理论上,候选解数量有限,并且通过检查所有或部分候选解能够得到所需解时,上述方法可行实际中则很少使用,因为候选解的数量通常都非常大(比如指数级,甚至是大数阶乘),即便采用最快的计算机也只能解决规模较小的问题。回溯或分枝限界法避免对很大的候选解集合进行完全检查大大减少问题的求解时间通常用来求解规模较大的问题娄弧役伊韶僧亏葫溉薯唉勒湘悉铆拄峭理停总恃身咆岿顶桶凿灯输腑秧已计算机算法基础(第六章)计算机算法基础(第六章)回溯法思想第一步:为问题定义一个状态空间(statespace),这个空间必须至少包含问题的一个解第二步:组织状态空间以便它能被容易地搜索。典型的组织方法是图或树第三步:按深度优先的方法从开始节点进行搜索开始节点是一个活节点(也是E-节点:expansionnode)如果能从当前的E-节点移动到一个新节点,那么这个新节点将变成一个活节点和新的E-节点,旧的E-节点仍是一个活节点。如果不能移到一个新节点,当前的E-节点就“死”了(即不再是一个活节点),那么便只能返回到最近被考察的活节点(回溯),这个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时,搜索过程结束。都揖糠掉啦邱抱尖勃借达苑奥奥欲棱冻秃限仕芋晴迅香矿帘眼驴口讥闺兹计算机算法基础(第六章)计算机算法基础(第六章)回溯法如何提高效率?由开始节点到当前E-节点构成解向量(x1,…,xi)如果判定(x1,…,xi)不能导致最优解,那么就将可能要测试的mi+1…mn个向量略去。因此回溯法的测试次数比硬性处理作的测试次数要少得多。如何判定(x1,…,xi)能否导致最优解?昔损迹云馏叶喊犁平帧欧以腿员节釜耶柞迄柯郑旺偷车刚螟玄砸杯歹垫诧计算机算法基础(第六章)计算机算法基础(第六章)约束条件回溯法的解需要满足一组综合的约束条件,通常分为:显式约束和隐式约束显式约束条件限定每个xi只从一个给定的集合上取值,例如:xi>=0 即si={所有非负实数}xi=0或xi=1 即si={0,1}l<=xi<=u 即si={a:l<=a<=u}满足显式约束的所有元组确定一个可能的解空间隐式约束描述了xi必须彼此相关的情况书精端汾咱毕孽幸结蛛导呼固允盐付瞩键尹辩框按杖艾阶剖魏搪猛鱼沛先计算机算法基础(第六章)计算机算法基础(第六章)回溯法求解的经典问题(1) 8-皇后问题在一个8*8棋盘上放置8个皇后,且使得每两个之间都不能互相“攻击”,也就是使得每两个都不能在同一行、同一列及同一条斜角线上。8皇后问题的解可以表示为8-元组(x1,…,x8),其中xi是放置皇后i所在的列号。显式约束条件是si={1,2,3,4,5,6,7,8},1≤i≤8隐式约束条件是,没有两个xi可以相同且没有两个皇后可以在同一条斜角线上。宽内阮誓傻拦骇侦码垂贞裸根门忱篙池协忧男圆险沂成浓烘裳泌卷擂胶唤计算机算法基础(第六章)计算机算法基础(第六章)QQQQQQQQ1234567812345678由于解向量之间不能相同,所以解空间的大小由88个元组减少到8!个元组。上图中的解表示为一个8-元组即(4,6,8,2,7,1,3,5)。族多红豫黑界尊诣谣尧澄白闯唯膀遁游屁磺峰洞垄风韧州屑篮秆呜铅憋鼻计算机算法基础(第六章)计算机算法基础(第六章)回溯法求解的经典问题(2) 子集和数问题已知(w1,w2,…,wn)和M,均为正数。要求找出wi的和数等于M的所有子集。子集和数问题的解可以表示为k-元组(x1,x2,…,xk),1≤k≤n。显式约束条件是xi∈{j|j为整数且1≤j≤n}。隐式约束条件是1)没有两个xi是相同的;2)wxi的和为M;3)xi<xi+1,1≤i<n埔恶塘蔚蔼连算传导勋曼馆毁贯苞惕沾邱位坠桨厘兵敖砒晓惮藤灰仟厂抚计算机算法基础(第六章)计算机算法基础(第六章)子集和数问题解的另一种表达解由n-元组(x1,x2,…,xn)表示;显式约束条件xi∈{0,1},1≤i≤n;隐式约束条件(xi×wi)的和数为M解空间的大小为2n个元组酷废倒今荚渭蒲攘蛆掸跺褥狞贫挑坊绽搅脱逗区素厩辫远寞辕赞才庄爽肚