3 Suche

Aufgabe 3.7

Im folgenden beziehen wir uns in unserer Notation auf PROLOG und unser Suchprogramm.

Bitte probieren Sie es zunächst allein! Wenn Sie nicht zurecht kommen, dann lesen Sie bitte die Lösung nach und nach !!

Zunächst muss man sich über die Datenstrukturen Gedanken machen. Wie stellt man das Schiebefax dar ? Am besten durch eine Matrix:

     *********       Diese Position kann dargestellt werden durch:
   3 * 1 2 3 *
   2 * 8   4 *       [2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2]
   1 * 7 6 5 *
     ********* 
       1 2 3

Was sind zulässige Zustandsübergänge? Die Position des Leerfeldes steht vorn. Wir müssen ein passendes Feld finden. Dies muss bez. der Manhatten-Distanz exakt 1 entfernt sein:

zustandsuebergang(Alt,Neu) :- s(Alt,Neu,_).

% s( Node, SuccessorNode, Cost) ... s vereinigt Zustandsuebergang und Kosten
s([Empty | Tiles], [Tile | Tiles1], 1):-    % Alle Kosten sind 1.
    tausche( Empty, Tile, Tiles, Tiles1).   % Tausche Leerfeld und ein passendes

tausche(Empty, Tile, [Tile | Ts], [Empty | Ts]) :- manhatten( Empty, Tile, 1).
tausche(Empty, Tile, [T1 | Ts], [T1 | Ts1]):- tausche( Empty, Tile, Ts, Ts1).

manhatten(X/Y, X1/Y1, D):-
      dif(X, X1, Dx),  dif(Y, Y1, Dy),
      D is Dx + Dy.
dif(A, B, D):- D is A-B, D >= 0,!    ;     D is B-A.

Die Kosten haben wir damit auch gleich berechnet, jeder Zug kostet 1.

Wie kann man nun die Entfernung zum Ziel berechnen? Hier bietet sich zB an, für alle Felder zu berechnen, wie weit sie von ihrem Zielplatz entfernt sind. Diese Entfernung summiert man.

dist_goal(S,D) :- h(S,D).

h([Empty | Tiles], D):-
      ziel_erreicht( [Empty1 | GoalSquares]),
      totdist(Tiles, GoalSquares, D).

totdist([], [], 0).
totdist([Tile | Tiles], [Square | Squares], D):-
      manhatten( Tile, Square, D1),
      totdist( Tiles, Squares, D2),
      D is D1 + D2.

Aufgabe 3.10

Im folgenden beziehen wir uns in unserer Notation auf PROLOG und unser Suchprogramm.

Bitte probieren Sie es zunächst allein! Wenn Sie nicht zurecht kommen, dann lesen Sie bitte die Lösung nach und nach !!

Zunächst muss man sich über die Datenstrukturen Gedanken machen. Wie stellt man den Kaefig dar ? Man braucht nur die existierenden Türen:

tuer(loewe,esel). 
tuer(esel,wolf). 
tuer(wolf,krokodil). 
tuer(krokodil,panther).
tuer(loewe,aussen). 
tuer(esel,aussen). 
tuer(wolf,aussen).
tuer(krokodil,aussen). 
tuer(panther,aussen).

Durch kaefig(loewe,panther) beschreibt man, dass der Panther im Löwe-Käfig ist.

Wodurch sind Start-/Zielzustand beschrieben?

startzustand([kaefig(loewe,panther), kaefig(esel,krokodil),
                 kaefig(wolf,esel), kaefig(krokodil,loewe),
                 kaefig(panther,wolf),kaefig(aussen,leer)]).
ziel_erreicht(Z) :- member(kaefig(X,Y),Z),X\=Y,X\=aussen,!,fail.
ziel_erreicht(_).

Wie sieht ein zulässiger Zustandsübergang aus?

zustandsuebergang(Alt,Neu) :-
        member(kaefig(Y,leer),Alt),
        (tuer(X,Y);tuer(Y,X)),
        member(kaefig(X,T),Alt),
        replace(kaefig(X,T),kaefig(X,leer),Alt,N1),
        replace(kaefig(Y,leer),kaefig(Y,T),N1,Neu).

replace(X,Y,[X|T],[Y|T]) :- !.
replace(X,Y,[F|T],[F|T1]) :- replace(X,Y,T,T1).

Die Kosten für ein Umsetzen: costs(_,_,1)..

Für die geschätzte Entfernung zum Ziel gibt es mehrere Varianten. Hier die Variante, wo man einfach die falsch besetzten Käfige zählt.

dist_goal(Zustand,M) :- zaehle_falsche(Zustand,0,M).

zaehle_falsche([],N,N) :- !. 
zaehle_falsche([kaefig(X,X)|T],N,N1) :- !, 
        zaehle_falsche(T,N,N1). 
zaehle_falsche([kaefig(aussen,leer)|T],N,N1) :- 
        zaehle_falsche(T,N,N1). 
zaehle_falsche([_|T],N,N1) :- !,N2 is N+1, 
        zaehle_falsche(T,N2,N1).

Hier noch ein Prädikat zum Anzeigen der Käfige:

zeige_kandidat([]) :- !.
zeige_kandidat([F|T]) :- zeige_kandidat(T),write(' * '),zeige_zustand(F).
zeige_zustand([kaefig(_,F)]) :- !,write(F).
zeige_zustand([kaefig(_,F)|T]) :- write(F),write('-'),zeige_zustand(T).
zustaende_gleich(F,F).

Aufgabe 3.13

Im folgenden beziehen wir uns in unserer Notation auf PROLOG und unser Suchprogramm.

Wir diskutieren dieses Problem am besten an einem Beispiel:

Jemand möchte einen Rucksack so bepacken, dass er einen höchstmöglichen Wert enthält. Zur Verfügung stehen einige Gegenstände. Jeder Gegenstand hat ein Gewicht. Jeder Gegenstand hat einen Wert.

Die Gegenstände spezifizieren wir in einer geeigneten Datenstruktur. Wir geben gleich ihr Gewicht und ihren Wert an:

gegenstand(maske,6,9).
gegenstand(kupfer,7,10).
gegenstand(amulett,5,14).
gegenstand(schnaps,8,11).
gegenstand(zigaretten,5,8).
gegenstand(schmetterlinge,3,8).

Zu Beginn haben wir keinen Gegenstand im Rucksack.

startzustand([]).

Der Rucksack verträgt ein Maximalgewicht von zB 20:

maximum(20).

Wie sieht ein zulässiger Zustandsübergang aus? Wir packen einen weiteren Gegenstand in den Rucksack:

zustandsuebergang(Alt,[G|Alt]) :-
        gegenstand(G,Gewicht,Wert),
        not member(G,Alt),
        kosten([G|Alt],Kosten),maximum(Max),Kosten =< Max.

kosten([],0) :- !.
kosten([F|Rest],S) :- kosten(Rest,S1),gegenstand(F,Kosten,_),!,S is Kosten+S1.

Die Kosten für das Hinzunehmen eines Gegenstands entsprechen exakt dem Gewicht:

costs(_,[G|_],Gewicht) :- gegenstand(G,Gewicht,_).

So weit so gut. Aber wie formulieren wir ein Ziel? Wir kennen das Maximum, was möglich ist, nicht. Also greifen wir zu einem Trick. Wir formulieren zunächst, dass wir uns umso näher am Ziel befinden, je größer der Wert ist. Da wir in den Suchproblemen immer Richtung Null wollten, müssen wir den Abstand zum Ziel zB wie folgt definieren:

dist_goal(Zustand,M) :-
        wert(Zustand,Wert),M is 100-Wert.

wert([],0) :- !.
wert([F|Rest],S) :- wert(Rest,S1),gegenstand(F,_,Wert),!,S is Wert+S1.

Und das Ziel? Wir kennen es nicht. Also lassen wir den Suchalg. einfach loslaufen, ohne dass er aufhören darf. Wir formulieren also ein unerfüllbares Ziel:

ziel_erreicht(hh).

Zum Schluss noch die Prädikate für das Anzeigen:

zeige_kandidat([]) :- !.
zeige_kandidat([F|T]) :- zeige_kandidat(T),write(' * '),zeige_zustand(F).
zeige_zustand([]) :- !.
zeige_zustand([F|T]) :- write(F),write('-'),zeige_zustand(T).

Ganz wichtig: Wann sind 2 Zustände gleich? Wenn im Rucksack die gleichen Gegenstände sind: Der Inhalt muss also nur mengenmäßig gleich sein.

zustaende_gleich(T,T1) :- sub(T,T1), sub(T1,T).

sub(X,Rest) :- member(F,X),not(member(F,Rest)),!,fail.
sub(_,_).

Aufgabe 3.14

Im folgenden beziehen wir uns in unserer Notation auf PROLOG und unser Suchprogramm.

Es gibt mehrere Varianten, die Distanz zum Ziel zu definieren:

Aufgabe 3.14 - Variante 1
Suchen des linkesten weissen Steins, Summieren der Abstaende zwischen den Positionen der schwarzen Steine rechts von dem weissen Stein + Zaehlen des Abstandes der schwarzen Steine von ihren korrekten Positionen

dist_goal1(State,Dist):-
        positionweisslinks(State,Pos),
        addiere(State,Pos,Pos,0,Zahl),
        zaehleschwarz(State,X),
        Dist is X+Zahl.

positionweisslinks(State,Pos) :- member(w,State,Pos),!. /* Bestimme linken weissen Stein */

addiere(State,Pos,Vergl,Accu,Zahl) :-
        member(s,State,P1),
        P1 > Vergl,
        Diff is P1-Pos,
        Accu1 is Accu+Diff,!,
        addiere(State,Pos,P1,Accu1,Zahl).
addiere(State,Pos,Corr,Accu,Accu).

zaehleschwarz(State,X) :-
        member(s,State,N1),A is N1-1,
        member(s,State,N2),N2>N1,B is N2-2,
        member(s,State,N3),N3>N2,C is N3-3,
        X is A+B+C,!.

Aufgabe 3.14 - Variante 2
Anzahl der falschen Steine

dist_goal2(State,Dist):- vergleiche(State,[s,s,s,' ',w,w,w],0,Dist).

vergleiche([],_,N,N) :- !.
vergleiche([F|T],[F|T2],N,N1) :- !,vergleiche(T,T2,N,N1).
vergleiche([_|T],[_|T2],N,N1) :- N2 is N+1,vergleiche(T,T2,N2,N1).

Aufgabe 3.14 - Variante 3
Suchen des linkesten weissen Steins, Summieren der Abstaende zwischen den Positionen der schwarzen Steine rechts von dem weissen Stein

dist_goal3(State,Dist):-
        positionweisslinks(State,Pos),
        addiere(State,Pos,Pos,0,Dist).

positionweisslinks(State,Pos) :- member(w,State,Pos),!. /* Bestimme linken weissen Stein */

addiere(State,Pos,Vergl,Accu,Zahl) :-
        member(s,State,P1),
        P1 > Vergl,
        Diff is P1-Pos,
        Accu1 is Accu+Diff,!,
        addiere(State,Pos,P1,Accu1,Zahl).
addiere(State,Pos,Corr,Accu,Accu).

Aufgabe 3.14 - Variante 4
Zaehlen des Abstandes der schwarzen Steine von ihren korrekten Positionen

dist_goal4(State,Dist) :- zaehleschwarz(State,Dist).

zaehleschwarz(State,X) :-
        member(s,State,N1),A is N1-1,
        member(s,State,N2),N2>N1,B is N2-2,
        member(s,State,N3),N3>N2,C is N3-3,
        X is A+B+C,!.


Zum KI-Buch
J. Cleve - Email : juergen.cleve@hs-wismar.de

2016-01-30