算法设计与分析lecture7

《算法设计与分析lecture7》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、回溯（backtrack）回溯算法的基本思想和适用条件回溯算法的设计步骤估计回溯算法的效率改进回溯算法的途径分支估界应用实例1基本思想和适用条件实例基本思想搜索问题、搜索空间、搜索策略判定条件、结点状态、存储结构必要条件2实例例1四后问题解表示成一个4维向量，（放置列号）1234搜索空间：4叉树3例20-1背包问题：V={12,11,9,8},W={8,6,4,3},B=13结点：向量（子集的部分特征向量）123k搜索空间：子集树，2n片树叶<0,1,1,1>可行解：x=0,x=1,x=1,x=1.重量：13,价值：281234<1,

2、0,1,0>可行解：x=1,x=0,x=1,x=0.重量：12，价值：2112344例3巡回售货员问题：结点：向量（部分巡回路线）12k搜索空间：排列树<1,2,4,3>对应于巡回路线：1→2→4→3→1长度：5+2+7+9=235基本思想适用问题：求解搜索问题搜索空间：一棵树每个结点对应了部分解向量树叶对应了可行解搜索过程：采用系统的方法隐含遍历搜索树搜索策略：深度优先，宽度优先，函数优先，宽深结合等6基本思想(续)结点分支判定条件：满足约束条件---分支扩张解向量不满足约束条件，回溯到该结点的父结点结点状态：动态生成结点状态：白结点（尚未访问）；灰结点

3、（正在访问该结点为根的子树）黑结点（该结点为根的子树遍历完成）存储：当前路径7必要条件--多米诺性质设P(x,x,…,x)为真表示向量中i个12i12i皇后放置在彼此不能攻击的位置P(x1,x2,...,xk+1)→P(x1,x2,...,xk)0

4、索问题的解向量和每个分量的取值范围解向量为12nx的可能取值的集合为X,i=1,2,…,n.iix,x,…,x确定以后x的取值集合为S,S⊆X12k-1kkkk确定结点儿子的排列规则判断是否满足多米诺性质搜索策略----深度优先确定每个结点能够分支的约束条件确定存储搜索路径的数据结构9递归回溯算法ReBack(k)1.ifk>nthen是解;12n2.elsewhileS≠∅dok3.x←S中最小值kk4.S←S–{x}kkk5.计算Sk+16.ReBack(k+1)算法ReBacktrack(n)1.fork←1ton计算Xk2.ReB

5、ack(1)10迭代回溯迭代算法Backtrack1.对于i=1,2,…,n确定Xi2.k←13.计算Sk4.whileS≠∅dok5.x←S中最小值;S←S–{x}kkkkk6.ifk是解12n9.ifk>1thenk←k-1；goto411例5装载问题二问题：n个集装箱装上2艘载重分别为c和c的轮船，12w为集装箱i的重量，且in∑wi≤c1+c2i=1是否存在一种合理的装载方案将n个集装箱装上轮船？如果有，给出一种方案.12求解思路命题：如果装载问题有解，则存在一个使得第一条船装载量与c的差达到最小的解

6、.1解题思路：1．确定使第一船装载量W与c的差达到最小的11装载方案；12n2．若集装箱总重−W≤c,则回答yes;否则回答No.120-1背包问题的限定情况v=wii13算法设计将w,w,…,w按照递降排序.12n解向量,x∈{1,0}12ni满足多米诺条件：kk+1∑wx>c⇒∑wx>cii1ii1i=1i=1搜索策略：深度优先在结点的约束条件：12kk∑wx≤cii1i=114算法算法Loading2(W)1.Sort(W)2.B←∞;best←∞//B空隙,best目前最优解空隙，3.i←1//c记录分支4.wh

7、ilei≤ndo5.if装入i后重量不超过c16.then修改B;x[i]←1;c[i]←1;i←i+1//装入i7.elsec[i]←2;x[i]←0;i←i+1//不装i8.ifB13.doi←i−14.ifi=1andc[i]=2thenreturn最优解5.c[i]←2;x[i]←0;i←i+116实例W=<90,80,40,30,20,12