算法分析与设计总复习.pptVIP

* * of 158 0-1背包问题 n=3, w=(16,15,15), v=(45,25,25), c=30 (1)定义解空间：X={(0,0,0),(0,0,1),(0,1,0),…,(1,1,0),(1,1,1)} (2)构造解空间树： (1,1,1) A H I D J K E B L M F N O G C 1 0 1 0 1 0 1 0 1 0 1 0 1 0 (1,1,0) (1,0,1) (1,0,0) (0,1,1) (0,1,0) (0,0,1) (0,0,0) * * of 158 n=3, w=(16,15,15), v=(45,25,25), c=30 (3)从A出发按DFS有哪些信誉好的足球投注网站： A H I D J K E B L M F N O G C 1 0 1 0 1 0 1 0 1 0 1 0 1 0 45 50 25 25 0 可行解: (1,0,0) (0,1,1) (0,1,0) (0,0,1) (0,0,0) 杀死结点 解值: 最优解L=(0,1,1), 最优值为 50 * * of 158 4后问题 设有一4*4的棋盘，把4个皇后放在棋盘上， 要求满足下列两个条件： 1）任意两个皇后不在同一行上和同一列上； 2）任意两个皇后不在同一条对角线上； 问有多少种放法？ * * of 158 1 2 3 4 7 5 6 8 10 9 x1=1 x2=2 3 4 2 4 2 3 3 B B B B B 11 12 13 14 15 16 x1=2 B B 1 3 4 1 3 * * of 158 子集和问题 问题 给定由n个不同正数组成的集合W={wi}，和正数M，求W中所有和等于M的子集的集合； 例如n = 6, M = 30, W={10, 13, 5, 18, 12, 15} * * of 158 子集和问题 按照回溯法思想，从状态树的根结点出发，做深度优先有哪些信誉好的足球投注网站； 为便于计算，将W中的正数按从小到大排序； 当在某一状态A下，依次尝试加入和不加入正数wi，若∑A+wiM，则可停止对该结点的有哪些信誉好的足球投注网站；若∑A+ ∑(wi…wn)M，则也可停止对该结点的有哪些信誉好的足球投注网站； * * of 158 0/1背包问题 且 * * of 158 有载重量M＝50的背包，物体重量分别为5, 15, 25, 27,30，物体价值分别为12,30,44,46,50。求最优装入背包的物体及价值。 * * of 158 回溯过程的效率 用回溯法去处理一实例所要生成的结点数，一般是采用在状态空间树中生成一条随机路径的方法估计。 分支限界法 * * of 158 方法概述: 与回溯法的区别 求解目标不同 ： 一般而言，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解； 有哪些信誉好的足球投注网站方法不同： 回溯算法使用深度优先方法有哪些信誉好的足球投注网站，而分枝限界一般用宽度优先或最小耗费方法来有哪些信誉好的足球投注网站； * * of 158 方法概述: 与回溯法的区别 对扩展结点的扩展方式不同： 分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点； 存储空间的要求不同： 相对而言，分枝限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大； * * of 158 方法概述: 示例1 示例1（FIFO队列分枝限界法） 问题： 0-1背包问题:物品数n=3, 重量w=(20,15,15), 价值v=(40,25,25), 背包容量c=30, 试装入最大价值之和的物品? 求解： ①解空间:{(0,0,0), (0,0,1), … , (1,1,1)} ②解空间树: D B H A I E J K F C L M G N O 1 1 1 1 1 1 1 0 0 0 0 0 0 0 * * of 158 方法概述: 示例1 ③BFS有哪些信誉好的足球投注网站（FIFO队列） 扩展结点 活结点 队列(可行结点) 可行解(叶结点) 解值 A B,C BC B D,E(D死结点) CE C F,G EFG E J,K(J死结点) FG