状态压缩DP入门.ppt

《状态压缩DP入门.ppt》由会员分享，可在线阅读，更多相关《状态压缩DP入门.ppt（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、经典入门经典入门状态压缩动态规划状态压缩动态规划状态压缩动态规划状态压缩动态规划n状态压缩动态规划：动态规划的状态有时候比较恶心，不容易表示出来，需要用一些编码技术，把状态压缩的用简单的方式表示出来。n典型方式：当需要表示一个集合有哪些元素时，往往利用2进制用一个整数表示。经典问题：经典问题：TSPn一个n个点的带权的有向图，求一条路径，使得这条路经过每个点恰好一次，并且路径上边的权值和最小（或者最大）。n或者求一条具有这样性质的回路，这是经典的TSP问题。nn=16(重要条件,状态压缩的标志)n今天讲第一个问题的状态压缩动态规划的解法，第2个问题大同小异。TSPn如何表示一个点集：n由于只有

2、16个点，所以我们用一个整数表示一个点集：n例如：5 0000000000000101；（2进制表示）它的第0位和第2位是1，就表示这个点集里有2个点，分别是点0和点2。31 0000000000011111；（2进制表示）表示这个点集里有5个点，分别是0，1，2，4，5；TSPn所以一个整数i就表示了一个点集；n整数i可以表示一个点集，也可以表示是第i个点。n状态表示：dpij表示经过点集i中的点恰好一次，不经过其它的点，并且以j点为终点的路径,权值和的最小值，如果这个状态不存在，就是无穷大。TSPn状态转移：单点集：状态存在dpij=0；否则无穷大。非单点集：状态存在 dpij=min(dpks+wsj)k表示i集合中去掉了j点的集合，s遍历集合k中的点并且dpks状态存在，点s到点j有边存在，wsj表示边的权值。状态不存在 dpij为无穷大。TSPn最后的结果是：min(dp(1n)1j)(0=j n)；n技巧：利用2进制，使得一个整数表示一个点集，这样集合的操作可以用位运算来实现。例如从集合i中去掉点j：k=i&(1 j)或者 k=i-(1 j)n遍历点集i中都包含哪些点nfor（j=0；(1j)=i;j+）npif（(1j)&i)!=0）n点集i就包含点jnn把点j加入点集ini=(i|（1j）);