《算法设计与分析》-回溯

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

1、回溯算法单击增加标题内容对于许多问题，当需要找出问题的所有解或者找出满足某些约束条件的（最优）解时，往往要使用回溯法。回溯算法应用领域圆排列问题N后问题0-1背包电路板排版问题回溯法有“通用的解题法”之称。5.1回溯法的基本思想5.2回溯法的算法框架5.3n后问题5.4圆排列问题5.5电路板排版问题回溯法（backtracking）是一种系统地搜索问题解的方法。为实现回溯，首先需要定义一个解空间（solutionspace），然后以易于搜索的方式组织解空间，最后用深度优先的方法搜索解空间，获得问题的解。说话的方式简单点：从一条路往前走，能进则进，不能进则退回来，换一条路再试。3为了避免不

2、必要的搜索，算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解4如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯1通常将问题的解空间组织成树或图的形式，使得回溯法能方便地搜索整个解空间2在问题的解空间树中，按深度优先策略（或先序遍历，根-左-右顺序），从根结点出发搜索解空间树5否则，进入该子树，继续按深度优先策略搜索搜索方式内注意：这棵解空间树不是遍历前预先建立的，而是隐含在遍历过程中。容定义一个解空间，它包含问题的解用易于搜索的方式组织解空间深度优先搜索解空间，获得问题的解。Ps：利用限界函数避免移动到不可能产生解的子空间。回溯法解题的一个显著特征是在搜索

3、过程中动态产生问题的解空间。单击增加标题内容解空间设问题的解向量为：X=(x1,x2,…,xn)，xi的取值范围为有穷集Si。把xi的所有可能取值组合，称为问题的解空间。每一个组合是问题的一个可能解。解空间S={0,1}，当n=3时，0/1背包问题的解空间是：{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}当输入规模为n时，有2n种可能的解。0/1背包问题S={1,2,…,n}，当n=3时，S={1,2,3}，货郎担问题的解空间是：{(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,

4、2),(1,2,3),┅,(3,3,1),(3,3,2),(3,3,3)}当输入规模为n时，它有nn种可能的解。考虑到约束方程xi≠xj。因此，货郎担问题的解空间压缩为：{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}当输入规模为n时，它有n!种可能的解。货郎担(旅行商)问题子集树解空间大小:2n排列树解空间大小:n!AddtextinheretooAddtextinhere从n个元素的集合S中找出满足某种性质的子集时确定n个元素满足某种性质的排列时使目标函数取极值（极大或极小）的可行解，一个或少数几个满足约束条件的解，解空间中的一个子集

5、可行解最优解可行解和最优解活结点扩展结点死结点不满足约束条件、目标函数、或其儿子结点已全部搜索完毕的结点、或者叶结点。以死结点作为根的子树，可以在搜索过程中删除所搜索到的结点不是叶结点，且满足约束条件和目标函数的界，其儿子结点还未全部搜索完毕正在搜索其儿子结点的结点，它也是一个活结点当前扩展结点成为死结点时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解，或解空间中已无活结点时终止从其解空间树的根结点开始搜索其解空间。开始时，根结点A是唯一的活结点，也是当前扩展结点。在当前扩展结点A处，可纵深移至B或

6、C。n=3,w=[16,15,15],p=[45,25,25],c=30。在当前扩展结点A处，可纵深移至B或C。选择先移至B，即选取物品w1，此时，A、B均为活结点，B成为当前扩展结点。在B处剩余背包容量是r=30-16=14，获取价值45。从B可纵深移至D或E，先考虑移至D，但现仅有的背包容量容不下物品w2，故移至D导致一个不可行解。而从B移至E不占用背包容量，因而可行。从而我们选择移至E。此时E成为新的扩展结点。此时，A、B和E是活结点。在E处容量仍为14，所得价值仍为45。从E可以移至J和K。移至J会导致一个不可行解，而移向K是可行的，于是移至K，K成为新的扩展结点。由于K是一个叶

7、结点，所以我们得到一个可行解(1,0,0),v=45。由于从K已无法纵深扩展，故K成为一个死结点，所以返回（回溯）至E（离K最近的一个活结点）。而E也没有可扩展的结点，也成为了死结点。接下来，再继续回溯，返回至B处，同样B也成为死结点。再返回A，从A可扩展移至C。从A移至C，r=30,获取价值0。从C可移至F或G，令先移至F，则F成为新的扩展结点，此时有活结点A,C,F。在F有r=30-w2=15,获取价值25。从F向纵深移至L处，