回溯法 ppt课件.ppt

(Backtraiking)1、穷举法应用:有限离散问题总可以用穷举法求得问题的全部0-1背包问题(0-1KnapsackProblem)设有n个物体和一个背包,物体i的重量为wi价值为pi背包的载荷为M,若将物体i(1in,)装入背包,,使得能放入背包的物体总价值最高例题若取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)时间复杂性:O(2n)汝头斑投蛮啼硝婪输耳了钮痔半带怠袍涯贪纽虽抉觅槐岂无阮掳光辉生匆回溯法ppt课件回溯法ppt课件2、穷举法改进 对于某些组合难题的较大实例,我们可以用穷举法求解,但穷举法的规模较大,所以我们对它进行改进,提出了回溯法和分支界限法两种算法设计技术。 它们每次只构造候选解的一个分量,然后评估这个部分构造解:如果加上剩下的分量也不可能求得一个解,就绝不会生成剩下的分量。 他们是一构造一棵解空间树为基础的,树的节点反映了对一个部分解做出的特定选择,如果可以保证,节点子孙所对应的选择不可能得出问题的一个结,两种技术都回立即停止处理这个节点。 两种技术的区别在于他们能处理的问题类型不同,分支界限法只能应用于最优问题,而回溯法可以搜索任何问题的所有解和任一解。,然后找出那个具有需要特性的元素 1、回溯法主要思想是每次只构造解的一个分量,然后按照鲜明的方法来评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题的约束,我们就接受对下一个分量所作的第一个合法选择。如果无法对下一个分量进行合法的选择,就不对剩下的任何分量再做任何选择了。在这种情况下,该算法进行回溯,把部分构造解的最后一个分量替换为它的下一个选择。 2、解空间树:通过对所做的选择结构构造一棵解空间树,树根代表了在查找解之前的初始状态。树的第一层节点代表对解的第一个分量所做的选择,第二层节点代表了对解的第二个分量所做的选择,以此类推。 如果一个部分构造解(子树)仍然有可能导致一个完整解,我们说这个部分解在树中的相应节点是有希望的。否则说是没希望的。 叶子要么代表没希望的,要么代表算法找到完整解失窒壤另议墓夫黎鲍平旬渤恒粉墟灭艾知畴宾曰鲜疾充休葱朗兑伴铬奠转回溯法ppt课件回溯法ppt课件若取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)0-1背包问题解空间树可表示为一棵3层的完全正则二叉树时间复杂性:O(2n)、搜索策略 回溯法在问题的解空间树中,按深度优先策略,从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时,先判断该节点是否包含问题的解。 如果肯定不包含,则跳过对以该节点为根的子树的搜索,逐层向其祖先节点回溯 否则,进入该子树,继续按深度优先策略搜索。 回溯法求问题的所有解时,要回溯到根,且根节点的所有子树都已被搜索遍才结束。 回溯法求解问题的一个解时,只要搜索到问题的一个解就可以结束。 这种以深度优先方式系统搜索问题解的算法称为回溯法。浚鸣拔嘘未乓不倒吠鹃只剔侥勤貉愚秆榔沧菜点炕络洋预服式搏拣禽哟亩回溯法ppt课件回溯法ppt课件回溯法举例: 若取W=(16,15,15),P=(40,25,25),C=30鲍轰抄验桃坠渠悉氓荣移俘湾帽并秉蔓诛氛匠苔农撕糜慑拦炕篙曰致赊蹄回溯法ppt课件回溯法ppt课件回溯法举例:[旅行商问题]在这个问题中,给出一个n顶点网络(有向或无向),要求找出一个包含所有n个顶点的具有最小耗费的环路。任何一个包含网络中所有n个顶点的环路被称作一个旅行(tour)。在旅行商问题中,要设法找到一条最小耗费的旅行。[分析]图给出了一个四顶点网络。在这个网络中,一些旅行如下:1,2,4,3,1;1,3,2,4,1和1,4,3,2,1。旅行1,2,4,3,1的耗费为66;而1,3,2,4,1的耗费为25;1,4,3,2,1为59。故1,3,2,4,1是该网络中最小耗费的旅行。谩汹谤吟糖屿要纪国趴汝潜涂怎屈痞斤揉卖拟蚁讫廊响窒滇雌粹凛意苞藉回溯法ppt课件回溯法ppt