Problem solving and nondeterministic programming systems
Loading...
Authors
Kennedy, William George
Subjects
Problem solving
Nondeterministic programming systems
Nondeterministic finite automata
Q-size rule
REF-ARF
POPS
Level of a problem
Nondeterministic programming systems
Nondeterministic finite automata
Q-size rule
REF-ARF
POPS
Level of a problem
Advisors
Gibbons, G.D.
Date of Issue
1973-06
Date
June 1973
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
This paper suggests and discusses an implementation 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 problem 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 hashing 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.
Type
Thesis
Description
Series/Report No
Department
Computer Science Group
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.