复杂问题解法的提示16.1回溯算法的思想16.2回溯算法的应

复杂问题解法的提示16.1回溯算法的思想16.2回溯算法的应用货箱装船旅行商问题（TSP问题）Chapter16回溯2022/11/711、寻求问题解的常规思路首先列出所有候选解然后依次检查每一个解，直到找到所需的解【可行性前提】：候选解数量有限，并且能够通过检查所有或部分候选解得到所需的解2022/11/72示例1：百元百鸡问题使用枚举法求解：百元买百鸡问题公鸡每只5元，母鸡每只3元，小鸡3只1元x+y+z=1005x+3y+z/3=1001<=x<=20，1<=y<=33解法：枚举所有满足条件的候选解缺点：运算量大；改进：找到限定规则2022/11/73对候选解进行系统检查的常用方法回溯分支定界避免对很大的候选解集合进行检查，同时能够保证算法运行结束可以找到所需要的解；通常能够用来求解规模很大的问题。2022/11/74回溯算法思想回溯算法，也叫试探算法。是一种系统的搜索问题的解的方法。【基本思想】从一条路往前走，能进则进，不能进则退回来，换一条路再试。2022/11/75示例2：n皇后问题在n行n列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称它们为互相攻击。【n皇后问题】找到这n个皇后的互不攻击的布局。8x8Chessboard2022/11/76查找时间与问题规模相关4x48x82022/11/77用回溯算法解决问题的一般步骤一、定义一个解空间，这个解空间必须至少包含问题的一个解（可能最优）；二、用易于搜索的方式组织该解空间。典型的组织方式是图（如迷宫）或树（如0/1背包）。三、按深度优先法从开始节点进行搜索。四、利用限界函数避免移动到不可能产生解的子空间。【回溯算法重要特性】问题的解空间通常是在搜索问题的解的过程中动态产生的。2022/11/78示例：3*3迷宫问题（图16-1）1、定义解空间：包含从入口到出口的所有路径；2、组织解空间：用图的形式给出。从点(1,1)到(3,3)的每一条路径都定义了3*3迷宫解空间中的一个元素；3、搜索解空间：从开始节点（1，1）进行深度优先搜索。2022/11/79示例：n个对象的0/1背包问题（图16-2）1、定义解空间：2n个长度为n的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))}2、组织解空间：用树的形式给出。第i层到第i+1层节点的一条边上的数字：向量x中第i个分量的值xi；从根节点到叶节点的每一条路径都定义了解空间中的一个元素。3、搜索解空间：开始节点为根节点进行深度优先搜索。2022/11/710活节点、死节点和E-节点活节点：开始节点是活节点，也是E-节点。死节点E-节点（ExpansionNode）及回溯从E节点可移动到一个新的节点；如果能从当前节点移动到一个新的节点，则这个新节点将变成一个活节点和新的E-节点；旧的E-节点仍然是个活节点。如果不能够移到一个新节点，则该E-节点成为死节点，只能返回到最近被考察的活节点（回溯），这个活节点变成新的E-节点。当已经找到答案或者回溯尽了所有的活节点时，搜索过程结束。2022/11/711限界函数通过确定一个新近到达的节点能否导致一个比当前最优解还要好的解，可以加速对最优解的搜索。如果不能，则移动到该节点的任何一个子树都是无意义的，这个节点可被立即杀死。用来杀死活节点的策略称为：限界函数（BoundingFunction）。2022/11/712解空间图：3*3迷宫老鼠问题

（P185程序5-13回溯算法）寻找从(1，1)到(3，3)的一条路径左图中，从起点到终点的每一条路径都定义了解空间中的一个元素。搜索结果：(1,1)-(2,1)-(3,1)-(3,2)-(3,3)2022/11/713解空间树：0/1背包问题从n个物品中选择装入背包的物品约束条件：左图为n=3时的解空间树n=3时，0/1背包问题的求解过程w=[20,15,15],p=[40,25,25],c=30剩余容量收益1040当前最优:ABEK1525050最优解:ACFL【限界函数】杀死代表不可行解决方案的节点。示例：旅行商问题（TSP）旅行商需要找到一条从家里出发，访问所有城市后返回原处的旅游环路。要求：路径最短或耗费最小HomecityVisitcity2022/11/716旅行商问题的定义顶点：旅行商所要旅行的城市（包括起点）边的耗费：给出了在两个城市旅行所需的时间（或花费）旅行：表示当旅行商游览了所有城市再回到出发点时所走的路线例如：旅行1-3-2-4-1的耗费为25，最小！2022/11/717解空间描述：排列树一个旅行：由树中的一条从根到叶的路径表示。例如：ABCFL表示旅行1-2-3-4-1

树中叶节点的数目（n-1）!2022/11/718n=4时，旅行商问题的求解过程路径耗费123415912431661324125【限界函数】如果目前建立的部分的费用大于或等于当前最佳路径的费用，则杀死当前节点。例如：到达I时，部分旅行耗费1,3,4的耗费为26>25，所以，搜索以I为根节点的子树毫无意义。2022/11/719回溯算法的解空间形式子集树：当问题解空间树是n个元素的一个子集时，例如：0/1背包问题子集树有2n个叶节点，遍历耗时Ω(2n)排列树：当问题解空间树是n个元素的一个排列时，例如：旅行商问题排列树有n!个叶节点，遍历耗时Ω(n!)2022/11/720回溯算法小结步骤：定义一个解空间，它包含问题的解；用适于搜索的方式组织该空间；用DFS法搜索该空间，并使用限界函数加速对最优解的搜索，避免不必要的移动在搜索期间的任何时刻，仅保留从开始节点到当前E节点的路径，因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）；解空间的大小是该长度的指数或阶乘！——全部存储解空间，不够用。2022/11/7213、回溯算法的应用货箱装船问题：子集树旅行商问题：排列树2022/11/722（1）货箱装船问题有两艘船，n个货箱。第一艘船的载重量是c1，第二艘船的载重量是c2，Wi是货箱i的重量且寻求一种将n个货箱全部装船的方法例如：当n=3，c1=c2=50，w=[10,40,40]；可将货箱1,2装到第一艘船上，货箱3装到第二艘船上。再如：w=[20,40,40]，结果如何？解决策略存在一种方法能够装载所有n个货箱时，可以验证以下的装船策略可以获得成功：1)尽可能地将第一艘船装至它的重量极限2)将剩余货箱装到第二艘船为了尽可能地将第一艘船装满，需要选择一个货箱的子集，它们的总重量尽可能接近c12022/11/724第一种回溯算法思想：寻找即寻找一个重量的子集尽量接近c1。限界函数：定义表示节点O的当前重量；若cw>c1，则表示以O为根的子树不能产生一个可行的解答，避免移动。n=4时，求解过程w=[8，6，2，3]，C1=12cw=8cw=10cw=8cw=11最优解x:[1,0,0,1]2022/11/726第一种回溯算法-代码分析Page498：程序16-1注意：一个可行节点的右孩子总是可行时间复杂度：O(2n)递归栈空间：O(n)2022/11/727第二种回溯算法：优化如果当前节点的右子树不可能包含比当前最优解更好的解时，就不移动到右子树上！设bestw为当前最优解，Z为解空间树的第i层的一个节点限界函数：为剩余货箱的重量；当cw+r<=bestw时，没有必要去搜索Z的右子树Page499：程序16-2寻找最优子集Page500：程序16-3引入bestx，记录当前找到的最优货箱子集时间复杂度：O(n2n)降低复杂度的两种方法：Page5012022/11/729（2）旅行商问题解空间是排列树可采用Page8的Perm函数，产生n个元素表的所有排列作为类AdjacencyWDigraph的成员2022/11/730使用递归函数生成排列（P7例1-3）【例】a,b,c的排列方式有：abc，acb，bac，bca，cab，cba。共6种（n个元素的排列方式共有n！种）令E{e1，…，en}表示n个元素的集合。令Ei为移去元素i后所得的集合，perm(X)表示集合X中元素的排列方式，ei.perm(X)表示在perm(X)中的每个排列方式的前面均加上ei以后所得到的排列方式。例如，若E={a,b,c}，则E1={b,c},perm(E1)={bc,cb}, e1.perm(E1)={abc,acb}2022/11/731使用递归函数生成排列（P7例1-3）【递归出口】n=1。当只有一个元素时，只可能产生一种排列方式，即perm(E)=e，其中e是E中唯一的元素。当n>1时，perm(E)=e1.perm(E1)+e2.perm(E2)+e3.perm(E3)+…en.perm(En)即采用n个perm(X)来定义perm(E)，其中每个X包含n-1个元素。【例】当n=3，并且E={a，b，c}则，perm(E)=a.perm({b,c})+b.perm({a,c})+c.perm({a,b})perm({b,c})=b.perm(c)+c.perm(b)a.perm({b,c})=ab.perm(c)+ac.perm(b)=ab.c+ac.b=(abc,acb)2022/11/732使用递归函数生成排列（P7例1-3）a.perm({b,c})包含两个排列式：abc和acb，a是它们的前缀，perm({b,c})是它们的后缀同样，ac.perm({b})表示前缀ac，后缀为perm({b})的排列方式。程序1-10输出所有前缀为list[0:k-1]，后缀为list[k,m]的排列方式。2022/11/733使用递归函数生成排列（程序1-10）template<classT>voidPerm(Tlist[],intk,intm){//Generateallpermutationsoflist[k:m].inti;if(k==m){//输出一个排列方式for(i=0;i<=m;i++)cout<<list[i];cout<<endl;}

2022/11/734使用递归函数生成排列（程序1-10）else//list[k:m]hasmorethanonepermutation//generatetheserecursivelyfor(i=k;i<=m;i++){Swap(list[k],list[i]);Perm(list,k+1,m);Swap(list[k],list[i]);}}2022/11/735预处理程序：TSPtemplate<classT>TAdjacencyWDigraph<T>::TSP(intv[]){x=newint[n+1];保存到当前节点的路径for(inti=1;i<=n;i++)x[i]=i;bestc=NoEdge;bestx=v;保存最优解路径cc=0;tSP(2);搜索x[2:n]的各种排列delete[]x;returnbestc;返回最优解耗费}2022/11/736tSP函数结构与Perm函数相同。当i=n时，处在排列树的叶节点的父节点上，并且需要验证从x[n-1]到x[n]有一条边，从x[n]到起点x[1]也有一条边。若两边都存在，则发现一个新旅行。若发现的旅行是目前发现的最优旅行，则将旅行和它的耗费分别存入bestx和bestc中。当i<n时，检查当前i-1层节点的孩子节点，并且仅当以下情况出现时，移动到孩子节点之一：（1）有从x[i-1]到x[i]的一条边（如果是的话，x[1:i]定义了网络中的一条路径）；（2）路径x[1:i]的耗费小于当前的最优解的耗费.变量cc保存目前所构造的路径的耗费。2022/11/737迭代回溯算法：tSPtemplate<classT>a[N][N]表示两个节点之间是否有边voidAdjacencyWDigraph<T>::tSP(inti){if(i==n)位于叶子节点的父节点{if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc==NoEdge)){找到更优的旅行路径for(intj=1;j<=n;j++)bestx[j]=x[j];bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];}}2022/11/738迭代回溯算法：tSPcont.else{for(intj=i;j<=n;j++)判断是否能移到子树x[j]if(a[x[i-1]][x[j]]!=NoEdge&&(cc+a[x[i-1]][x[i]]<bestc||bestc==NoEdge)){类perm的排列法搜索Swap(x[i],x[j]);cc+=a[x[i-1]][x[i]];tSP(i+1);cc-=a[x[i-1]][x[i]];Swap(x[i],x[j]);}}}2022/11/739本章小结