Efficient dynamic programming using quadrangle inequalities
Efficient dynamic programming using quadrangle inequalities
复制标题
使用四边形不等式的高效动态规划
DOI：
--
复制
发表时间：
1980
期刊：
影响因子：
--
通讯作者：
F. Yao
中科院分区：
文献类型：
--
作者：
F. Yao
<italic>动态规划</italic>是计算机科学和运筹学中几种广泛使用的问题求解技术之一。在应用这种技术时，人们总是试图通过利用手头问题的特殊性质来提高速度。然而，在目前的技术水平，特设的方法来加速似乎是特征;很少有一般的标准是已知的。本文给出了一个提高绘制速度的<italic>四边形不等式</italic>条件。这个条件很容易检验，并且可以应用于几个明显不同的问题。例如，它立即从我们的一般条件，最佳二叉搜索树的建设可以加快从<italic>O（n</italic><supscrpt>3</supscrpt>）步骤到<italic>O（n</italic><supscrpt>2</supscrpt>），一个结果，首先获得了克努特使用不同的和相当复杂的参数。
<italic>Dynamic programming</italic> is one of several widely used problem-solving techniques in computer science and operation research. In applying this technique, one always seeks to find speed-up by taking advantage of special properties of the problem at hand. However, in the current state of art, ad hoc approaches for speeding up seem to be characteristic; few general criteria are known. In this paper we give a <italic>quadrangle inequality</italic> condition for rendering speed-up. This condition is easily checked, and can be applied to several apparently different problems. For example, it follows immediately from our general condition that the construction of optimal binary search trees may be speeded up from <italic>O(n</italic><supscrpt>3</supscrpt>) steps to <italic>O(n</italic><supscrpt>2</supscrpt>), a result that was first obtained by Knuth using a different and rather complicated argument.