Musterlösung Blatt 2, Aufgaben 2.1 a und 2.2 a
Aufgabe 2.1 a
% D aus ziffernliste ziehen falls D noch nicht gebunden,
% (ggf.) verminderte Ziffernliste zurueckgeben
% D schon gebunden: cut
bind(D, Avail, Avail) :- nonvar(D), !.
% D kann erste ziffer sein...
bind(D, [D|T], T), !.
% ...oder im rest
bind(D, [H|T1], [H|T2]) :- bind(D, T1, T2).
% sum/5: Eingabe Ziffernliste Summand 1,
% Eingabe Ziffernliste Summand 2,
% Rueckgabe Uebertrag, Rueckgabe Ziffernliste Summe,
% Rueckgabe noch verfuegbare Ziffern
% Rekursionsende: keine Ziffern uebrig. Uebertrag ist 0,
% Summenliste is [], alle Ziffern verfuegbar
sum([],[],0,[],[0,1,2,3,4,5,6,7,8,9]).
% Rekursion und dann fuehrende Ziffer unter beruecksichtigung
% der verfuegbaren Ziffern und des Uebertrages summieren
sum([H1|T1], [H2|T2], C, [H3|T3], Avail3) :-
sum(T1, T2, CA, T3, Avail0),
bind(H1, Avail0, Avail1),
bind(H2, Avail1, Avail2),
bind(H3, Avail2, Avail3),
H3 is (H1+H2+CA) mod 10,
C is (H1+H2+CA) // 10.
% convenience-praedikat sum/3 auf sum/5 abbilden
sum([H1|T1], [H2|T2], [H3|T3]) :- sum([H1|T1], [H2|T2], H3, T3, _),
H1 =\= 0, H2 =\= 0, H3 =\= 0.
% sum([S,E,N,D],[M,O,R,E],M,[O,N,E,Y], AVAIL), M =\= 0, S =\=0.
Aufgabe 2.2 a
%% Bibliotheken fuer Listenfunktionen und Negation:
:- ensure_loaded(library(basics)).
:- ensure_loaded(library(not)).
%% Praedikat zum Starten des Suchprozesses, das den Start-Spielzustand
%% auf den zugehoerigen Suchraumknoten abbildet, die Suche startet und
%% die Anzahl der zum Erreichen des Ziels benoetigten Expansionen sowie
%% den Suchraumknoten mit der Loesung liefert, der unter anderen den
%% Pfad der Spielzustaende zum Ziel sowie die Kosten dieses Pfades umfasst:
%% start( Startzustand+, Expansionen-, Loesung- )
start(Startzustand,Expansionen,Loesung) :-
suche([pfad(0,0,0,Startzustand,[])],[],0,Expansionen,Loesung).
%% A*-Suche (und Bergsteigen durch Aendern einer Zeile in 'sortiere'):
%% suche( Offen+, Geschlossen+, AnzahlBisherigerExpansionen+,
%% AnzahlExpansionenDerLoesung-, Loesung- )
suche([Aktuell|_],_Geschl,Expansionen,Expansionen,Aktuell) :- ziel(Aktuell).
%% Ende der Suche: Ziel erreicht (aktueller gleich Ziel-Suchraumknoten)
suche([],_Geschl,Expansionen,Expansionen,[]).
%% Ende der Suche: keine Loesung gefunden ('Offen' ist leer und Ziel
%% nicht erreicht).
%% Expandierung des aktuell besten, noch offenen (Suchraum)Zustands
%% (= erstes Element in der 'Offen'-Liste):
suche([Aktuell|Offen],Geschl,Expansionen,ExpansionenErg,Loesung) :-
write(Aktuell),nl,
nachfolger(Aktuell,Geschl,Nachf), %% Ermitteln aller noch zu
%% betrachtenden Nachfolger
sortiere(Offen,Nachf,OffenNeu), %% Aktualisiere sortiere die Vereinigung
%% der Menge offener Knoten und der
%% Menge der aktuellen Nachfolger
ExpansionenNeu is Expansionen+1,
suche(OffenNeu,[Aktuell|Geschl],ExpansionenNeu,ExpansionenErg,Loesung).
%% Bestimme alle noch zu betrachtenden Nachfolger-Suchraum-Zustaende des
%% Suchraum-Zustands mit dem Spielzustand K:
nachfolger(pfad(_,G,_,K,P),Geschl,Nachf) :-
findall(pfad(F1,G1,H1,K1,[K|P]), %% Ermittle alle (Spielzustand-)Nachfolger
(nachf(K,K1,Kosten), %% K1 von K mit realen Kosten des
%% Wegs zu ihnen
bewerte(K1,H1), %% Schaetze Restkosten von K1 aus
%% entsprechend aktueller Heuristik
G1 is G+Kosten, %% Berechne neue reale Kosten
F1 is G1+H1, %% Berechne geschaetzte Gesamtkosten
\+ (member(pfad(_,G2,_,K1,_),Geschl), %% betrachte noch nicht
G1 >= G2)), %% geschlossene Nachfolger
Nachf). %% sowie auch geschlossene,
%% wenn sie jetzt mit
%% kuerzerem realen Weg
%% erreichbar sind
%% Sortierte (Nachfolger)Liste: eine Zeile fuer den A*-Algorithmus
%% (Aufgabe 1.1) und eine Zeile fuer das Bergsteigen (Aufgabe 1.2),
%% d.h. die jeweils andere ist auszukommentieren;
%% die dritte Klausel ist beiden gemein:
%% sortiere( Offen+, Nachfolger+, OffenNeu- )
%%% A*-Algorithmus
best(Offen,Best,Restoffen):-
sort(Offen,[Best | Restoffen]).
%%% Bergsteigen
%%% (nur aktuell bestes Element behalten, den Rest verwerfen)
%best(Offen,Best,[]):-
% sort(Offen,[Best|_]).
%%% Entferne alten Suchraumknoten mit groesseren realen Kosten fuer den
%%% aktuellen Spielraumknoten.
%%% sortiere(+Offen,+Nachfolger,-OffenNeu)
sortiere(Offen,[],[Best | Restoffen]) :- best(Offen,Best,Restoffen).
sortiere(Offen,[pfad(F,G,H,K,P)|Nachf],OffenNeu) :- %% BEIDE Verfahren
( (member(pfad(FAlt,GAlt,HAlt,K,PAlt),Offen),
G < GAlt )=")" -="-"> %% IF
(append(Vor,[pfad(FAlt,GAlt,HAlt,K,PAlt)|Nach],Offen), %% THEN
append(Vor,Nach,Offen2)
)
;
Offen2 = Offen %% ELSE
),
sortiere([pfad(F,G,H,K,P)|Offen2],Nachf,OffenNeu).
% %% Abbildung Problemraum-Zielzustand <-> Spiel-Zielzustand
ziel(pfad(_,_,_,K,_)) :- zielzustand(K).
:-ensure_loaded(library(math)).
%%%%%%%%%%%%%%%%% Modellierung %%%%%%%%%%
% Repraesentation: Liste aus Zeilenindex der
% Leerstelle und drei Unterlisten fuer die
% drei Zeilen, siehe Start-/Zielzustand
% Verschiebungen in einer Zeile
horiz([0, A, B], [A, 0, B]).
horiz([A, 0, B], [0, A, B]).
horiz([A, 0, B], [A, B, 0]).
horiz([A, B, 0], [A, 0, B]).
% Vertikale verschiebungen (2 Zeilen eingabe, 2 Zeilen ausgabe)
vert([0, B, C], [D, E, F], [D, B, C], [0, E, F]).
vert([A, 0, C], [D, E, F], [A, E, C], [D, 0, F]).
vert([A, B, 0], [D, E, F], [A, B, F], [D, E, 0]).
% nachfolgezustaende (horizontale versch.)
nachf([1, A, B, C], [1, X, B, C], 1) :- horiz(A, X).
nachf([2, A, B, C], [2, A, X, C], 1) :- horiz(B, X).
nachf([3, A, B, C], [3, A, B, X], 1) :- horiz(C, X).
% nachfolgezustaende (vertikale versch.)
nachf([1, A1, B1, C], [2, A2, B2, C], 1) :- vert(A1, B1, A2, B2).
nachf([2, A, B1, C1], [3, A, B2, C2], 1) :- vert(B1, C1, B2, C2).
nachf([3, A, B1, C1], [2, A, B2, C2], 1) :- vert(C1, B1, C2, B2).
nachf([2, A1, B1, C], [1, A2, B2, C], 1) :- vert(B1, A1, B2, A2).
% startzustand
startzustand([3, [2, 8, 3], [1, 6, 4], [7, 5, 0]]).
zielzustand([2, [1, 2, 3], [8, 0, 4], [7, 6, 5]]).
% h=0
bewerte(_,0).
% start(X, E, L), startzustand(X), zielzustand(L).