Robert W. Floyd
Skip Abstract Section
Abstract
Programs to solve combinatorial search problems may often be simply written by using multiple-valued functions. Such programs, although impossible to execute directly on conventional computers, may be converted in a mechanical way into conventional backtracking programs. The process is illustrated with algorithms to find all solutions to the eight queens problem on the chessboard, and to find all simple cycles in a network.
- 1 BALL, W.R. Mathematical Recreations and Essays (12th ed.). Macmillan, New York, 1947.Google Scholar
- 2 FLOYD, R. W. The syntax of programming languages--a survey. IEEE Trans. EC-I3, 4 (Aug. 1964), 346-353.Google Scholar
- 3 GOLOMB, S. W., AND BAUMERT, L .D . Backtrack programming. J. ACM 12, 4 (Oct. 1965), 516-524. Google Scholar
- 4 IRONS, E. T. A syntax-directed compiler for ALGOL 60. Comm. ACM 4, 1 (Jan. 1961), 51-55. Google Scholar
Index Terms
- Nondeterministic Algorithms
Recommendations
Nondeterministic Control for Hybrid Search
Hybrid algorithms combining local and systematic search often use nondeterminism in fundamentally different ways. They may differ in the strategy to explore the search tree and/or in how computation states are represented. This paper presents ...
Comments