Accession Number : AD0688604

Title :   A HEURISTIC PROGRAM FOR SOLVING PROBLEMS STATED AS NONDETERMINISTIC PROCEDURES.

Descriptive Note : Doctoral thesis,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Fikes,Richard Earl

Report Date : NOV 1968

Pagination or Media Count : 271

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)

Descriptors :   (*PROBLEM SOLVING, COMPUTER PROGRAMS), PROGRAMMING LANGUAGES, SEARCH THEORY, MATHEMATICAL LOGIC, THESES

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE