NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Collections About News Help Login
Back to Results
An algorithm for a general class of routing problems derived from Huygens' principleIf a set of N points or nodes with a nonnegative cost associated with each ordered pair is known, it is desired to find a path from one given node to another given node which minimizes the cost sum. An algorithm is presented which yields a global minimum solution after at most N - 1 iterations or on a typical large third-generation computer, after 1 hour of computation time for a 10,000-node problem. The rapid-access data storage capacity demanded by the algorithm is approximately 3N words for costs read in from slow-access storage or 2N words for calculable costs. The time-storage requirements of the algorithm known to the authors. When the problem is viewed as a discretized optimal control problem, after N-1 iterations, an optimal control or node transition is established for each of the N nodes or states; thus, the algorithm can be applied to situations were there may be errors in the control that necessitate a closed loop control that necessitate a closed loop control philosophy.
Document ID
19740019222
Acquisition Source
Legacy CDMS
Document Type
Other - NASA Technical Note (TN)
Authors
Avis, L. M. (NASA Langley Research Center Hampton, VA, United States)
Young, G. R. (NASA Langley Research Center Hampton, VA, United States)
Date Acquired
September 3, 2013
Publication Date
June 1, 1974
Subject Category
Space Sciences
Report/Patent Number
L-9342
NASA-TN-D-7580
Accession Number
74N27335
Funding Number(s)
PROJECT: RTOP 790-93-08-01
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.

Related Records

There are no records associated with this record.
No Preview Available