北京大学屈婉玲算法设计与分析最新课件05.pdf

《北京大学屈婉玲算法设计与分析最新课件05.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章回溯与分支限界5.1回溯算法的基本思想和适用条件5.2回溯算法的设计步骤535.3回溯算法的效率估计和改进途径5.4分支限界5.4.1背包问题5.4.2最大团问题5.4.3货郎问题5445.4.4圆排列问题5.4.5连续邮资问题15.1回溯算法的基本思想和适用条件5115.1.1几个典型例子四后问题0-1背包问题货郎问题（TSP）5.1.2回溯算法的适用条件25.1.1几个典型例子例1n后问题4后问题：解是一个4维向量，（放置列号）1234搜索空间：4叉树<1><4><2,4><241><2,4,1><2413><2,

2、4,1,3>8后问题：解是一个8维向量，12345678搜索空间：8叉树，一个解：<1,3,5,2,4,6,8,7>3例2：0-1背背问包问题题实例：V={12,11,9,8},W={8,6,4,3},B=13结点：向量（子集的部分特征向量）123k搜索空间：子集树，2n片树叶<1><0><1010><1,0,1,0><0111><0,1,1,1><0,1,1,1>可行解：x=0,x=1,x=1,x=1.价值:28，重量:131234<1,0,1,0>可行解：x=1,x=0,x=1,x=

3、0.价值:21，重量:1212344例3：货郎问题为巡回路线12n搜索空间：排列树,(n-1)!片树叶实例：<1>125<1,2><1,4>42974133<1,2,4,3><1,2,4,3>对应于巡回路线：1→2→4→3→1长度：5+2+7+9235+2+7+9=235回溯算法的基本思想(1)适用问题：求解搜索问题和优化问题(2)搜索空间：树，结点对应部分解向量，树叶对应可行解(3)搜索过程：采用系统的方法隐含遍历搜索树(4)搜索策略：深度优先，宽度优先，函数优先，宽深结合等(5)结点分支判定条件：满足约束条件---分支扩

4、张解向量不满足约束条件，回溯到该结点的父结点(6)结点状态：动态生成白结点(尚未访问)；灰结点(正在访问该结点为根的子树);黑结点(该结点为根的子树遍历完成)(7)存储：当前路径65.1.2回溯算法的适用条件设P(x,x,…,x)为真表示向量满足某个性12i12i质(n后问题中i个皇后放置在彼此不能攻击的位置）多米诺性质：P(x,x,...,x)→P(x,x,...,x)0

5、的相应部分1k12k使得左边小于等于10不满足多米诺性质变换：令x=3−x’,335x+4x+x’≤13，1≤x,x≤303,0≤x’≤212312375.2回溯算法的设计步骤(1)定义搜索问题的解向量和每个分量的取值范围解向量为12n确定x的可能取值的集合为X,i=1,2,…,n.ii(2)当x,x,…,x确定以后计算x取值集合S,S⊆X12k-1kkkk(()3)确定结点儿子的排列规则(4)判断是否满足多米诺性质(5)搜索策略----深度优先、宽度优先等(6)确定每个结点分支约束条件(7)确定存储搜索路径的数据结构8回溯

6、溯实算法的递归实现现算法ReBack(k)1if1.ifk>nthen是解12n2.elsewhileS≠∅dok3.x←S中最小值kk4.S←S–{x}kkk5.计算Sk+16R6.ReBBackk((k+1)算法ReBacktrack(n)输入：n输出：所有的解1.fork←1ton计算Xk2.ReBack(1)9回溯算法的迭代实现迭代算法Backtrack输入：n输出：所有的解1.对于i=1,2,…,n确定Xi2.k←13.计算Sk4.whileS≠∅dok5.x←S中最小值;S←S–{x}kkkkk6.if

7、k是解12n9.ifk>1thenk←k-1；goto410例5装载问题n个集装箱装上2艘载重分别为c和c的轮船，w为集装箱i的12i重量，且n∑wi≤c1+c2i=1问是否存在一种合理的装载方案将n个集装箱装上轮船？如果有，给出一种方案.求解思路：令第一船装载量为W，用回溯算法求使W-c达111n到最小的装载方案，如果∑i=1wi−W1≤c2回答Yes,否则回答No.问题满足多米诺性质，搜索策略：深度优先算法算法5.4Loading(W,c),1输入：

8、集装箱重量W=,c是第一条船的载重12n1输出：使船1装载量最大的方案，其中x=0,1,…,n12ni1S(1.Sort(W)/