A HEURISTIC PROGRAM FOR SOLVING PROBLEMS STATED AS NONDETERMINISTIC PROCEDURES.
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
The paper describes an effort to design a heuristic problem solving program in which the primary concerns are with the generality of the programs input language and the effectiveness and generality of the programs 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
- Computer Programming and Software