欢迎来到天天文库
浏览记录
ID:49198332
大小:527.00 KB
页数:8页
时间:2020-02-01
《状态压缩DP入门.ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、经典入门状态压缩动态规划状态压缩动态规划状态压缩动态规划:动态规划的状态有时候比较恶心,不容易表示出来,需要用一些编码技术,把状态压缩的用简单的方式表示出来。典型方式:当需要表示一个集合有哪些元素时,往往利用2进制用一个整数表示。经典问题:TSP一个n个点的带权的有向图,求一条路径,使得这条路经过每个点恰好一次,并且路径上边的权值和最小(或者最大)。或者求一条具有这样性质的回路,这是经典的TSP问题。n<=16(重要条件,状态压缩的标志)今天讲第一个问题的状态压缩动态规划的解法,第2个问题大同小异。TSP如何表示一个点集:由于只有16个点,所以我们用一个整
2、数表示一个点集:例如:5=0000000000000101;(2进制表示)它的第0位和第2位是1,就表示这个点集里有2个点,分别是点0和点2。31=0000000000011111;(2进制表示)表示这个点集里有5个点,分别是0,1,2,4,5;TSP所以一个整数i就表示了一个点集;整数i可以表示一个点集,也可以表示是第i个点。状态表示:dp[i][j]表示经过点集i中的点恰好一次,不经过其它的点,并且以j点为终点的路径,权值和的最小值,如果这个状态不存在,就是无穷大。TSP状态转移:单点集:状态存在dp[i][j]=0;否则无穷大。非单点集:状态存在dp
3、[i][j]=min(dp[k][s]+w[s][j])k表示i集合中去掉了j点的集合,s遍历集合k中的点并且dp[k][s]状态存在,点s到点j有边存在,w[s][j]表示边的权值。状态不存在dp[i][j]为无穷大。TSP最后的结果是:min(dp[(1<4、包含点j}把点j加入点集ii=(i5、(1<
4、包含点j}把点j加入点集ii=(i
5、(1<
此文档下载收益归作者所有