资源描述：
《算法设计与分析-回溯.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章回溯法1学习要点理解回溯法的深度优先搜索策略。掌握用回溯法解题的算法框架（1）递归回溯（2）迭代回溯（3）子集树算法框架（4）排列树算法框架2通过应用范例学习回溯法的设计策略。（1）装载问题；（2）批处理作业调度；（3）符号三角形问题（4）n后问题；（5）0-1背包问题；（6）最大团问题；（7）图的m着色问题（8）旅行售货员问题（9）圆排列问题（10）电路板排列问题（11）连续邮资问题3第五章.回溯法(Backtraiking)1、穷举法应用：有限离散问题总可以用穷举法求得问题的全部0-1背包
2、问题(0-1KnapsackProblem)设有n个物体和一个背包,物体i的重量为wi价值为pi背包的载荷为M,若将物体i(1in,)装入背包,则有价值为pi.目标是找到一个方案,使得能放入背包的物体总价值最高例题若取W=(16,15,15),P=(40,25,25),C=30穷举法求解相当于分别计算每个可能解，再求优解例如取N=3,问题所有可能的解为(解空间):(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)时间复杂
3、性:O(2n)42、穷举法改进对于某些组合难题的较大实例，我们可以用穷举法求解，但穷举法的规模较大，所以我们对它进行改进，提出了回溯法和分支界限法两种算法设计技术。它们每次只构造候选解的一个分量，然后评估这个部分构造解：如果加上剩下的分量也不可能求得一个解，就绝不会生成剩下的分量。他们是以构造一棵解空间树为基础的，树的节点反映了对一个部分解做出的特定选择，如果可以保证，节点子孙所对应的选择不可能得出问题的一个解，两种技术都会立即停止处理这个节点。两种技术的区别在于他们能处理的问题类型不同，分支界限法
4、只能应用于最优问题，而回溯法可以搜索任何问题的所有解和任一解。55.1回溯法基本思想穷举法技术建议我们先生成所有的候选解，然后找出那个具有需要特性的元素1、回溯法主要思想是每次只构造解的一个分量，然后按照鲜明的方法来评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题的约束，我们就接受对下一个分量所作的第一个合法选择。如果无法对下一个分量进行合法的选择，就不对剩下的任何分量再做任何选择了。在这种情况下，该算法进行回溯，把部分构造解的最后一个分量替换为它的下一个选择。2、解空间树：通过对
5、所做的选择结构构造一棵解空间树，树根代表了在查找解之前的初始状态。树的第一层节点代表对解的第一个分量所做的选择，第二层节点代表了对解的第二个分量所做的选择，以此类推。如果一个部分构造解（子树）仍然有可能导致一个完整解，我们说这个部分解在树中的相应节点是有希望的。否则说是没希望的。叶子要么代表没希望的，要么代表算法找到完整解6生成问题状态的基本方法扩展结点:一个正在产生儿子的结点称为扩展结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点死结点:一个所有儿子已经产生的结点称做死结点深度优先
6、的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法7若取W=(16,15,15)
7、,P=(40,25,25),C=30例如取N=3,问题所有可能的解为(解空间):(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)0-1背包问题解空间树可表示为一棵3层的完全正则二叉树时间复杂性:O(2n)求解过程相当于在树中搜索满足条件的叶结点.83、搜索策略回溯法在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时，先判断该节点是否包含问题的解。如果肯定不包含，则跳过对以该节点为根
8、的子树的搜索，逐层向其祖先节点回溯否则，进入该子树，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。回溯法求解问题的一个解时，只要搜索到问题的一个解就可以结束。这种以深度优先方式系统搜索问题解的算法称为回溯法。9回溯法举例：若取W=(16,15,15),P=(40,25,25),C=3010回溯法举例：[旅行商问题]在这个问题中，给出一个n顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。任何一
