回溯算法的思想课件.ppt

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

1、第五章回溯法5.1回溯算法基本思想回溯法是一种通用的解决问题的办法，本质上就是一种穷举，并且是一种避免重复的穷举。所有回溯算法与走迷宫具有相同的本质。1迷宫问题回溯：往回退，追根溯源。求解的目标:确定每一个十字路口的选择，最后走出迷宫。2问题的解空间树问题的解向量：回溯算法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。解空间树：由解元素x1,x2…xn取不同值所构成组合(或排列)序列，迷宫中xi表示第i个十字路口做出的选择。Eg.n=3时的0-1背包问题解空间树为左图所示二叉树显式约束：对分量xi的取值限定。隐式约束：为满足问题的解对不同分量之间施加的约束。x1x

2、2x33回溯算法的本质：确定问题的解空间树后，深度优先遍历此空间树。但是往往问题的解空间树是无法完全存储的（eg），所以遍历有它的特点。通常情况下的处理策略是：一边生成解空间树，一边遍历。4解空间树的生成方法深度优先的解空间树生成法：从根结点R开始（R是第一个扩展结点），生成它的一个儿子结点C(即确定了x1)；然后以C作为新的扩展结点，在完成了以C为根的子树的穷尽搜索之后(即递归，是在x1保持不变的情况下，分别求解x2…xn的所有可能组合)，将R重新变成扩展结点（即回溯到R结点处），继续生成R的下一个儿子（即让x1取另外一个值，直至没有值可取即会回退到R的父结点，此时以R为根的树遍历结

3、束）。扩展结点：一个准备生成其儿子的结点5回溯算法正是按深度优先解空间树生成法，结点生成到哪里，就遍历到哪里。此过程可以表达成如下递归形式和非递归形式。递归形式的表达：BackTrack(k)//当前已经具备k-1个解元素，准备求Xk{if(x1,x2,…,xk-1)是问题的解输出；else{计算第k个解元素的候选集合Sk;//Sk相当于第k个十字路口的选择while(Sk!=空){xk=Sk中的一个元素；//Xk已求出Sk=Sk-{xk}；BackTrack(k+1);//递归进一步求Xk+1}}//while结束，即表示第k个路口已穷举完}6非递归形式的表达：BackTrack(X

4、){计算解向量X的第一个元素x1的候选集合S1；k=1;//S1即第一个十字路口处没有走过的支路While(k>0){whileSk!=空{Xk=Sk中的一个元素；//第k个路口已确定Sk=Sk-{Xk};//已走过的支路不会重复走if(X=(x1,x2,…xk)是问题的解)输出；k++;计算候选集合Sk;}k--;//回溯，即回退到第k-1个十字路口}}7例如：输出1~n的全排列，递归表达如下（pailie0.c）voidf(intk)//已经具备X1~Xk-1,函数目的：求解X[k]{inti;if(k-1==n)//找到问题的一个解{cout<

5、unt<<":";for(i=1;i

6、1~Xk-1不变的情况//下，看看除了i以外Xk还有没有其它可用的值此处有多种写法，写成限界函数(xianjie(k,i),判断Xk能否取i)最好8非递归的算法过程如下voidf1(void){k=1;from=1;I=1;while(k>0){for(;i

7、量X的过程。2）把限界函数分离出来，便于程序的编写和调试，每一个问题的约束条件都不一样，但是他们回溯的思路都是一样的。所以这样处理类似于模块化。关键点：限界函数的设计，限界函数完全取决于问题的显式约束和隐式约束。105.2解空间树的两种形态时间复杂度：Θ(an)a为被划分集合个数voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++)if(xianjie(t,i)){x[t]=i