Automatic Synthesis Of Greedy Programs

Sanjay Bhansali; Kanth Miriyala; Mehdi T. Harandi

doi:10.1117/12.969286

21 March 1989 Automatic Synthesis Of Greedy Programs

Sanjay Bhansali, Kanth Miriyala, Mehdi T. Harandi

Proceedings Volume 1095, Applications of Artificial Intelligence VII; (1989) https://doi.org/10.1117/12.969286
Event: SPIE 1989 Technical Symposium on Aerospace Sensing, 1989, Orlando, FL, United States

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.

Citation Download Citation

Sanjay Bhansali, Kanth Miriyala, and Mehdi T. Harandi "Automatic Synthesis Of Greedy Programs", Proc. SPIE 1095, Applications of Artificial Intelligence VII, (21 March 1989); https://doi.org/10.1117/12.969286

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available