回溯法设计的运用和发展

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

1、算法设计与分析第五讲回溯法教师:屈喜龙8/14/2021基本内容1）了解回溯法的基本思路及回溯法的基本要素2）掌握2~3个用回溯法求解的程序实现方法3）回溯法的优点与缺点总结8/14/2021用计算机求解问题问题空间现实求解过程实际解状态空间对象的定义机器求解过程算法与程序的设计机内解8/14/2021计算机求解的过程在状态空间寻找机内解可以看成是从初始状态出发搜索目标状态(解所在的状态)的过程。状态空间初始状态目标状态搜索搜索的过程可描述为：S0S1…Sn，其中S0为初态，Sn为终态。或者

2、说ψ(S0)且φ(Sn)，这里ψ称为初始条件，φ称为终止条件。8/14/2021求解是状态空间的搜索求解的过程可以描述为对状态空间的搜索S0S11S12…S1k………………Sn1……Sni……Snm其中S0为初始状态，不妨设Sni为终止状态S0Sni于是问题的求解就是通过搜索寻找出一条从初始状态S0到终止状态Sni的路径。8/14/2021几种搜索方法状态空间的搜索实际上是一种树/DAG的搜索，常用的方法有：广度优先的搜索深度优先的搜索启发式的搜索从初始状态开始，逐层地进行搜索。从初始状态开始，逐个分

3、枝地进行搜索。从初始状态开始，每次选择最有可能达到终止状态的结点进行搜索。8/14/2021三种搜索的优劣之处一般来说，三种搜索方法各有优劣之处：广度优先搜索的优点是一定能找到解；缺点是空间复杂性和时间复杂性都大。深度优先搜索的优点是空间复杂性和时间复杂性较小；缺点是不一定能找到解。启发式搜索的是最好优先的搜索，优点是一般来说能较快地找到解，即其时间复杂性更小；缺点是需要设计一个评价函数，并且评价函数的优劣决定了启发式搜索的优劣。8/14/2021三种搜索的不同之处树的三种搜索方法的不同就在于它们对表

4、L使用了不同控制方式：L是一个队列L是一个栈L的元素按照某方式排序广度优先搜索深度优先搜索启发式搜索其中，深度优先搜索就是回溯法。8/14/2021什么是回溯法回溯法实际是穷举算法，按问题某种变化趋势穷举下去，如某状态的变化用完还没有得到最优解，则返回上一种状态继续穷举。回溯法有“通用的解题法”之称，其采用了一种“走不通就掉头”思想作为其控制结构，用它可以求出问题的所有解和任意解。它的应用很广泛，很多算法都用到回溯法，例如，图的深度优先算法，最短路径算法，骑士巡游算法，八皇后问题，N重循环等都用到回溯

5、法，当然其中还使用了其他策略。8/14/2021回溯法的一般形式Try(s){做挑选候选者的准备；while(未成功且还有候选者){挑选下一个候选者next；if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}8/14/2021解空间树(SolutionSpaceTree)start??deadenddeadend??deadenddeadend?success!deadend8/14/202

6、1解空间的组织(TreeOrganizationOfSolutionSpace)任何时候,在构造问题解的时候,都包含做出一系列的决策,如果我们将做出的决策画出来,这个图就象一棵树.建立一个树型结构,使得树叶对应解空间的一个解,而内部节点的一个分支,对应一个决策,这样,便可以将解空间组织为一棵解空间树.回溯法可以很容易地被用来搜索一个集合的所有子集合或是排列..8/14/2021当我们要解决的问题是要求一个使问题最优的n个元素的子集,问题的解空间常可以组织成一棵子集树构造所有的子集n个元素的集合有多少个

7、子集?如果每个Si的大小是k,对每个xi∈Si,共有kn个子集子集树8/14/2021子集树(Subtree)8/14/2021货箱装载问题问题给定n个货箱,货箱i重为wi.船可以装载的货箱总重量为W.货箱装载问题是在不使船翻的前提下装载尽可能多的货箱.解空间假设解可以由向量(x1,x2,…,xn)表示,xi∈{0,1},xi=1表示货箱i被装上船,xi=0表示货箱i不装上船.8/14/2021货箱装载问题可以形式地描述如下:解空间树有2n个叶子的子集树在第j层，节点的展开由xj+1的值决定.8/14

8、/2021Subtree:n=410x2010x1x3x41约束函数令cw(i)表示到第i层的当前重量,记为则约束函数为剪枝若，则停止搜索第i层及其下面的层,否则，继续搜索.8/14/2021对n=4,w=[8,6,2,3],W=12进行回溯1x1101x20x4x3814810[1,0,1,0]C(t)活动节点死节点101310回溯递归版本Backtrack(t)1if(t>n)then2if(cw>bestw)thenbestw←cw3return4