经典树型DP状态压缩DP入门.ppt

经典入门,树型动态规划和状态压缩动态规划,百度文库不能允许上传同样的,所以我在这里改改 财富值为零,请随便下载,树型动态规划,什么是树型动态规划： 树本身就是一个递归的结构，所以在树上进行动态规划或者递推是在合适不过的事情。 必要条件：子树之间不可以相互干扰，如果本来是相互干扰的，那么我们必须添加变量使得他们不相互干扰。,Party at Hali-Bula,题目大意： n个人形成一个关系树，每个节点代表一个人，节点的根表示这个人的唯一的直接上司，只有根没有上司。要求选取一部分人出来，使得每2个人之间不能有直接的上下级的关系，求最多能选多少个人出来，并且求出获得最大人数的选人方案是否唯一。 这是一个经典的树型动态规划。,Party at Hali-Bula,简单的染色统计是不正确的,Party at Hali-Bula,人之间的关系形成树型结构 DP, 用dpi0表示不选择i点时，i点及其子树能选出的最多人数，dpi1表示选择i点时，i点及其子树的最多人数。,Party at Hali-Bula,状态转移方程: 对于叶子节点 dpk0 = 0, dpk1 = 1 对于非叶子节点i, dpi0 = max(dpj0, dpj1) (j是i的儿子) dpi1 = 1 + dpj0 (j是i的儿子) 最多人数即为max(dp00, dp01) 如何判断最优解是否唯一?,Party at Hali-Bula,新加一个状态dupij，表示相应的dpij是否是唯一方案。 对于叶子结点, dupk0 = dupk1 = 1. 对于非叶子结点, 对于i的任一儿子j，若(dpj0 dpj1 且 dupj0 = 0) 或 (dpj0 dpj1 且 dupj1 = 0) 或 (dpj0 = dpj1)，则dupi0 = 0 对于i的任一儿子j有dupj0 = 0, 则dupi1 = 0,Strategic game,题目大意： 一城堡的所有的道路形成一个n个节点的树，如果在一个节点上放上一个士兵，那么和这个节点相连的边就会被看守住，问把所有边看守住最少需要放多少士兵。 典型的树型动态规划,Strategic game,dproot i 表示以i为根的子树，在i上放置一个士兵，看守住整个子树需要多少士兵。 all i 表示看守住整个以i为根的子树需要多少士兵。,Strategic game,状态转移方程： 叶子节点：dprootk =1； allk = 0； 非叶子节点： dprooti = 1 + allj(j是i的儿子)； alli = min( dprooti, dprootj(j是i的儿子) )； 这个题目还是比较简单的，如果把题目中看守边变成看守相邻的点呢？留给你来思考_,状态压缩动态规划,状态压缩动态规划： 动态规划的状态有时候比较恶心，不容易表示出来，需要用一些编码技术，把状态压缩的用简单的方式表示出来。 典型方式：当需要表示一个集合有哪些元素时，往往利用2进制用一个整数表示。,经典问题：TSP,一个n个点的带权的有向图，求一条路径，使得这条路经过每个点恰好一次，并且路径上边的权值和最小（或者最大）。 或者求一条具有这样性质的回路，这是经典的TSP问题。 n = 16 (重要条件,状态压缩的标志) 今天讲第一个问题的状态压缩动态规划的解法，第2个问题大同小异。,TSP,如何表示一个点集： 由于只有16个点，所以我们用一个整数表示一个点集： 例如： 5 0000000000000101；（2进制表示） 它的第0位和第2位是1，就表示这个点集里有2个点，分别是点0和点2。 31 0000000000011111； （2进制表示） 表示这个点集里有5个点，分别是0，1，2，4，5；,TSP,所以一个整数i就表示了一个点集； 整数i可以表示一个点集，也可以表示是第i个点。 状态表示：dpij表示经过点集i中的点恰好一次，不经过其它的点，并且以j点为终点的路径,权值和的最小值，如果这个状态不存在，就是无穷大。,TSP,状态转移： 单点集：状态存在dpij = 0；否则无穷大。非单点集： 状态存在 dpij = min(dpks + wsj) k表示i集合中去掉了j点的集合，s遍历集合k中的点并且dpks状态存在， 点s到点j有边存在，wsj表示边的权值。 状态不存在 dpij为无穷大。,TSP,最后的结果是： min( dp( 1n ) 1j ) ( 0 = j n )； 技巧：利用2进制，使得一个整数表示一个点集，这样集合的操作可以用位运算来实现。例如从集合i中去掉点j： k = i & ( ( 1 j ) ) 或者 k = i - ( 1 j ),习题,树型动态规划 nkoj 1791 Party at Hali-Bula nkoj 1678 Strategic game nkoj 1794 Bribing FIPA （需要2重dp） poj 1946 Rebuilding Roads （需要2重dp） 状态压缩动态规划 nkoj 1068 Islands and Bridges poj 3229 The Best Travel Design poj 1038 Bugs Integrated, Inc.,T