教学讲稿第5章 回溯法

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

1、第5章回溯法上海大学计算机学院学习要点与要求掌握与理解回溯法的DFS搜索策略与方法（1）掌握递归回溯（2）理解迭代回溯编程技巧掌握用回溯法解题的算法框架，了解搜索过程（1）子集树算法框架（2）排列树算法框架通过学习典型范例，掌握回溯法的设计策略（1）装载问题（2）批处理作业调度（3）n后问题（4）0-1背包问题（5）最大团问题（6）图的m着色问题（7）旅行售货员问题n皇后问题国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子，问在n×n格的棋盘上如何摆上n个皇后而使她们都不能相互吃掉？引言穷举法：n=4时，有n！=24中情况N皇后搜索过程与多叉树0x4=41

2、2271810513315911614416x2=2x2=4x2=3x3=3x3=4x3=2x3=4x3=2x3=3x4=3x4=4x4=2x4=3x4=2x1=1x1=2x1=3x1=41234x1x2x3x4迷宫问题演示5.1回溯法的算法框架问题的解空间（1）1.解向量：问题的解用向量表示(x1,x2,…,xk)其中kn,n为问题的规模。2.约束条件1）显式约束：对分量xi的取值的明显限定。2）隐式约束：为满足问题的解而对不同分量之间施加的约束。3.解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。问题的解空间（2）

3、4、状态空间树用于形象描述解空间的树。5、目标函数与最优解1.目标函数：衡量问题解的“优劣”标准。2.最优解：使目标函数取极（大/小）值的解。n=3时的0-1背包问题用完全二叉树表示的解空间搜索状态空间树的两种策略1.以深度优先方式系统搜索问题的解------回溯法2.以广度优先方式搜索问题的解------分支-限界法几种搜索过程中涉及的结点：扩展结点：一个正在产生儿子的结点称为扩展结点活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点死结点：一个所有儿子已经产生的结点称做死结点回溯法基本方法：利用限界函数来避免生成那些实际上不可能产生所需解的活结点，

4、以减少问题的计算量，避免无效搜索。限界函数：用于剪枝(1)约束函数：某个满足条件的表达式或关系式。不真时用于在扩展结点处剪去不满足约束的子树；(2)限界函数：某个函数表达式或关系式。不真时，用于剪去得不到最优解的子树。回溯法：具有限界函数的深度优先搜索方法回溯法的基本思想以深度优先方式搜索解空间。开始时，根结点为活结点，也是当前的扩展结点。对扩展结点，寻找儿子结点：如找到新结点，新结点成为活结点并成为扩展结点。转3；如找不到新结点，当前结点成为死结点，并回退到最近的一个活结点，使它成为扩展结点。转3；搜索继续进行，直到找到所求的解或解空间中已无活结点时为止。n=

5、3时的0-1背包问题：c=30,w=[16,15,15],v=[45,25,25]搜索过程举例--0-1背包问题搜索过程举例—旅行商问题TSPG=(V，E)，

6、V

7、=n1234301020654总路径数：对称情况：(n-1)!/2非对称情况：(n-1)!回溯法解题步骤(1)针对所给问题，定义问题的解空间；(2)确定合适的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索，直到找到所求的解或解空间中已无活结点时为止。回溯法形式描述-递归算法voidBACKTRACK(intt){//n为递归深度,t为当前深度if（t>n）返回;els

8、ewhile(存在合适的xt){if(x1,…,xt)是解输出解x1,…,xt；BACKTRACK(t+1);}}另一种方式for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);若（xt满足约束和限界条件）BACKTRACK(t+1)}回溯法形式描述-非递归算法迭代回溯voidBACKTRACK(intn){intt=1;while(t>0){if(有xt，满足约束C(x1,…,xt)&&限界Bound(x1,…,xt)){if((x1,…,xt)是问题的一个“解”)则输出解(x1,…,xt)；elset=t+1//“深入”一步}el

9、set=t-1;//“回退”一步}}if(f(n,t)<=g(n,t))for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(Constraint(t)&&Bound(t)){if(solution(t))output(x);elset++;}}子集树与排列树注意：2n<n)output(x);els

10、efor(inti=0;