It has been shown that the parallel Lattice Linear Predicate (LLP) algorithm solves many combinatorial optimization problems such as the shortest path problem, the stable marriage problem and the market clearing price problem. In this paper, we give the parallel LLP algorithm for many dynamic programming problems. In particular, we show that the LLP algorithm solves the longest subsequence problem, the optimal binary search tree problem, and the knapsack problem. Furthermore, the algorithm can be used to solve the constrained versions of these problems so long as the constraints are lattice linear. The parallel LLP algorithm requires only read-write atomicity and no higher-level atomic instructions.
翻译：已经证明平行的 Lattice Linesar Predicate (LLP) 算法可以解决许多组合优化问题,如最短路径问题、稳定的婚姻问题和市场清理价格问题。 在本文中,我们将平行的 LLP 算法用于解决许多动态编程问题。 特别是, 我们显示 LLP 算法可以解决最长的后继问题、 最佳的二进制搜索树问题和 knapsack 问题。 此外, 算法可以用来解决这些问题的有限版本, 只要限制是线性。 平行的 LLP 算法只需要读写原子, 不需要更高的原子指令 。
相关内容
微信扫码咨询专知VIP会员