A discipline of dynamic programming over sequence data
A discipline of dynamic programming over sequence data
复制标题
DOI：
10.1016/j.scico.2003.12.005
复制
发表时间：
2004-06-01
影响因子：
1.3
通讯作者：
Steffen, P
中科院分区：
文献类型：
--
作者：
Giegerich, R;Meyer, C;Steffen, P
动态规划是一种经典的编程技术，适用于各种各样的领域，如随机系统分析，运筹学，离散结构的组合学，流问题，歧义语言的解析和生物序列分析。迄今为止，很少有方法可用于指导这种算法的设计。描述动态规划算法的矩阵递归式通常很难构造，容易出错，并且在重要的应用程序中几乎不可能完全调试。本文介绍了一种旨在缓解这一问题的规则。我们描述了一个代数风格的动态规划序列数据。我们定义其正式的框架，基于语法和代数的组合，并包括形式化的贝尔曼的原则。我们提出了一种语言用于算法设计上的一个方便的抽象层次。我们概述了实现这种语言的三种方法，包括在一个懒惰的函数式语言中的嵌入。新方法的工作原理说明了一系列的例子来自不同领域的计算机科学。(C)2004 Elsevier B.V.保留所有权利。
Dynamic programming is a classical programming technique, applicable in a wide variety ofdomains such as stochastic systems analysis, operations research, combinatorics of discrete structures, flow problems, parsing of ambiguous languages, and biosequence analysis. Little methodology has hitherto been available to guide the design of such algorithms. The matrix recurrences that typically describe a dynamic programming algorithm are difficult to construct, error-prone to implement, and, in nontrivial applications, almost impossible to debug completely.This article introduces a discipline designed to alleviate this problem. We describe an algebraic style of dynamic programming over sequence data. We define its formal framework, based on a combination of grammars and algebras, and including a formalization of Bellman's Principle. We suggest a language used for algorithm design on a convenient level of abstraction. We outline three ways of implementing this language, including an embedding in a lazy functional language. The workings of the new method are illustrated by a series of examples drawn from diverse areas of computer science. (C) 2004 Elsevier B.V. All rights reserved.