Accession Number : ADP002963

Title :   Space and Time Analysis in Dynamic Programming Algorithms,

Corporate Author : ATLANTA UNIV GA DEPT OF MATHEMATICAL AND COMPUTER SCIENCES

Personal Author(s) : Warsi,N. A. ; Setzer,C. B.

Report Date : FEB 1984

Pagination or Media Count : 4

Abstract : Dr. Nazir Warsi, in recent work, showed how to solve certain dynamic programming problems while keeping strict bounds on the amount of working storage needed. We discuss extensions of Dr. WArsi's methods and anlaysis to more general dynamic programming networks. We describe a general algorithm for solving problems in this more general class. This algorithm may be applied in such a way as to limit working storage arrays to any dimensions greater than or equal to 2. In making this restriction, there are two costs: a number of arrays of dimension 2 may need to be stored simultaneously; searches for maxima can become arbitrarily complex with the complexity of the network. We discuss the implementation of the general algorithm in a higher level language with particular emphasis on storage management. We also discuss data representations and the practicality of implementing a system for handling general networks. (Author)

Descriptors :   *Dynamic programming, *Algorithms, Problem solving, Networks, Loops, Data management, Data storage systems, High level languages

Distribution Statement : APPROVED FOR PUBLIC RELEASE