Problem Solving and Nondeterministic Programming Systems.
Abstract
The paper suggests and discusses an implementaion of several ideas in the area of problem solving and nondeterministic programming systems. After discussing the history of work in this field, definitions of forward, horizontal, and backwards simple moves are given. With these definitions, the level of a problem is defined to be the maximum number of consecutive backwards moves required to solve the problem. Level zero problems can be solved using forward and horizontal moves only. It is then shown how two methods, the combination of moves and problems reduction, sometimes reduce the level of a problem. The use of Gibbons' Q-size rule to prevent redundancy is shown to sometimes conflict with heuristic search methods. The use of a hasing function to detect redundancy is discussed. The choosing of moves according to their evaluation of move types was used in a program, POPS II, based on Gibbons' POPS, which was shown to be more efficient than previous nondeterministic problem solvers for several problems. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1973
- Accession Number
- AD0764501
Entities
People
- William George Kennedy
Organizations
- Naval Postgraduate School