Eine Einführung in das EcliPSe System

Fallbeispiel: Das Damenproblem als Veranschaulichung der Verwendung von Heuristik innerhalb von Suchstrategien

• Einleitung
• Lösung per Hand
• Ein ECLiPSe Programm zur Lösung
• Optimierung durch die Anwendung von Heuristiken

Anhand des bekannten Damenproblems (N-Queens-Problem) wird eine kleine Einführung in die Programmierung in ECLiPSe mit der FD-Library gegeben. Dabei wird das Problem mit unterschiedlichen Heuristiken angegangen und die Ergebnisse diskutiert.

Die Aufgabenstellung

Wie muß man N Damen auf einem Schachbrett der Ausmaß NxN plazieren, damit sich keine zwei Damen gleichzeitig bedrohen.

Offensichtlich darf auf jeder Spalte, jeder Zeile und jeder Diagonalen nur eine Dame stehen.
Ein solches Problem, welches nur über binäre Relationen verfügt, kann gut als Graph dargestellt werden. Einen solchen Graphen bezeichnet man dann als Constraint Network. Als Beispiel folgt hier die Darstellung des Constraint Networks für das 4-Damen Problem.


Die Kanten sind jeweils mit mit den Wertepaaren beschriftet, die der Constraint "DameX und DameY bedrohen sich nicht" genügen.

Anhand dieses Netzwerkes läßt sich nun ein Suchbaum konstruieren, der zu den Lösungen führt:


Die Lösung erfolgt nach mittels inkrementeller Zuordnung (Constructive Search), deren Methodik im vorangegangenen Kapitel schon näher beschrieben wurde. Bei jeder Wertzuweisung müssen die Constraints zwischen aktueller und bereits zugewiesenen Variablen beachtet werden. So erhält man die beiden einzigen Lösungen für das 4-Damen Problem. Schon bei dieser kleinen Dimensionierung fällt auf, daß die Lösungen in der Mitte des Suchbaumes liegen, womit sich das Problem als gutes Anschauungsobjekt für den Einsatz von Heuristiken anbietet.

:- lib(fd).	Hiermit wird die Finite Domain Library eingebunden
queens(N, Board) :-	Der Klauselkopf. Mit N wird die Größe des Schachbrettes spezifiziert. Board ist ein Platzhalter, damit man vom Prolog Interpreter die Lösung erhält und nicht nur die Aussage, daß es eine gibt.
length(Board,N),	Das vordefinierte Prädikat length/2 erzeugt bei dieser Art der Verwendung eine Liste mit N Variablen.
Board :: 1..N,	Hiermit wird der Wertebereich für die Listenvariablen festgelegt
( fromto (Board, [Q1|Cols], Cols, []) do ( foreach(Q2, Cols), count(Dist,1,_), param(Q1) do noattack(Q1, Q2, Dist) ) ),	Verschachtelte Schleifenprogrammierung in ECLiPSe unter Vermeidung von Symmetrie. Dem Prädikat noattack/3 werden die nötigen Parameter übergeben: Die beiden Damen Variablen und die Distanz in Spalten zueinander. Aus diesen Informationen definiert das Prädikat die erforderlichen Constraints
labeling(Board).	Die Standard Suchmethode von ECLiPSe wird aufgerufen
noattack(Q1,Q2,Dist) :-	Der Klauselkopf für die Generierung der Constraints
Q1 ## Q2,	Die Damen dürfen nicht auf einer gemeinsamen Zeile positioniert werden
Q1 - Q2 ## Dist, Q2 - Q1 ## Dist.	Die Damen dürfen nicht auf einer gemeinsamen Diagonalen positioniert werden

Wenn man dieses Programm nun mit verschiedenen Instanzen ausführt, macht sich selbst auf einem derzeit aktuellen System (PIII, 933 MHZ) schnell Ernüchterung breit. Beim 16-Damen Problem wird noch ohne merkbare Verzögerung eine Lösung gefunden, bei einem 32x32 Feld ist geduldiges Warten angesagt. Um diese Performance zu steigern, werden im folgenden Heuristiken angewendet, die im vorangegangenen Kapitel näher beschrieben wurden.

Ausgangspunkt war die Standardsuchroutine, die mit dem vordefinierten Prädikat labeling/1 aufgerufen wurde. Intern ist dieses Prädikat wie folgt aufgebaut:

   labeling(AllVars) :- 
   	( foreach(Var, AllVars) do
   		indomain(Var)
   	).
 

   labeling(AllVars) :- 
   	( fromto(AllVars, Vars, VarsRem, []) do
   		deleteff(Var, Vars, VarsRem),
   		indomain(Var)
   	).
 

:- lib(list).

labeling(AllVars) :-
		middle_first(AllVars, AllVarsPreOrdered),
		( fromto(AllVarsPreOrdered, Vars, VarsRem,[]) do 
			deleteff(Var,Vars,VarsRem),			
			indomain(Var)
                ).

middle_first(List,Ordered) :- 
	halve(List, Front, Back),
	reverse(Front,RevFront),
	splice(Back,RevFront,Ordered).