Dynamic Programming on the Word RAM
Dynamic Programming on the Word RAM
复制标题
字 RAM 上的动态编程
作者：
David Pisinger
动态规划是求解最优化问题的基本方法之一。在本文中，我们提出了一个通用的框架，可以用来降低这些算法的时间和空间复杂度的对数因子。该框架基于字编码，即通过将子解表示为整数中的位。这样，字并行就可以用于动态规划递归的计算。使用这种编码可以在O（n B/ log B）时间和O（B/ log B）空间中解决子集和问题，其中n是给定整数的个数，B是目标和。该背包问题的求解时间复杂度为O（n m/ log m），空间复杂度为O（m/ log m），其中n为项目数，m = max{B，z}为容量B和最优解z的最大值.在有向无环图G=（V，E）中寻找给定长度B的路的问题可以在O（|E| B/ log B）时间和O（|V| B/ log B）空间。给出了其他几个例子，显示所实现的技术的一般性。提供了大量的计算实验，以证明所取得的成果不仅是理论上的兴趣，但实际上导致的算法是两个数量级的速度比他们的前辈。这是一个令人惊讶的观察，因为速度的增加大于处理器的字长。
Dynamic programming is one of the fundamental techniques for solving optimization problems. In this paper we propose a general framework which can be used to decrease the time and space complexity of these algorithms with a logarithmic factor. The framework is based on word encoding, i.e. by representing subsolutions as bits in an integer. In this way word parallelism can be used in the evaluation of the dynamic programming recursion. Using this encoding the subset-sum problem can be solved in O( n b/ log b) time and O(b/ log b) space, where n is the number of integers given and b is the target sum. The knapsack problem can be solved in O( n m/ log m) time and O(m/ log m) space, where n is the number of items and m = max{b,z} is the maximum of the capacity b and the optimal solution value z . The problem of finding a path of a given length b in a directed acyclic graph G=(V,E) can be solved in O(|E|b/ log b) time and O(|V|b/ log b) space. Several other examples are given showing the generality of the achieved technique. Extensive computational experiments are provided to demonstrate that the achieved results are not only of theoretical interest but actually lead to algorithms which are up to two orders of magnitude faster than their predecessors. This is a surprising observation as the increase in speed is larger than the word size of the processor.