MINION (CSP-Solver)
MINION ist ein kostenloses Programm bzw. eine Sprache zur Lösung von Bedingungserfüllungsproblemen (Constraint-Satisfaction-Problems = CSP).
Im Gegensatz zu einigen andern CSP-Solvern für welche man z.B. C++- oder Java-Programmteile schreiben muss, schreibt man für die Anwendung von MINION nicht viel mehr als die logischen Formeln nieder. (Prolog-Ansätze sind recht ähnlich) .
Das Werkzeug wurde am Institut für Computerwissenschaften[1] der University of St Andrews (Schottland) entwickelt.
Um die Arbeit zu erleichtern gibt es noch das Programm TAILOR[2]. Es verfügt über eine interaktive graphische Oberfläche die sogar MINION ausführt und eigentlich in der Sprache Essence’[3][4][5] Geschriebenes benutzt. Die User müssen nicht einmal programmieren können, um Probleme in MINION zu lösen. (TAILOR wird seit September 2010 nicht mehr weiterentwickelt[6] und wurde durch Savile Row[7][8] abgelöst.)
Essence’ ist bei der Formulierung von Problemstellungen weitaus weniger aufwendig und vom jeweiligen Lösungssystem unabhängig. Ein weiterer Vorteil von Essence’ ist, dass man ganze Problemklassen und nicht nur einzelne Problemstellungen (wie in MINION) formulieren kann.
Ein Beispiel[Bearbeiten]
Man löse das System: {pigs + hens = 7} und {4·pigs + 2·hens = 22}
Der MINION-Code hierzu wäre: summer_school/examples/FarmersProblem.minion[9] (leichter lesbare Essence’-Version[10])
MINION 3
**VARIABLES**
DISCRETE pigs {0..7}
DISCRETE hens {0..7}
**SEARCH**
PRINT [[pigs],[hens]]
VARORDER [pigs,hens]
**CONSTRAINTS**
weightedsumgeq([2,4], [hens,pigs], 22)
weightedsumleq([2,4], [hens,pigs], 22)
sumleq([hens,pigs], 7)
sumgeq([hens,pigs], 7)
**EOF**
Weblinks[Bearbeiten]
Einzelnachweise[Bearbeiten]
- ↑ University of St Andrews: Institute of Computer Science
- ↑ MINION: Tools (TAILOR)
- ↑ MINION: Tools (Essence’)
- ↑ ESSENCE’ Homepage
- ↑ ESSENCE’ Beispiele
- ↑ TAILOR abgelöst durch Savile Row
- ↑ Savile Row Homepage
- ↑ Savile Row: Beispiele etc.
- ↑ Code von summer_school/examples/FarmersProblem.minion
- ↑ Code als Essence’-Version: summer_school/examples/FarmersProblem.eprime
