A HEURISTIC PROGRAM FOR SOLVING PROBLEMS STATED AS NONDETERMINISTIC PROCEDURES.
Abstract
The paper describes an effort to design a heuristic problem solving program in which the primary concerns are with the generality of the program's input language and the effectiveness and generality of the program's problem solving methods. To obtain the desired generality and ease of problem statement in an input language, extending a programming language is proposed to form a nondeterministic language which is suitable for stating problems. The extensions preserve the representational power and generality of the data and control structures of the base programming language. The scope and limitations of nondeterministic programming languages as input languages are discussed and compared with the input languages used by other problem solving programs. The program was designed to accept problems stated in a particular nondeterministic programming language and to deal effectively with the diversity of problems expressible in the language. The program translates a nondeterministic procedure into a heuristic search problem in which each object in the search space is itself a constraint satisfaction problem. The program combines heuristic search methods and constraint satisfaction methods to conduct the search and to solve the problems defined by the objects in the space. The behavior of the program on a set of example problems is described and analyzed. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1968
- Accession Number
- AD0688604
Entities
People
- Richard Earl Fikes
Organizations
- Carnegie Mellon University