博弈树搜索课件

University of Science and Technology of China主讲人：主讲人：吕敏吕敏Email: Spring 2012，USTC算法基础算法基础算法基础算法基础University of Science and Technology of China2024/7/222第十一讲第十一讲 回溯法回溯法内容提要：内容提要：p 理解回溯法的深度优先搜索策略理解回溯法的深度优先搜索策略p 掌握用回溯法解题的算法框架掌握用回溯法解题的算法框架 子集树算法框架 排列树算法框架p 通过应用范例学习回溯法的设计策略通过应用范例学习回溯法的设计策略2023/8/152第十一讲第十一讲 回溯法内容提要：回溯法内容提要：University of Science and Technology of China3l搜索算法介绍搜索算法介绍（1 1）穷举搜索）穷举搜索（2 2）盲目搜索）盲目搜索 深度优先深度优先(DFS)(DFS)或回溯搜索或回溯搜索(Backtracking);(Backtracking);广度优先搜索广度优先搜索(BFS);(BFS);分支限界法分支限界法 (Branch&Bound)(Branch&Bound)；博弈树搜索博弈树搜索(-Search)Search)（3 3）启发式搜索）启发式搜索 A*A*算法和最佳优先算法和最佳优先(Best-First Search)(Best-First Search)迭代加深的迭代加深的A*A*算法算法 B*,AO*,SSS*B*,AO*,SSS*等算法等算法 Local Search,GA Local Search,GA等算法等算法11-1 方法概述方法概述3搜索算法介绍搜索算法介绍11-1 方法概述方法概述University of Science and Technology of China4p搜索空间的三种表示：搜索空间的三种表示：表序表示：搜索对象用线性表数据结构表示；表序表示：搜索对象用线性表数据结构表示；显示图表示：搜索对象在搜索前就用图（树）的数据结构表示；显示图表示：搜索对象在搜索前就用图（树）的数据结构表示；隐式图表示：除了初始结点，其他结点在搜索过程中动态生成。缘于搜隐式图表示：除了初始结点，其他结点在搜索过程中动态生成。缘于搜索空间大，难以全部存储。索空间大，难以全部存储。p搜索效率的思考：随机搜索搜索效率的思考：随机搜索 上世纪上世纪7070年代中期开始，国外一些学者致力于研究随机搜索求解困难的年代中期开始，国外一些学者致力于研究随机搜索求解困难的组合问题，将随机过程引入搜索；组合问题，将随机过程引入搜索；选择规则是随机地从可选结点中取一个，从而可以从统计角度分析搜索选择规则是随机地从可选结点中取一个，从而可以从统计角度分析搜索的平均性能；的平均性能；随机搜索的一个成功例子是：判定一个很大的数是不是素数，获得了第随机搜索的一个成功例子是：判定一个很大的数是不是素数，获得了第一个多项式时间的算法。一个多项式时间的算法。11-1 方法概述方法概述4搜索空间的三种表示：搜索空间的三种表示：11-1 方法概述方法概述University of Science and Technology of China5p回溯法：回溯法：回溯法是一个既带有系统性又带有跳跃性的搜索算法；回溯法是一个既带有系统性又带有跳跃性的搜索算法；它在包含问题的所有解的解空间树中，按照深度优先的策略，它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。从根结点出发搜索解空间树。系统性系统性 算法搜索至解空间树的任一结点时，判断该结点为根的子树是算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续深度优先的策略进行搜索。深度优先的策略进行搜索。跳跃性跳跃性 这种以深度优先的方式系统地搜索问题的解的算法称为回溯这种以深度优先的方式系统地搜索问题的解的算法称为回溯法法，它适用于解一些组合数较大的问题。，它适用于解一些组合数较大的问题。11-1 方法概述方法概述5回溯法：回溯法：11-1 方法概述方法概述University of Science and Technology of China6p问题的解空间问题的解空间 问题的解向量：回溯法希望一个问题的解能够表示成一个问题的解向量：回溯法希望一个问题的解能够表示成一个n n元式元式 (x (x1 1,x,x2 2,x,xn n)的形式。的形式。显约束：对分量显约束：对分量x xi i的取值限定。的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元 组，组，构成了该实例的一个解空间。构成了该实例的一个解空间。11-1 方法概述方法概述注意：注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。更小（存储量少，搜索方法简单）。n=3n=3时的时的0-10-1背包问题用完全二叉树表示的解空间背包问题用完全二叉树表示的解空间6问题的解空间问题的解空间11-1 方法概述注意：同一个问题可以有多种表方法概述注意：同一个问题可以有多种表University of Science and Technology of China711-1 方法概述方法概述711-1 方法概述方法概述University of Science and Technology of China8p基本思想：基本思想：搜索从开始结点（根结点）出发，以深度优先搜索整个解空间。搜索从开始结点（根结点）出发，以深度优先搜索整个解空间。这个开始结点成为这个开始结点成为活结点活结点，同时也成为当前的，同时也成为当前的扩展结点扩展结点。在当前的扩展。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为为死结点死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点；直到找到一个解或全部解。为当前的扩展结点；直到找到一个解或全部解。11-1 方法概述方法概述8基本思想：基本思想：11-1 方法概述方法概述University of Science and Technology of China9p基本步骤：基本步骤：针对所给问题，定义问题的解空间；针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；确定易于搜索的解空间结构；以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索无效搜索。11-1 方法概述方法概述常用剪枝函数：常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。用限界函数剪去得不到最优解的子树。9基本步骤：基本步骤：11-1 方法概述常用剪枝函数：方法概述常用剪枝函数：University of Science and Technology of China10p二类常见的解空间树：二类常见的解空间树：子集树子集树：当所给的问题是从当所给的问题是从n n个元素的集合个元素的集合S S中找出满足某种性质中找出满足某种性质的子集时的子集时，相应的解空间树称为子集树。子集树通常有，相应的解空间树称为子集树。子集树通常有2 2n n个叶子个叶子结点，其总结点个数为结点，其总结点个数为2 2n+1 n+1-1-1，遍历子集树时间为，遍历子集树时间为(2(2n n)。如。如0-10-1背包问题，叶结点数为背包问题，叶结点数为2 2n n，总结点数，总结点数2 2n+1n+1；排列树排列树：当所给问题是确定当所给问题是确定n n个元素满足某种性质的排列时个元素满足某种性质的排列时，相，相应的解空间树称为排列树。排列树通常有应的解空间树称为排列树。排列树通常有n!n!个叶子结点，因此，个叶子结点，因此，遍历排列树需要遍历排列树需要(n!)(n!)的计算时间。如的计算时间。如TSPTSP问题问题(Traveling Salesman Problem，推销员问题，推销员问题)，叶结点数为，叶结点数为n!n!，遍历时间为，遍历时间为(n!)(n!)。11-1 方法概述方法概述10二类常见的解空间树：二类常见的解空间树：11-1 方法概述方法概述University of Science and Technology of China11例1 0-1背包：n=3,w=(16,15,15),v=(45,25,25),c=30(1)定义解空间：X=(0,0,0),(0,0,1),(0,1,0),(1,1,0),(1,1,1)(2)构造解空间树：11-1 方法概述方法概述11例例1 0-1背包背包：n=3,w=(16,15,University of Science and Technology of China1211-1 方法概述方法概述1211-1 方法概述方法概述University of Science and Technology of China13p例例2 2 TSPTSP问题问题:（1 1）定义解空间：）定义解空间：X=12341,12431,13241,13421,14231,14321X=12341,12431,13241,13421,14231,14321（2 2）构造解空间树：）构造解空间树：（3 3）从）从A A出发按出发按DFSDFS搜索整棵树：搜索整棵树：最优解最优解：1324113241，1423114231 成本成本：252511-1 方法概述方法概述13例例2 TSP问题问题:11-1 方法概述方法概述University of Science and Technology of China14l用回溯法解题的一个显著特征是用回溯法解题的一个显著特征是在搜索过程中动态产在搜索过程中动态产生问题的解空间生问题的解空间。在任何时刻，算法只保存从根结点。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为叶结点的最长路径的长度为h(n)h(n)，则回溯法所需的计，则回溯法所需的计算空间通常为算空间通常为O(h(n)O(h(n)。而显式地存储整个解空间则需。而显式地存储整个解空间则需要要O(2O(2h(n)h(n)或或O(h(n)!)O(h(n)!)内存空间。内存空间。11-1 方法概述方法概述14用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解University of Science and Technology of China15l回溯法对解空间作深度优先搜索，因此在一般情况下可用递归函回溯法对解空间作深度优先搜索，因此在一般情况下可用递归函数来实现回溯法：数来实现回溯法：l子集树回溯算法子集树回溯算法Backtrack(int t)Backtrack(int t)/搜索到树的第搜索到树的第t t层层 /由第由第t t层向第层向第t+1t+1层扩展，确定层扩展，确定xtxt的值的值 if tn then output(x);if tn then output(x);/叶子结点是可行解叶子结点是可行解 else else while(all Xt)do while(all Xt)do /Xt/Xt为当前扩展结点的所有可能取为当前扩展结点的所有可能取值集合值集合 xt=Xt xt=Xt中的第中的第i i个值；个值；if(Constraint(t)and Bound(t)if(Constraint(t)and Bound(t)Backtrack(t+1);Backtrack(t+1);执行时，从执行时，从Backtrack(1)Backtrack(1)开始。开始。11-2 算法框架算法框架15回溯法对解空间作深度优先搜索，因此在一般情况下可用递归函回溯法对解空间作深度优先搜索，因此在一般情况下可用递归函University of Science and Technology of China16p排列树回溯法排列树回溯法Backtrack(int t)Backtrack(int t)/搜索到树的第搜索到树的第t t层层 /由第由第t t层向第层向第t+1t+1层扩展，确定层扩展，确定xtxt的值的值 if tn then output(x);if tn then output(x);/叶子结点是可行解叶子结点是可行解 else else for i=t to n do for i=t to n do swap(xt,xi);swap(xt,xi);if(Constraint(t)and Bound(t)if(Constraint(t)and Bound(t)Backtrack(t+1);Backtrack(t+1);swap(xt,xi);swap(xt,xi);11-2 算法框架算法框架16排列树回溯法排列树回溯法11-2 算法框架算法框架University of Science and Technology of China17l问题定义问题定义：给定正整数：给定正整数n n，生成，生成1,2,n1,2,n所有排列。所有排列。l解空间树（排列树）：解空间树（排列树）：当当n=3n=3时时，11-3 排列生成问题排列生成问题17问题定义：给定正整数问题定义：给定正整数n，生成，生成1,2,n所有排列所有排列University of Science and Technology of China1811-3 排列生成问题排列生成问题1811-3 排列生成问题排列生成问题University of Science and Technology of China19l问题描述问题描述：略：略l基本思想基本思想：利用排列生成问题的回溯算法：利用排列生成问题的回溯算法Backtrack(2)Backtrack(2)，对，对x=1,2,nx=1,2,n的的x2.nx2.n进行全排列，则进行全排列，则(x1,x2)(x1,x2)，(x2,x3)(x2,x3)，,(xn,x1),(xn,x1)构成一个回路。在全排列算法构成一个回路。在全排列算法的基础上，进行路径计算保存以及进行限界剪枝。的基础上，进行路径计算保存以及进行限界剪枝。l main(int n)main(int n)ann;xn=1,2,n;bestx;cc=0.0;ann;xn=1,2,n;bestx;cc=0.0;bestv=;bestv=;/bestx/bestx保存当前最佳路径，保存当前最佳路径，bestvbestv保存当前最保存当前最优值优值 input(a);input(a);/输入邻接矩阵输入邻接矩阵 TSPBacktrack(2);TSPBacktrack(2);output(bestv,bestx);output(bestv,bestx);11-4 TSP问题问题19问题描述：略问题描述：略11-4 TSP问题问题University of Science and Technology of China20 TSPBacktrack(int i)TSPBacktrack(int i)/cc/cc记录记录(x1,x2),(xi-1,xi)(x1,x2),(xi-1,xi)的距离和的距离和 if(in)if(in)/搜索到叶结点，输出可行解与当前最优解比较搜索到叶结点，输出可行解与当前最优解比较 if(cc+axn1 bestv or bestv=)if(cc+axn1 bestv or bestv=)bestv=cc+axn1;bestv=cc+axn1;for(j=1;j=n;j+)bestxj=xj;for(j=1;j=n;j+)bestxj=xj;else else for(j=i;j=n;j+)for(j=i;j=n;j+)if(cc+axi-1xj bestv or bestv=)if(cc+axi-1xj half)|(t*(t-1)/2-counthalf)return;/剪枝法，剪除不必要的子树剪枝法，剪除不必要的子树 if(tn)sum+;/到叶子结点，到叶子结点，”+”+”号数和号数和”-”-”号数相同的符号三角形个数增加号数相同的符号三角形个数增加1 1 else for(int i=0;i2;i+)/当前扩展结点当前扩展结点Z Z只有两种可能的取值只有两种可能的取值0 0或或1 1，即只可能有，即只可能有2 2个孩子个孩子 p1t=i;/二维数据二维数据p p记录了符号三角形矩阵记录了符号三角形矩阵 count+=i;/当前符号三角形矩阵中，当前符号三角形矩阵中，”+”+”号的个数号的个数 for(int j=2;j=t;j+)/从第二行起计算从第二行起计算”+”+”号个数，计算可行性约束号个数，计算可行性约束 pjt-j+1=pj-1t-j+1pj-1t-j+2;count+=pjt-j+1;Backtrack(t+1);/扩展到第扩展到第t+1层层 for(int j=2;j n)if(i n)/搜索到可行解搜索到可行解 bestv=(bestv cv)?cv:bestv;bestv=(bestv cv)?cv:bestv;output(x);output(x);else else if(cw+wi=c)if(cw+wi=c)/走左子树走左子树 xi=1;cw+=wi;cv+=vi;xi=1;cw+=wi;cv+=vi;KnapBacktrack(i+1);KnapBacktrack(i+1);cw-=wi;cv-=vi;cw-=wi;cv-=vi;/以下走右子树以下走右子树 xi=0;xi=0;KnapBacktrack(i+1);KnapBacktrack(i+1);11-7 0-1背包问题背包问题main(float c,int n,float w,float v,main(float c,int n,float w,float v,int x)int x)/主程序主程序 float cw=0.0,cv=0.0,bestv=0.0;float cw=0.0,cv=0.0,bestv=0.0;KnapBacktrack(1);KnapBacktrack(1);30无限界函数的算法无限界函数的算法11-7 0-1背包问题背包问题main(flUniversity of Science and Technology of China31p有限界函数的算法有限界函数的算法基本思想基本思想：设设r r是当前扩展结点是当前扩展结点z z的右子树（或左子树）的价值上界，如果的右子树（或左子树）的价值上界，如果cv+r cv+r=bestvn)if(tn)sum+;sum+;for(int i=1;i=n;i+)for(int i=1;i=n;i+)cout xi ;cout xi ;cout endl;cout endl;else else for(int i=1;i=m;i+)for(int i=1;i=m;i+)xt=i;xt=i;if(Ok(t)Backtrack(t+1);if(Ok(t)Backtrack(t+1);bool Color:Ok(int k)bool Color:Ok(int k)/检查颜色可用性检查颜色可用性 for(int j=1;j=n;j+)for(int j=1;j=n;j+)if(akj=1)&(xj=xk)if(akj=1)&(xj=xk)return false;return false;return true;return true;33解向量：解向量：(x1,x2,xn)表示顶点表示顶点i所着颜色所着颜色University of Science and Technology of China34p算法复杂度分析：算法复杂度分析：图图m m可着色问题的解空间树中内结点个数是可着色问题的解空间树中内结点个数是 。对于每一个内结点，在最坏情况下，用对于每一个内结点，在最坏情况下，用okok检查当前扩展结点的每一检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时个儿子所相应的颜色可用性需耗时O(mn)O(mn)。因此，回溯法总的时间。因此，回溯法总的时间耗费是耗费是11-8 图的图的m着色问题着色问题34算法复杂度分析：算法复杂度分析：11-8 图的图的m着色问题着色问题University of Science and Technology of China35通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以下因素：依赖于以下因素：(1)(1)产生产生xtxt的时间；的时间；(2)(2)满足显约束的满足显约束的xtxt值的个数；值的个数；(3)(3)计算约束函数计算约束函数constraintconstraint的时间；的时间；(4)(4)计算上界函数计算上界函数boundbound的时间；的时间；(5)(5)满足约束函数和上界函数约束的所有满足约束函数和上界函数约束的所有xkxk的个数。的个数。好的约束函数能显著地减少所生成的结点数。但这样的约束函数往好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在往计算量较大。因此，在选择约束函数时通常存在生成结点数与约生成结点数与约束函数计算量之间的折衷束函数计算量之间的折衷。11-9 回溯法效率分析回溯法效率分析35通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度University of Science and Technology of China36p对于许多问题而言，在搜索试探时选取对于许多问题而言，在搜索试探时选取xixi的值顺序是任意的。的值顺序是任意的。在其它条件相当的前提下，让可取值最少的在其它条件相当的前提下，让可取值最少的xixi优先优先。从图中关。从图中关于同一问题的于同一问题的2 2棵不同解空间树，可以体会到这种策略的潜力。棵不同解空间树，可以体会到这种策略的潜力。11-9 回溯法效率分析回溯法效率分析(a)(b)图图(a)(a)中，从第中，从第1 1层剪去层剪去1 1棵子树，则从所有应当考虑的棵子树，则从所有应当考虑的3 3元组中一次消去元组中一次消去1212个个3 3元组。对于图元组。对于图(b)(b)，虽然同样从第，虽然同样从第1 1层剪去层剪去1 1棵子树，却只从应当考虑的棵子树，却只从应当考虑的3 3元组中消去元组中消去8 8个个3 3元组。前者的效果明显比后者好。元组。前者的效果明显比后者好。36对于许多问题而言，在搜索试探时选取对于许多问题而言，在搜索试探时选取xi的值顺序是任意的值顺序是任意University of Science and Technology of China谢谢！谢谢！2024/7/2237Q&A 作业：作业：1.P335 22.3-2 2 用回溯法从用回溯法从n个不同元素中取个不同元素中取r个不重复的元素的所有个不重复的元素的所有组合。组合。谢谢！谢谢！2023/8/1537Q&A