Share Email Print

Proceedings Paper

Automatic Synthesis Of Greedy Programs
Author(s): Sanjay Bhansali; Kanth Miriyala; Mehdi T. Harandi
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

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.

Paper Details

Date Published: 21 March 1989
PDF: 12 pages
Proc. SPIE 1095, Applications of Artificial Intelligence VII, (21 March 1989); doi: 10.1117/12.969286
Show Author Affiliations
Sanjay Bhansali, University of Illinois at Urbana-Champaign (United States)
Kanth Miriyala, University of Illinois at Urbana-Champaign (United States)
Mehdi T. Harandi, University of Illinois at Urbana-Champaign (United States)

Published in SPIE Proceedings Vol. 1095:
Applications of Artificial Intelligence VII
Mohan M. Trivedi, Editor(s)

© SPIE. Terms of Use
Back to Top