算法设计与分析 课件 第四章 回溯法

回溯法第四章主讲人：杨圣云E-mail:yang@回溯法的思想回溯法是属于搜索法的一类算法，主要特点是在可能解空间的搜索过程中，根据某个条件回溯，再开启新的搜索，如此不断的重复，直至找到满足要求的一个解或所有解。回答以下四个问题：1、如何构建可能解空间？2、采用什么样的搜索过程？3、回溯条件是什么？4、什么是满足要求和终止条件？回溯法的简单示例简单全排列问题：对于集合

S={1，2，3}

，求它的三个元素的全排列。请先思考以下问题：1、如何构建可能解空间？一种可能解空间{X1，X2，X3}其中X1，X2，X3是集合S的任一元素。2、什么样的搜索过程？用三个for嵌套搜索这个可能解空间。3、回溯条件是什么？只要X1、X2、X3有两个相同就回溯（或者开启新的搜索）。4、什么是满足要求？X1、X2、X3不相同且前面没出现与他们一样的序列。回溯法的简单示例简单全排列问题：对于集合

S={1，2，3}

，求它的三个元素的全排列。intmain(){intnums[]={1,2,3};for(inti=0;i<3;i++){for(intj=0;j<3;j++){if(j==i)continue;for(intk=0;k<3;k++){if(k==i||k==j)continue;

//输出一个序列：nums[i],nums[j],nums[k]阅读这个代码段，思考并回答前面四个问题。通过简单示例理解算法思想！回溯法:求解全排列问题的框架简单全排列问题：对于集合

S={1，2，3…，n}

，求它的n个元素的全排列。请先思考以下问题：1、如何构建可能解空间？2、什么样的搜索过程？3、回溯条件是什么？4、什么是满足要求？新问题：有没有n变化，但代码不变的框架？for嵌套方式的代码，会因n变化而变化。回溯法:求解全排列问题的框架简单全排列问题：对于集合

S={1，2，3…，n}

，求它的n个元素的全排列。for嵌套方式的代码，会因n变化而变化。新问题：有没有n变化，但代码不变的框架？多叉树的深度优先遍历框架是一种好的不变框架！回溯法:求解全排列问题的框架简单全排列问题：对于集合

S={1，2，3…，n}

，求它的n个元素的全排列。多叉树的深度优先遍历框架是一种好的不变框架！对四个问题的回答：1、多叉树表示可能解空间。2、DFS进行搜索。3、回溯即对树的剪枝。4、满足要求即访问到叶子节点。回溯法:求解全排列问题的框架代码voidbacktrack(std::vector<int>&permutation){//如果当前的排列已经包含了所有的元素，那么就找到了一个新的排列if(permutation.size()==m){results.push_back(permutation);return;}//满足条件-4for(size_ti=0;i<nums.size();i++){//多叉树中同一层的兄弟节点-1，2if(visited[i]){continue;}//剪枝：开始搜索此节点的右兄弟，没有则父节点的右兄弟，如此逐级搜索-3visited[i]=true;permutation.push_back(nums[i]);

backtrack(permutation);//继续搜索它的子树，递归地生成剩余元素的所有排列-1，2visited[i]=false;//回溯，撤销前面的选择-3permutation.pop_back();//开始搜索此节点的右兄弟，没有则父节点的右兄弟，如此逐级搜索-3}}//理解并记住这个代码框架与四个问题的对应部分！！回溯法:求解组合问题现实世界的问题中，还有一大类问题，它们的最终解与元素顺序无关，但与是否包含某些元素有关，这类算法问题被称为是组合问题。简单示例：对于集合

S={1，2，3，...，N}，求解集合S的所有可能组合（集合S的所有子集）。依照回溯法框架：构造可能解树、DFS遍历这棵树、回溯剪枝、终止条件？回溯法:求解组合问题依照回溯法框架：构造可能解树、DFS遍历这棵树、回溯、设置终止条件。构造具体问题的可能解树是一个难点，但在代码中这棵树是不存在的！回溯法:求解组合问题的框架代码voiddfs(intindex){

if(index==S.size()){result.push_back(currentSubset);return;}////如果索引等于集合的长度，返回结果//选择不包括当前元素在子集中dfs(index+1);//二叉树空节点的子树//选择包括当前元素在子集中currentSubset.push_back(S[index]);//二叉树实节点的子树dfs(index+1);//回溯：移除最后一个元素，回到它的父节点currentSubset.pop_back();}};//理解并记住这个代码框架代码与四个问题的对应部分！！回溯法:N-皇后问题N-皇后问题，其中需要在棋盘上安排皇后，使得它们互不攻击。这个问题的解决方案涉及到皇后的所有可能排列，并且每种排列都需要通过回溯法来检验是否有效！典型的多叉排列树表示可能解空间。回溯法:0-1背包问题0-1背包问题，它要求在不超过背包最大承重的情况下，从一系列具有不同重量和价值的物品中选择出最优组合。结果与元素的排列顺序无关，典型的组合问题，解空间树是一棵完全二叉树。回溯条件？终止条件？回溯法:物流派送问题已知n个城市的全连通矩阵T，要找出一个最短的可能物流派送路线，使得派送者访问每个城市一次并返回原始城市。排列问题？组合问题？20回溯法:物流派送问题排