资源描述：
《算法设计与分析6回溯法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6章回溯法回溯法的基本思想回溯法是一种通用性解法，可以将回溯法看作是带优化的穷举法。回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。回溯法的基本步骤1、针对所给问题，定义问题的解空间；2、确定易于搜索的解空间结构
2、（树）；3、以深度优先方式搜索解空间，尽量避免无效搜索；0-1背包问题问题描述：3个物W=[16,15,15],S=[45,25,25],C=301.定义解空间：(0,0,0),(0,0,1)…(1,1,1)，含有个解。2.确定解空间的结构(二叉树)如图3.进行深度优先搜索n=3时的0-1背包问题用完全二叉树表示的解空间旅行商(TSP)问题问题描述：某售货员要到若干城市去推销商品，给出各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。该问题是一个NP完全问题，有(n-1)!条可选路线最优
3、解(1,3,2,4,1)，最优值251234206305410ABCDEFGHIJKLMNOPQ1234344342322423剪枝函数回溯法：在解空间树中按深度优先策略从根节点出发搜索解空间树剪枝函数：1.用约束函数剪去不满足的子树2.用限界函数剪去肯定得不到最优解的子树解空间树的两种常用结构1.子集树：当所给问题是从n个元素的集合s中找到满足某种性质的子树集时相应的解空间树，如0-1背包问题。2.排列树：当所给问题是确定n个元素是否满足某个性质的排列时相应的解空间树成为排列树，如TSP问题。0-1背包问题的具体求解过程问题描述：
4、n个物品，第i个物品的体积为Si，价值为Wi，背包容量为C。变量Xi表示物体i放入背包的情况，0表示不放，1表示放。1.解空间，2.解空间结构树：高度为n+1的完全二叉树，结点总数为，左孩子为1，右孩子为0.0-1背包问题的具体求解过程求解过程：1.初始化：目标函数置为0，将物品按价值体积比的非增顺序排序2.搜索：从根节点出发，尽量沿左孩子结点前进，当不能继续沿左孩子前进时，得到问题的一部分解，把搜索转到右子树。3.估计由部分解所能得到的最大价值：如果估计价值高于上界，继续向下搜索，直到找到可行解保存可行解，并用可行解得到的目标函数
5、的值更新目标函数的上界，向上回溯，寻找其他可行解。若估计值小于目标函数的上界，则丢弃当前的部分解，向上回溯。由部分解估计目标函数值最大值的方法1.假定当前部分解为，并且满足2.将得到新的部分解，由这个部分解继续向下搜索直到满足3.能够找到得最大价值不会超过由部分解估计目标函数值最大值的方法4.回溯：当前估计值小于上界时向上回溯，若当前结点是左孩子，则转向搜索右孩子；若当前结点是右孩子，则继续向上回溯，直到左孩子为止。然后转到相应的左孩子结点，重复（2），（3）实例1：0-1背包问题问题描述：C=50，S=(15,5,25,27,30
6、)W=(30,12,44,46,50)1.令Wup=0,将物体的序号按价值体积比排序结果是（2，1，3，4，5）2.生成部分解(1,1,1,0)，估计当前部分解的价值为Weva=94.3，Weva>Wup3.继续向下搜索生成结点6，得到可行解(1,1,1,0,0),得到价值为86，更新Wup=86实例1：0-1背包问题4.回溯：沿右孩子回溯到左孩子4，生成相应右孩子7，得到部分解(1,1,0,1)，此时Weva=935.因为Weva>Wup，继续生成结点8，9，得到可行解(1,1,0,1,0),价值为88，更新Wup=88实例1：0
7、-1背包问题6.回溯到8生成10，得到部分解(1,1,0,0),估计部分解Weva=92>887.继续生成结点11，得到可行解(1,1,0,0,1),更新Wup=928.因为11是左孩子，生成其对应的右孩子结点12，得到另一个可行解(1,1,0,0,0)实例1：0-1背包问题6.回溯，沿结点12向上回溯到结点3生成结点13，得到部分解(1,0),此时Weva=90<92,7.向上继续回溯生成结点14，得到部分解(0),此时得到的Weva=91<92实例2：n皇后问题问题描述：在一个nn的棋盘上，布置n个皇后，使任意皇后之间不能相互攻
8、击（不能同时在同一行，同一列，同一正反对角线上）1.解空间2.树回溯法的效率分析产生一个结点的时间结点的个数判断约束满足与否的时间判断上界满足与否的时间回溯法的效率分析满足约束的结点个数：1.剪枝函数与生成结点总数之间的一个折中2.生
