21 March 1989 Automatic Synthesis Of Greedy Programs
Author Affiliations +
This paper describes a knowledge based approach to automatically generate Lisp programs using the Greedy method of algorithm design. The system's knowledge base is composed of heuristics for recognizing problems amenable to the Greedy method and knowledge about the Greedy strategy itself (i.e., rules for local optimization, constraint satisfaction, candidate ordering and candidate selection). The system has been able to generate programs for a wide variety of problems including the job-scheduling problem, the 0-1 knapsack problem, the minimal spanning tree problem, and the problem of arranging files on tape to minimize access time. For the special class of problems called matroids, the synthesized program provides optimal solutions, whereas for most other problems the solutions are near-optimal.
© (1989) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Sanjay Bhansali, Sanjay Bhansali, Kanth Miriyala, Kanth Miriyala, Mehdi T. Harandi, Mehdi T. Harandi, } "Automatic Synthesis Of Greedy Programs", Proc. SPIE 1095, Applications of Artificial Intelligence VII, (21 March 1989); doi: 10.1117/12.969286; https://doi.org/10.1117/12.969286


Back to Top