基于连通性压缩的动态规划：棋盘与非棋盘问题的优化解法

本文主要探讨了棋盘与非棋盘问题中的共通点，特别是关注基于连通性状态压缩的动态规划问题。作者陈丹琦，来自长沙市雅礼中学，通过电子邮件skyfish_cdq@163.com分享了她的研究成果。动态规划在此问题中扮演了关键角色，因为它能够处理数据规模相对较小的问题，如棋盘上的哈密顿回路个数，其中m和n的值均小于等于12。 在这些问题中，状态压缩是重要的技术，用于减少状态空间的大小。一个关键的概念是“插头”，它表示一个格子在特定方向与相邻格子的连接情况。"轮廓线"则用来划分已决策区域和未决策区域，其上方的插头数量固定，包括n个下插头和1个右插头。状态被定义为f(i,j,S)，其中i和j代表当前格子的位置，S则是表示插头连通性的编码，用最小表示法表示，如0表示无插头，正整数表示有插头且连通性相同。 状态转移过程依赖于上一个状态，并在O(n)时间内更新新状态。即使在最大规模（m=n=12）的情况下，无障碍棋盘的极限状态总数也达到了1333113，表明这个问题已经可以通过现有方法有效解决。然而，作者提出的问题特殊性促使进一步思考：由于每个非障碍格子恰好有两个插头，且这些插头可以形成若干互不相交的路径，它们之间存在匹配关系，避免了插头交叉的情况。为了简洁地表示这种结构，文章提及了括号序列，其中括号的使用规则反映了插头的匹配情况。 总结来说，这篇论文深入研究了如何利用连通性状态压缩来简化动态规划问题，特别是在棋盘模型中的哈密顿回路问题，通过巧妙地定义状态和状态转移规则，有效地解决了规模适中的问题。同时，作者也提出了针对特殊性质问题可能存在的优化思路，即通过括号表示法来更紧凑地表示插头连通性。