《状态压缩DP入门》PPT课件.ppt_第1页
《状态压缩DP入门》PPT课件.ppt_第2页
《状态压缩DP入门》PPT课件.ppt_第3页
《状态压缩DP入门》PPT课件.ppt_第4页
《状态压缩DP入门》PPT课件.ppt_第5页
已阅读5页，还剩3页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

经典入门,状态压缩动态规划,状态压缩动态规划,状态压缩动态规划：动态规划的状态有时候比较恶心，不容易表示出来，需要用一些编码技术，把状态压缩的用简单的方式表示出来。典型方式：当需要表示一个集合有哪些元素时，往往利用2进制用一个整数表示。,经典问题：TSP,一个n个点的带权的有向图，求一条路径，使得这条路经过每个点恰好一次，并且路径上边的权值和最小（或者最大）。或者求一条具有这样性质的回路，这是经典的TSP问题。n=16(重要条件,状态压缩的标志)今天讲第一个问题的状态压缩动态规划的解法，第2个问题大同小异。,TSP,如何表示一个点集：由于只有16个点，所以我们用一个整数表示一个点集：例如：50000000000000101；（2进制表示）它的第0位和第2位是1，就表示这个点集里有2个点，分别是点0和点2。310000000000011111；（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=jn)；技巧：利用2进制，使得一个整数表示一个点集，这样集合的操
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论