基于连通性状态压缩的动态规划问题长沙市雅礼中学陈丹琦长沙市雅礼中学陈丹琦Email : skyfish_cdq163.com1引入 状态压缩动态规划状态总数为状态总数为指数级指数级以集合信息为状态以集合信息为状态我我的的论论文文针针对对其其中中的的一一类类问问题题进进行行探探讨讨和和研研究究 状状态态中中需需要要记记录录若若干干个个元元素素之之间间的的连连通通情情况况，称称为为基于连通性状态压缩的动态规划问题2【例】Formula 1 (Ural1519)一个一个 m * n 的棋盘的棋盘有的格子存在障碍有的格子存在障碍求经过所有非障碍格子的哈密顿回路个数求经过所有非障碍格子的哈密顿回路个数m, n123初步分析问题特点：问题特点：数据规模小数据规模小m, n12搜索?O(mn)!)状态压缩!棋盘模型棋盘模型划分阶段：从上到下，从左到右逐格递推划分阶段：从上到下，从左到右逐格递推基本概念：插头，轮廓线基本概念：插头，轮廓线4基本概念插头一个格子某个方向的插头存在一个格子某个方向的插头存在表示这个格子在这个方向与相表示这个格子在这个方向与相邻格子相连邻格子相连轮廓线已决策格子和未决策格已决策格子和未决策格子的分界线子的分界线轮廓线上方与其相连的轮廓线上方与其相连的有有n+1个插头，包括个插头，包括n个个下插头和下插头和1个右插头个右插头5初步分析问题特点：问题特点：数据规模小数据规模小棋盘模型棋盘模型每个插头是否存在每个插头是否存在所有的非障碍格子连通所有的非障碍格子连通插头之间的连通性插头之间的连通性!6确立状态设设 f (i, j, S) 表示转移完表示转移完(i, j) ，轮廓线上从左到轮廓线上从左到右右n+1个插头是否存在以及它们的连通性为个插头是否存在以及它们的连通性为S的方案总数的方案总数如何表示如何表示S?最小表示法12201无插头标记无插头标记0 0，有插头标记一个正整数，有插头标记一个正整数连通的插头标记相同的数字连通的插头标记相同的数字从左到右依次标记从左到右依次标记f (3,2,1,2,2,0,1)7状态转移考虑每个格子的状态考虑每个格子的状态, 根据上一个状态根据上一个状态O(n)扫扫描计算出新的最小表示状态描计算出新的最小表示状态对于对于m = n = 12的无障碍棋盘的极限数据的无障碍棋盘的极限数据, 扩展状扩展状态总数为态总数为1333113 , 问题已经基本解决问题已经基本解决本题为一个棋盘模型的本题为一个棋盘模型的简单回路简单回路问题问题针对问题的特殊性针对问题的特殊性, 是否有更好的方法呢是否有更好的方法呢?8进一步分析每个非障碍格子恰好有每个非障碍格子恰好有2个插头个插头轮廓线以上由若干条互不相交的路径构成轮廓线以上由若干条互不相交的路径构成每条路径的两端对应两个插头每条路径的两端对应两个插头插头两两匹配从左到右一定不会出现从左到右一定不会出现4个插头个插头a, b, c, d，a, c匹配，匹配，b, d匹配匹配dcab插头不会交叉括号序列!( ) ( ( ) ) ( ) 9括号表示法( () (0：无插头状态，用：无插头状态，用 # 表示表示1：左括号插头，用：左括号插头，用 ( 表示表示 2：右括号插头，用：右括号插头，用 ) 表示表示3进制进制#(1 1 2 0 2 1 2)310状态的转移每次转移相当于轮廓线上当前决策格子的左插每次转移相当于轮廓线上当前决策格子的左插头改成下插头，上插头改成右插头的状态头改成下插头，上插头改成右插头的状态11Case 1没有上插头和左插头，有下插头和右插头，没有上插头和左插头，有下插头和右插头，相当于相当于构成一个新的连通块构成一个新的连通块 ) 插头插头 ( 插头插头( (# # # # # #) )( ( () )# #) )转移时间：转移时间：O(1)12Case 2有上插头和左插头，这种情况下相当于有上插头和左插头，这种情况下相当于合并合并两个连通分量两个连通分量预处理每个状态每的预处理每个状态每的括号所匹配的括号括号所匹配的括号转移时间转移时间: : O(1) ( 插头插头(插头插头# #( ( () ) )( (# # # #( () ) ( 插头插头Case 2.1 上插头和左插头均为上插头和左插头均为( (插头插头13Case 2有上插头和左插头有上插头和左插头转移时间：转移时间：O(1)( (# #) )( () )( (# # # # # #) ) ( 插头插头)插头插头Case 2.2 左插头为左插头为) )插头，上插头为插头，上插头为( (插头插头14Case 2有上插头和左插头有上插头和左插头 ( 插头插头)插头插头路径的两端连接路径的两端连接起来形成回路起来形成回路Case 2.3 左插头为左插头为( (插头，上插头为插头，上插头为) )插头插头15Case 3上上插头和左插头恰好有一个，这种情况相当插头和左插头恰好有一个，这种情况相当于于延续原来的连通分量延续原来的连通分量 ) 插头插头)插头插头无插头无插头转移时间：转移时间：O(1)( ( () )# #) )( ( () )# #) )16实验比较测试数据 最小表示 7Based最小表示 8Based括号表示 3Based括号表示 4Basedm = n = 10无障碍31ms15ms0ms0msm = n = 11(1,1)为障碍187ms109ms46ms31msm = n = 12无障碍873ms499ms265ms140ms建议使用建议使用2k进制，位运算效率高进制，位运算效率高17拓展如果求经过所有非障碍格子的如果求经过所有非障碍格子的哈密顿哈密顿路径路径的个数呢的个数呢?独立插头独立插头0 无插头状态无插头状态1 左括号插头左括号插头2 右括号插头右括号插头3 独立插头独立插头3进制进制4进制进制18如果一个连通块只有如果一个连通块只有1个插头或大于个插头或大于2个插头呢个插头呢?广义的括号匹配括号表示法需要满足一个括号表示法需要满足一个连通块内恰好有连通块内恰好有2个插头个插头特殊性对于一个大于对于一个大于2个插头的连通块个插头的连通块 最左边的插头标记为最左边的插头标记为 ( 最右边的插头标记为最右边的插头标记为 ) 中间的插头标记为中间的插头标记为 )(单独为一个连通块的插头标记为单独为一个连通块的插头标记为 ( )广义的括号表示法19广义的括号表示法左括号与右括号匹配对应的插头连通左括号与右括号匹配对应的插头连通例例: 最小表示法最小表示法 广义括号表示法广义括号表示法12234321()()普适性20总结简单回路简单回路最小表示法最小表示法一般性一般性特殊性特殊性括号表示法括号表示法拓拓展展简单路径简单路径3 3进制进制44进制进制括号表示法的改进括号表示法的改进广广义义的的括括号号表表示示法法21全文研究内容一类简单路径问题一类简单路径问题一类棋盘染色问题一类棋盘染色问题一类基于非棋盘模型的问题一类基于非棋盘模型的问题一类最优性问题的剪枝优化一类最优性问题的剪枝优化Rocket Mania (Zju2125)生成树计数 (NOI2007)Black & White(Uva10532)Formula 1(Ural1519)Formula 2(改编自Formula 1)22Thank you for listening!Questions are welcome. 23谢谢观赏！谢谢观赏！