A dynamic programming algorithm to find all solutions in a neighborhood of the optimum
type: Item
instance of: scholarly article
title: A dynamic programming algorithm to find all solutions in a neighborhood of the optimum
zbMATH Open document ID: 0586.90089
DOI: 10.1016/0025-5564(85)90096-3
author: Michael S. Waterman
author: Thomas H. Byers
published in: Mathematical Biosciences
publication date: 1985-01-01T00:00:00Z
review text: A dynamic programming algorithm is described whose aim is to give all paths through an acyclic network whose length is within a certain fixed percentage of that of the shortest path. An example is given and is followed by an extensive discussion of the application of the algorithm to a problem of finding distances between biological sequences. This method is compared with some suggested previously with respect to computational and storage requirements.
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 92B05
zbMATH DE Number: 3941289
zbMATH Keywords: k-th best policies
zbMATH Keywords: near-optimal policies
zbMATH Keywords: matching topological sequences
reviewed by: Kevin D. Glazebrook
MaRDI profile type: Publication
full work available at URL: 0025-5564(85)90096-3
OpenAlex ID: W2027490384
cites work: Onkth Best Policies
cites work: Technical Note—Determining All Optimal and Near-Optimal Solutions when Solving Shortest Path Problems by Dynamic Programming
cites work: An Appraisal of Some Shortest-Path Algorithms
cites work: Q5591269
cites work: Q5519754
cites work: CalculatingKth Shortest Paths
cites work: Data Structures and Computer Science Techniques in Operations Research
cites work: A Method for the Solution of the N th Best Path Problem
cites work: Q3048571
cites work: A Note on an Algebra for the k Best Routes in a Network
cites work: Letter to the Editor—The kth Best Route Through a Network
cites work: Solutions of the kth best route through a network. A review
cites work: Computational experience with an algorithm for finding the k shortest paths in a network
cites work: Iterative methods for determining the k shortest paths in a network
cites work: Sequence alignments in the neighborhood of the optimum with general application to dynamic programming
cites work: General methods of sequence comparison
cites work: On Elmaghraby's “The Theory of Networks and Management Science”
description: scientific article; zbMATH DE number 3941289