本文共 710 字,大约阅读时间需要 2 分钟。
动态规划问题中重要的一环就是确定状态的定义,在大多数情况下,状态中所包含的信息并不多,比如线性规划问题的状态一般表示为 d[i,j](i 表示状态的位置,j 表示状态的阶段),算法实现时可用二维数组保存计算过程中的状态。但是也有一些问题,它的状态中包含的信息很多,比如它的状态可能是一个集合中各个元素的情况,或者是像铺瓷砖问题这样,是某一行的覆盖状态。如果沿用简单的状态表示方法,则可能会用到 N 维数组,这样不仅空间占用大,而且状态的转移(状态递推公式)算法也会非常复杂。不信?读者猜猜这个状态 d[i, j, k, l, m, n, o, p, q, r, s, t] 的下一个状态是什么,是 t + 1 还是 q + 1 ?
在这种情况下,如果我们能用一种编码策略,将前面例子中的 j, k, l, m, n, o, p, q, r, s, t 编码成一个整数数字,就可以将状态简化成 d[i, encode(j, k, l, m, n, o, p, q, r, s, t)],这种情况下就可以用二维数组来保存状态,并且状态的递推公式也会简单很多。这种策略看起来好像状态被“压缩”了,所以被称为状态压缩动态规划。
严格来说,状态压缩是状态压缩,动态规划是动态规划,是算法模式,它们只是碰巧一起发生了而已。这种通过某种编码和解码方式将某些离散的信息(比如集合中各个元素的状态)转化成某种简单数值类型进行计算和处理的方法,在很多算法中都有体现,并非状态规划独有的方法。最常见的就是各种 hash 算法,通过比较 hash 值的方法比较原始数据的差异要比直接比较原始数据简单高效。
<转载地址:http://odcgj.baihongyu.com/