6Problemlösung mit Prolog
6.1Suche im Zustandsraum
Bemerkung: eine allgemeine Theorie der Suche im Zustandsraum wird von Dr. F. Ade im "Lisp-Teil" der Vorlesung vorgestellt. Hier konzentrieren wir uns auf die rekursive Implemen-tierung einiger grundlegenden Verfahren in Prolog.
Zustandsraum
- Menge S der möglichen Zustände des Problems; oft nur implizit gegeben.
- Menge T der möglichen Zustandsübergänge (Transitionen, Produktionen). T ist eine binäre Relation auf S.
- Anfangszustand, oder Menge von Anfangszuständen A (z.B. implizit durch ein Prädikat gegeben).
- Zielzustand, oder Menge von Zielzuständen Z.
- Lösung: Weg bestehend aus Folge von Zuständen in S, der in A anfängt und in Z endet.
Zustandsgraph
Zustände werden durch Knoten, Übergänge durch gerichtete Kanten dargestellt. Jeder Zustand (Knoten) kommt nur einmal vor. Schleifen sind möglich.
Lösungssbaum
Die Wurzel entspricht dem Anfangszustand. Söhne eines Knotens s sind Zustände si, sodass (s, si) eine Transition ist. Es gibt keine Schleifen, dafür können Zustände mehrfach oder unendlich oft auftreten. Der Lösungsbaum wird oft nur während der Lösung implizit aufgebaut.
Beispiel
Fig. 6.1: Ein Zustandsgraph
| Zustandsraum: | gemäss Fig. 6.1 |
| Anfangszustand: | a. |
| Endzustände: | z1, z2 |
Prolog Suche im Zustandsgraph
1) Kanten als Regeln, Suche durch Prolog-Beweiser
a) Rückwärtssuche (backward chaining)
s( b) :- s( a). /* Man kommt zu b, wenn man zu a kommt */
s( c) :- s( a).
s( e) :- s( b).
. . .
s( z1) :- s( e). /* Man kommt zu z1, wenn man zu e kommt */
s( a). /* Man kommt zu a; man ist in a: Start */
?- s( z1). ⇒ yes /* yes: Lösung existiert;
no: Lösung existiert nicht */
b) Vorwärtssuche (forward chaining)
s( a) :- s( b). /* Man kommt von a zum Ziel, wenn man von b zum Ziel kommt */
s( b) :- s( e).
. .
s( e) :- s( z1).
s( z1). /* Von z1 kommt man zum Ziel */
?- s( a). => yes /* yes: Lösung existiert;
no: Lösung existiert nicht */
Eigenschaften von a) und b):
- Suche depth-first (in der jeweiligen Richtung)
- mögliche Schleifen nicht berücksichtigt
- kein Weg berechnet (wäre durch Zusatzparameter möglich)
- sehr effizient, aber inflexibel
2) Kanten als Fakten, Suche durch ein Prolog (Meta-) Programm
t( a, b). /* Es gibt eine Transition (direkten Weg) von a nach b */
t( a, c).
t( b, e).
. . .
t( e, z1).
path( X, X).
path( X, Y) :- /* Vorwärtssuche */
t( X, Z), path( Z, Y).
path( X, Y) :- /* Rückwärtssuche */
t( Z, Y), path( X, Z).
?- path( a, z1). /* yes: Lösung existiert; no: Lösung exist. nicht */
Berechnung des Wegs
path( X, Y, Path) :-
path( X, Y, [X], V),
reverse( V, Path).
path( X, X, V, P) :- P = V. /* P wird zu V instantiiert */
path( X, Y, V, P) :- /* V = bereits besuchte Knoten (Visited), P nicht instantiiert */
t( X, Z),
path( Z, Y, [ Z| V], P).
Suche depth-first. Illustration durch Tracing:
path( X, Y, V, P) :-write(V), nl, …
[ a]
[ b, a]
[ d, b, a]
[ h, d, b, a]
[ e, b, a]
[ i, e, b, a]
/* Lösung: P = [ a, b, e, z1] */
Behandlung von Zyklen.
Der Zustandsraum kann Zyklen enthalten. Z.B. addiere die Transition t(e,a) vor t(e,i) und t(e,z1) . Das Programm terminiert nicht. Abhilfe: verfolge keine Zustände, die bereits besucht wurden. Der Test not member() ist leider sehr teuer.
path( X, Y, V, P) :-
t( X, Z), not member( Z, V),
path( Z, Y, [ Z| V], P).
Repräsentation von Zuständen und Übergängen
| Beispiel (Fig. 6.2): | Tische p, q, r; Blöcke a, b, c. |
| Anfangszustand: | a auf b, b auf p; q leer; c auf r. |
| Endzustand: | p leer; q leer; a auf b, b auf c, c auf r. |
Fig. 6.2: Ein Problem aus der Blockwelt
Repräsentation: s( p( [ a, b]), q( []), r( [ c])).
Beispiel einer Transition:
t( s( p( [ a, b]), q( []), r( [ c])), /* Zustand */
s( p( [ b]), q( [ a]), r( [ c])), /* neuer Zustand */
move( a, from( p), to( q)) ). /* Bewegung */
Sinnvoller: Regeln für Transitionen der gleichen Struktur:
t( s( p( [ P1| Ps], q( Q), r( R)),
s( p( Ps), q( Q1), r( R1)),
move( P1, from( p), to( D))) :-
( D = q, Q1 = [ P1| Q], R1 = R) ;
( D = r, Q1 = Q, R1 = [ P1| R]).
Tiefensuche:
solve( Problem, Solution) :-
start( Problem, Start),
solve( Start, [ Start], Solution).
solve( S, Visited, []) :-
goal( S).
solve( S, Visited, [T| Ts]) :- /* Ts = Transitionen, "Moves" */
t( S, S1, T),
not member( S1, Visited),
solve( S1, [ S1| Visited], Ts).
Problemformulierung:
| Transitionen: | t( S, S1, T) :- /* Bedingungen: Von S nach S1 mittels T */ |
| Anfangszustand: | start( Problem, Solution) :- .... |
| Zielzustand: | goal( State) :- .... |
| Lösung: | solve( Problem, Solution) |
Iterative Deepening
Tiefensuche leidet unter dem Problem, dass sie lange, resp. unendliche Wege verfolgen kann (z.B. bei Linksrekursion), obwohl es Lösungen entlang anderer, kurzer Wege gibt. Wir können die Tiefensuche beschränken und dabei sogar auf den member-Test verzichten:
solve( S, Visited, [T| Ts], Level) :-
Level > 0, Level1 is Level - 1,
t( S, S1, T),
solve( S1, [ S1| Visited], Ts, Level1).
Wie soll aber die maximale Suchtiefe gewählt werden? Eine interessante Methode ist das "Iterative Deepening" (R. E. Korf: Depth-first iterative deepening, Artificial Intelligence 27, 1985, p.97-105): Man fängt mit einer relativ kleinen Tiefe an. Wenn keine Lösung gefunden wird, so wird die Tiefe um 1 erhöht und der Prozess wird wiederholt
solve( Problem, Solution) :-
start( Problem, Start),
level( 1, 100, Level), /* generiert levels von 1 bis 100 */
solve( Start, [ Start], Solution, Level
level( Min, Max, Min).
level( Min, Max, Level) :-
Min < Max, Min1 is Min + 1,
level( Min1, Max, Level).
Optimale Lösungen: Best-first search
Oft will man nicht irgendeine, sondern eine optimale Lösung finden. Die Güte einer Lösung wird dabei durch eine Kostenfunktion gemessen, die vom zurückgelegten Weg abhängt (z.B. die Länge des Weges). Üblicherweise werden den Transitionen (positive) Kosten zugeordnet; die Kosten eines Weges ergeben sich dann als die Summe der Transitionskosten:
t( S1, S2, T, C) /* Transition von S1 nach S2 namens T mit Kosten C */
Beim best-first search wird eine ganze Front von Zuständen unterhalten, zusammen mit den Wegen dorthin:
p( Path, CP + H)
solve_best( [p( Path, Cost)| Frontier], FinalPath) :-
Path = [ T -> S | _],
goal( S),
reverse( Path, FinalPath).
solve_best( Frontier, FinalPath) :-
Frontier = [ p( Path, Cost)| Frontier1], /* lösche p( Path, Cost aus Frontier */
Path = [ T -> S | _],
findall( t( S, S1, T1, C1),
next_state( S, S1, T1, C1, Path), Ts),
update_frontier( p( Path, Cost), Frontier1, Ts, Frontier2),
/*..Nachfolgeknoten in Ts werden in Frontier1 eingefügt; dies ergibt Frontier2 */
solve_best( Frontier2, FinalPath).
update_frontier( p( Path, CP + HS), Frontier1,
[ t( S, S1, T1, C1)| Ts], Frontier2)
/* Head t(..) wird in Frontier1 eingefügt => NewFrontier */
:-
h( S1, H1),
CP1 is CP + C1,
insert( p( [ T1 -> S1| Path], CP1 + H1), Frontier1, NewFrontier),
update_frontier( p( Path, CP + HS), NewFrontier, Ts, Frontier2).
update_frontier( P, Frontier, [], Frontier).
next_state( S, S1, T1, C, Visited) :-
t( S, S1, T1, C),
not member( S1, Visited).
insert( X, [], [X]).
insert( X, [ X1 | Xs], [ X, X1 | Xs]) :-
cost( X, C),
cost( X1, C1),
C =< C1,
!.
insert( X, [ X1 | Xs], [ X1 | Xs1]) :-
insert( X, Xs, Xs1).
cost( X, C) :-
X = p( P, CP + H),
C is CP + H,
!.
6.2Andere Lösungsmethoden
Generate and Test
Eine mögliche Lösung wird geraten und dann auf Korrektheit getestet. Obwohl die Generierung der möglichen Lösungen durch eine Suche im Zustandsraum erfolgen kann, steht der Lösungsweg nicht im Vordergrund. Prolog-Formulierung (Ausnützung des Backtrackings):
solve( Problem, Solution) :-
generate( Problem, Solution),
test( Solution).
Rekursion
Das Problem wird auf ein einfacheres, gleich strukturiertes Problem zurückgeführt.
Beispiel: Die Türme von Hanoi.
In einem Kloster bei Hanoi lösen Mönche seit der Weltentstehung eine Aufgabe, die ihnen von Gott gestellt wurde: Es gibt drei Stäbe. Auf dem ersten Stab sind 64 verschieden grosse Ringe der Grösse nach geordnet (grosse Ringe unten). Die Mönche sollen die Ringe auf den zweiten Stab bringen - unter Zuhilfenahme des dritten Stabes -, sodass sie wieder gleich geordnet sind. Man darf immer nur einen Ring bewegen, und nur einen kleineren auf einen grösseren legen. [Die beste Lösung benötigt 264 - 1 Bewegungen; ihre Ausführung braucht 264 sec, wenn eine Bewegung 1 sec dauert. Das Alter des Universums ist 258 sec, die Lebenzeit des geschlossenen Universums ist 261 sec. Die Mönche müssen sich beeilen!]
Fig. 6.3: Die Türme von Hanoi
Lösung im Zustandsraum (ungeeignet): Zustände sind alle legalen Positionen, Transitionen sind alle legalen Bewegungen; keine Strategie, keine Struktur.
Lösung durch Rekursion (geeignet):
Schematische Darstellung der Aufgabe ist "hanoi( N, p -> q, r)", für N Ringe und die Überführung vom Stab p nach Stab q mit Hilfe vom Stab r. Rekursive Überlegung: hanoi( N-1, p -> r, q), dann hanoi( 1, p -> q, _), dann hanoi( N-1, r -> q, p)
hanoi( N, move( P, Q), using (R)) :-
N > 0, N1 is N - 1,
hanoi( N1, move( P, R), using (Q)),
write( move( from( P), to( Q)), /* hanoi( 1, p -> q, _) */
hanoi( N1, move( R, Q), using (P)).
hanoi( 0, move( P, Q), using( R)).
Und-Zerlegung in Teilprobleme
Das Problem wird in mehrere einfachere Probleme zerlegt, die alle gelöst werden müssen. Meistens sind die Teilprobleme voneinander abhängig, sodass sie mit üblichen sequentiellen Methoden nicht ohne weiteres gelöst werden können. Im Prolog ist die "Und-Zerlegung" dagegen sehr einfach: die Abhängigkeit unter den Teilproblemen wird durch Variablensharing automatisch berücksichtigt. Beispiel:
solve( Problem, Solution) :-
solve1( Problem1, X, X1), solve2( Problem2, X, X2),
compose(X, X1, X2, Solution).