第7章 回溯法ppt课件.ppt

《第7章 回溯法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章回溯法**《算法分析与设计》胡伟平**主要内容§7.2n皇后问题§7.1回溯法的思想方法**《算法分析与设计》胡伟平**§7.3图的着色问题§7.4哈密尔顿回路问题§7.50/1背包问题§7.6回溯法的效率分析回溯法和分枝限界法都是对问题实例进行学习，有组织地检查和处理问题实例的解空间，并在此基础上对解空间进行规约和修剪的一种方法。§7.1回溯法的思想方法**《算法分析与设计》胡伟平**这两种方法操作的都是解空间，那么解空间指的是什么呢？简而言之，解空间就是所有的可能解所组成的集合。例如：0/1背包问题，如果有n个物品的话，设定xi为每个物品装入背包的量，那么将这些xi合并起来构成一个向

2、量：解空间与状态空间树**《算法分析与设计》胡伟平**X就被称为这个问题的解向量。X所有可以取的组成的集合就称为解空间。（0，0，…，0）～（1，1，…，1）解空间大小为2n又例：货郎担问题，如果有n个城市的话，设定xi为第i次走的城市，那么将这些xi合并起来构成一个向量：**《算法分析与设计》胡伟平**因为不能重复走同一城市，所以解向量X中的分量不能相同。解空间大小为n!。解空间与状态空间树例如：4个城市的货郎担问题。**《算法分析与设计》胡伟平**通常情况下使用树来表示解空间解空间与状态空间树**《算法分析与设计》胡伟平**满足约束条件的解称为问题的可行解，很显然，可行解的集合是解空间的一

3、个子集。解空间与状态空间树满足约束条件的并且使得目标函数最大或者最小的解称为问题的最优解，最优解的集合又是可行解集合的一个子集。通过观察知道，可行解或者最优解都是由状态空间树中从根结点出发到某个叶子结点的路径上的标号组成的。**《算法分析与设计》胡伟平**约束条件根据具体情况分为两种：解空间与状态空间树显式条件：对解向量的每一个分量的取值范围的限定，也叫显约束。比如八皇后问题中，每个皇后只能取1～8是显式条件，而每两个之间不能在横竖斜线上是隐式条件。隐式条件：对解向量的分量之间的取值的限定，也叫隐约束。**《算法分析与设计》胡伟平**为了寻找所有最优解，最笨的方法是对整个解空间进行穷举搜索，但

4、是这种方法非常费时。回溯法的动态搜索因为最优解必须满足约束条件且使得目标函数最大或最小，于是我们可以考虑，只搜索部分解空间，将很明显不满足条件的分枝去掉，这样使得搜索的空间减少很多。回溯法和分枝限界法都是采用这种思想来减少搜索空间的，只不过它们去掉分枝的方法不同而已。**《算法分析与设计》胡伟平**回溯法是按照深度优先遍历来进行搜索的。l-结点：非叶子结点，并且满足约束条件和目标函数，同时，其所有子结点还没搜索完。e-结点：当前正在搜索其子结点的结点。d-结点：叶子结点，或者不满足约束条件的结点，或者不满足目标函数的结点，或者是所有子结点都搜索完的结点。回溯法的动态搜索**《算法分析与设计》胡

5、伟平**回溯法搜索过程：从根结点开始搜索，当搜索到l-结点时，将它变成e-结点，继续向下搜索它的子结点；当搜索到d-结点，但是还未得到最终解时，就向上上溯到它的双亲结点，如果这个结点还是e-结点，那么就搜索它的下一个子结点；如果这个结点的所有子结点已经搜索完，那么该结点变为d-结点，并且沿着这个双亲结点向上，回溯到它的祖父结点。直到找到最终解或者根结点变成d-结点。回溯法的动态搜索**《算法分析与设计》胡伟平**例：以下是4个城市之间的费用矩阵，求最短路径回溯法的动态搜索**《算法分析与设计》胡伟平**回溯法的动态搜索1.voidbacktrack()2.{初始化；3.while(i>=0){

6、4.while(k[i]

7、.voidback_rec(inti,BOOL&flag)2.{k[i]=0；3.while((k[i]<=m[i])&&!flag){5.x[i]=a(i,k[i]);6.if(constrain(x)&&bound(x))7.if(solution(x)){8.flag=TRUE;break;}9.elseback_rec(i+1,flag);10.elsek[i]++;}12.}13.}**