Eine Einführung in das EcliPse System
... [ Seminarthemen SS01 ] ... [ Inhaltsverzeichnis ] ... [ Suchstrategien ] ...
Das ECLiPSe System
Einleitung
Bei ECLiPSe handelt es sich um eine CLP Plattform, die über CLP hinaus
auch mathematische und stochastische Funktionalität bietet.
ECLiPSe wurde zur Lösung von kombinatorischen industriellen Problemen in
den Gebieten der Planung, Ressourcenverteilung und Scheduling entwickelt.
Folgende Programmiersprachen können integriert werden, um die
Fähigkeiten von Eclipse zu erweitern.
- C und C++.
- Tcl/TK (wird auch für die mitgelieferte Entwicklungsumgebung genutzt).
- Visual Basic.
Weitere Eigenschaften von ECliPSe:
- Rapid Prototyping wird unterstützt.
- Eine Entwicklungsumgebung (in Tcl/TK implementiert) wird mitgeliefert.
- Es gibt einen Debugger zu Fehlersuche.
- Ein Profiling Tool wird eingesetzt, um die einzelnen Laufzeiten zu bestimmen.
- Es können Bibliotheken geschrieben und eingebunden werden.
Die FD Library von ECLiPSe
Die FD Library ermöglicht dem Benutzer, Constraints auf die
Werte von Variablen zu legen.
Entscheidend ist hier der Begriff der Domain Variablen. Dabei handelt es
sich um eine Variable mit einem endlichen Wertebereich.
Beispiel:
X :: 1..5
Y :: [red,green,blue]
Z :: [1,3,5,5..8]
Es gibt zwei Arten von Constraints, symbolische und arithmetische.
Eine arithmetische Constraint ist nichts anderes als eine mathematische Beziehung
zwischen Termen. Dabei kann es sich um eine Gleichheits oder
Ungleichheitsbeziehung handeln:
Gleichheit
#= ist gleich
Ungleichheit
## ungleich
#< echt kleiner
#<= kleiner gleich
#> echt größer
#>= größer gleich
ECLiPSe bietet die Möglichkeit, lineare und nichtlineare
Constraints zu definieren.
Ein linearer Term ist ein Ausdruck von Zahlen und Domain Variablen,
in dem es keine Multiplikation oder Division von Domain Variablen
gibt. 2*X-Z #< X-3 ist eine lineare arithmetische Beschränkung, X*Z #> 3 ist
hingegen keine.
Konjuktion und Disjunktion wird durch die #/\ und #\/ Prädikate
ausgedrückt.
Symbolische Constraints werden durch spezielle Prädikate
wie z.B. element(I, List, X) ausgedrückt. Dieser Ausdruck bedeutet, daß
X das I-te Element von Liste sein soll.
Es gibt eine elementare Strategie, wie in einer CLP Sprache wie ECLiPSe
ein CSP (Constraint Satisfaction Problem) angegegangen werden sollte.
- Identifiziere die Domain Variablen und definiere sie mit den jeweiligen
Wertebereichen.
- Identifiziere und definiere die Constraints zwischen den zu betrachtenden
Domain Variablen. Mit diesem Schritt wird der Suchraum eingeschränkt.
- Spezifiziere und starte einen Suchmechanismus, der in Zusammenarbeit mit dem internen
Constraint Lösungsmechanismus und der ECLiPSe Engine die Lösung findet, sofern
eine existiert.
Beispiel für CLP
Gibt es eine Zahl, die bei einer Division durch 3 einen Rest von 1,
bei Division durch 4 einen Rest von 2, bei Division durch 5 einen Rest von 3
und bei Division durch 6 einen Rest von 4 ergibt?
(Kordemsky)
Lösungansatz
:- lib(fd).
solve(X) :-
X #> 0,
X #= A*3 + 1,
X #= B*4 + 2,
X #= C*5 + 3,
X #= D*6 + 4,
labeling([X,A,B,C,D]).
... [ Seminarthemen SS01 ] ... [ Inhaltsverzeichnis ] ... [ Suchstrategien ] ...