%% ------------------------------------------------------------------
%%  Datei:  vs.pl  (= a6.pl)
%%  Datum:  1998/06/16
%%
%%  Einfache Implementation der Versionenraummethode (Version Space).
%%
%%  Autor:        Thorsten Joachims,  05.06.1997
%%  Modifiziert:  Ralf Klinkenberg,   16.06.1998
%% ------------------------------------------------------------------
%%
%%  Nur bei Quintus-Prolog benoetigt, bei SWI-Prolog auskommentieren:

:- use_module(library(basics)).
:- use_module(library(lists)).
:- use_module(library(sets)).

:- ensure_loaded(library(print_chars)).

%% ------------------------------------------------------------------
%%
%%  Spezifikation der hierarchischen Wertebereiche der vier Attribute
%%  'wetter', 'lufttemperatur', 'wassertemperatur' und 'wind':
%%
%%	wetter:  ? --+--> trocken --+--> sonnig
%%		     |		    +--> bewoelkt
%%		     |
%%		     +--> nicht_trocken --> regen
%%
%%	lufttemperatur,
%%	wassertemperatur:  ? --+--> niedrig --+--> kalt
%%			       |	      +--> kuehl
%%			       |
%%			       +--> hoch --+--> warm
%%					   +--> heiss
%%
%%	wind:  ? --+--> nein
%%		   +--> ja --+--> schwach
%%			     +--> stark
%%			     +--> stuermisch
%%
%%  'isa(A,W1,W2)' ist wahr, wenn fuer Attribute 'A' der Wert 'W2'
%%  den Wert 'W1' subsumiert (also wenn 'W2' genereller als 'W1' ist),
%%  und 'W1' direkter Vorgaenger von 'W2' in der Wertebereichsstruktur ist.

isa(wetter,trocken,x).
isa(wetter,nicht_trocken,x).
isa(wetter,sonnig,trocken).
isa(wetter,bewoelkt,trocken).
isa(wetter,regen,nicht_trocken).

isa(lufttemperatur,niedrig,x).
isa(lufttemperatur,hoch,x).
isa(lufttemperatur,kalt,niedrig).
isa(lufttemperatur,kuehl,niedrig).
isa(lufttemperatur,warm,hoch).
isa(lufttemperatur,heiss,hoch).

isa(wassertemperatur,niedrig,x).
isa(wassertemperatur,hoch,x).
isa(wassertemperatur,kalt,niedrig).
isa(wassertemperatur,kuehl,niedrig).
isa(wassertemperatur,warm,hoch).
isa(wassertemperatur,heiss,hoch).

isa(wind,nein,x).
isa(wind,ja,x).
isa(wind,schwach,ja).
isa(wind,stark,ja).
isa(wind,stuermisch,ja).

%% ------------------------------------------------------------------
%%
%%  Definition der Vorgaenger-Relation 'pre':
%%    'pre(A,W1,W2)' ist wahr, wenn fuer Attribute 'A' der Wert 'W1'
%%    den Wert 'W2' subsumiert (also wenn 'W1' genereller als 'W2' ist),
%%    egal ob 'W1' direkter oder indirekter Vorgaenger von 'W2' in der 
%%    Wertebereichsstruktur ist.

pre(_,X,X).
% pre(A,X,Y) :- isa(A,Y,X).
pre(A,X,Y) :- isa(A,Y,Z),pre(A,X,Z).

%% ------------------------------------------------------------------
%%
%%  'covers(T1,T2)' ist wahr, wenn Term 'T1' den Term (oder das Beispiel)
%%  'T2' abdeckt (also genereller ist):

covers([A=W1],[A=W2]) :- pre(A,W1,W2).
covers([A=W1|C],[A=W2|E]) :- pre(A,W1,W2),covers(C,E).

%% ------------------------------------------------------------------
%%
%%  Generalisierung /Spezialisierung eines Konzeptes 'C' mit Hilfe eines
%%  Beispiels 'Ex' zu 'Cneu':

generalisiere_schritt(C,Ex,Cneu) :-
	covers(Cneu,Ex),
	covers(Cneu,C),
	\+ (covers(Cneu,Other),
	    \+ Cneu=Other,
	    covers(Other,Ex),
	    covers(Other,C)).

spezialisiere_schritt(C,Ex,Cneu) :-
	covers(C,Cneu),
	\+ covers(Cneu,Ex),
	\+ (covers(Other,Cneu),
	    \+ Cneu=Other,
	    \+ covers(Other,Ex),
	    covers(C,Other)).

%% ------------------------------------------------------------------
%%
%%  Versionenraum-Hauptprogramm:
%%    Loesung gefunden, wenn die Mengen 'S' (speziellste gueltige Hypothesen)
%%    und 'G' (generellste gueltige Hypothesen) in einer einelementigen
%%    Menge zusammenfallen, die dann die eindeutige Loesung enthaelt.

vs(G,S,Erg) :- length(G,1),S=G,Erg=G.

%%    Einlesen und verarbeiten eines Beispiels je Aufrufebene:

vs(G,S,Erg) :-
	read_example(E,Klasse),
	((Klasse = positiv,lerne_pos_beispiel(G,S,E,G1,S1));
	 (Klasse = negativ,lerne_neg_beispiel(G,S,E,G1,S1))),
	entferne_g_spezieller_als_s(G1,S1,Gneu),
	entferne_s_genereller_als_g(G1,S1,Sneu),
	write(Gneu),nl,write(Sneu),nl,nl,
	vs(Gneu,Sneu,Erg).

%%  Einlesen eines Beispiels und seiner Klassifikation:

read_example(E,K) :-
	write('Beispiel: '),
	read(E),
	write('Klasse: '),
	read(K).

%%  Lerne aus einem positiven Beispiel 'E' durch Aktualisieren der 
%%  Mengen 'S' und 'G' in 'Sneu' und 'Gneu':

lerne_pos_beispiel(G,S,E,Gneu,Sneu) :-
	entferne_uncovered(G,E,Gneu),
	generalisiere_schritt_alle(S,E,S1),
	entferne_zu_generelle(S1,Sneu).

entferne_uncovered([],_,[]).
entferne_uncovered([C|G],E,[C|Gneu]) :-
	covers(C,E),
	entferne_uncovered(G,E,Gneu).
entferne_uncovered([C|G],E,Gneu) :-
	\+ covers(C,E),
	entferne_uncovered(G,E,Gneu).

generalisiere_schritt_alle([],_,[]).
generalisiere_schritt_alle([C|S],E,Sneu) :-
	findall(Cneu,
	        generalisiere_schritt(C,E,Cneu),
		Sneu1),
	generalisiere_schritt_alle(S,E,Sneu2),
	append(Sneu1,Sneu2,Sneu).

entferne_zu_generelle(S,Sneu) :-
	findall(C1,
	        (member(C1,S),
		 \+ (member(C2,S),
		     \+ C1=C2,
		     covers(C1,C2))),
		Sneu).

%%  Lerne aus einem negativen Beispiel 'E' durch Aktualisieren der 
%%  Mengen 'S' und 'G' in 'Sneu' und 'Gneu':

lerne_neg_beispiel(G,S,E,Gneu,Sneu) :-
	entferne_covered(S,E,Sneu),
	spezialisiere_schritt_alle(G,E,G1),
	entferne_zu_spezielle(G1,Gneu).

entferne_covered([],_,[]).
entferne_covered([C|S],E,[C|Sneu]) :-
	\+ covers(C,E),
	entferne_covered(S,E,Sneu).
entferne_covered([C|S],E,Sneu) :-
	covers(C,E),
	entferne_covered(S,E,Sneu).

spezialisiere_schritt_alle([],_,[]).
spezialisiere_schritt_alle([C|G],E,Gneu) :-
	findall(Cneu,
	        spezialisiere_schritt(C,E,Cneu),
		Gneu1),
	spezialisiere_schritt_alle(G,E,Gneu2),
	append(Gneu1,Gneu2,Gneu).

entferne_zu_spezielle(G,Gneu) :-
	findall(C1,
	        (member(C1,G),
		 \+ (member(C2,G),
		     \+ C1=C2,
		     covers(C2,C1))),
		Gneu).

%%  Entferne aus 'G' alle 'g', fuer die es kein 's' aus 'S' gibt, das
%%  spezieller als 'g' ist, und speichere das Ergebnis in 'Gneu':

entferne_g_spezieller_als_s(G,S,Gneu) :-
	findall(C1,
	        (member(C1,G),
		 member(C2,S),
		 covers(C1,C2)),
		G1),
	remove_dups(G1,Gneu).

%%  Entferne aus 'S' alle 's', fuer die es kein 'g' aus 'G' gibt, das
%%  genereller als 's' ist, und speichere das Ergebnis in 'Sneu':

entferne_s_genereller_als_g(G,S,Sneu) :-
	findall(C2,
	        (member(C2,S),
		 member(C1,G),
		 covers(C1,C2)),
		S1),
	remove_dups(S1,Sneu).

%%  Anmerkung:  'remove_dups(-Liste,+Menge)' ist eine Bibliotheksfunktion
%%		von Quintus-Prolog, die die Liste 'Liste' in eine Menge
%%		('Menge') transformiert, indem es doppelte Elemente entfernt
%%		und die verbleibenden Elemente in der Liste lexikographisch
%%		sortiert.

%% ------------------------------------------------------------------
%%
%%  Testlauf mit Beispielen in Originalreihenfolge:
%%  -----------------------------------------------
%%  ?- ['vs.pl'].
%%  yes
%%
%%  %% Versionenraum-Initialisierung mit 'G' als einelementiger Menge mit der
%%  %% allgemeinsten Bedingung (alle Attribute beliebig ('x') belegt) und mit
%%  %% dem ersten (positiven) Beispiel als speziellste Hypothese (da jede
%%  %% Hypothese alle positiven Beispiele abdecken muss, also auch das erste):
%%
%%  ?- vs([[wetter=x,lufttemperatur=x,wassertemperatur=x,wind=x]],
%%        [[wetter=sonnig,lufttemperatur=kuehl,wassertemperatur=kalt,wind=stark]],
%%        Loesung).
%%
%%  %% Eingabe des zweiten Beispiels:
%%
%%  Beispiel: [wetter=regen,lufttemperatur=warm,wassertemperatur=x,wind=stark].
%%  Klasse:   negativ.
%%
%%  G = [[wetter=trocken,lufttemperatur=x,wassertemperatur=x,wind=x],
%%       [wetter=x,lufttemperatur=niedrig,wassertemperatur=x,wind=x],
%%       [wetter=x,lufttemperatur=x,wassertemperatur=niedrig,wind=x]]
%%  S = [[wetter=sonnig,lufttemperatur=kuehl,wassertemperatur=kalt,wind=stark]]
%%
%%  %% Eingabe des dritten Beispiels:
%%
%%  Beispiel: [wetter=sonnig,lufttemperatur=heiss,wassertemperatur=x,wind=stark].
%%  Klasse:   positiv.
%%
%%  G = [[wetter=trocken,lufttemperatur=x,wassertemperatur=x,wind=x]]
%%  S = [[wetter=sonnig,lufttemperatur=x,wassertemperatur=x,wind=stark]]
%%
%%  %% Eingabe des vierten Beispiels:
%%
%%  Beispiel: [wetter=sonnig,lufttemperatur=x,wassertemperatur=warm,wind=nein].
%%  Klasse:   negativ.
%%
%%  G = [[wetter=trocken,lufttemperatur=x,wassertemperatur=x,wind=ja]]
%%  S = [[wetter=sonnig,lufttemperatur=x,wassertemperatur=x,wind=stark]]
%%
%%  %% Eingabe des fuenften Beispiels:
%%
%%  Beispiel: [wetter=bewoelkt,lufttemperatur=x,wassertemperatur=warm,wind=schwach].
%%  Klasse:   positiv.
%%
%%  G = [[wetter=trocken,lufttemperatur=x,wassertemperatur=x,wind=ja]]
%%  S = [[wetter=trocken,lufttemperatur=x,wassertemperatur=x,wind=ja]]
%%
%%  Loesung = [[wetter=trocken,lufttemperatur=x,wassertemperatur=x,wind=ja]]
%%
%% ------------------------------------------------------------------
%%
%%  Testlauf mit Beispielen in guenstigerer Reihenfolge:
%%  ----------------------------------------------------
%%  ?- ['vs.pl'].
%%  yes
%%
%%  %% Start mit dem 1. Beispiel:
%%
%%  ?- vs([[wetter=x,lufttemperatur=x,wassertemperatur=x,wind=x]],
%%        [[wetter=sonnig,lufttemperatur=kuehl,wassertemperatur=kalt,wind=star!
%%        Loesung).
%%
%%  %% Eingabe des 2. Beispiels:
%%
%%  Beispiel: [wetter=regen,lufttemperatur=warm,wassertemperatur=x,wind=stark].
%%  Klasse:   negativ.
%%
%%  G = [[wetter=trocken,lufttemperatur=x,wassertemperatur=x,wind=x],
%%       [wetter=x,lufttemperatur=niedrig,wassertemperatur=x,wind=x],
%%       [wetter=x,lufttemperatur=x,wassertemperatur=niedrig,wind=x]]
%%  S = [[wetter=sonnig,lufttemperatur=kuehl,wassertemperatur=kalt,wind=stark]]
%%
%%  %% Eingabe des 5. Beispiels:
%%
%%  Beispiel: [wetter=bewoelkt,lufttemperatur=x,wassertemperatur=warm,wind=schwach].
%%  Klasse:   positiv.
%%
%%  G = [[wetter=trocken,lufttemperatur=x,wassertemperatur=x,wind=x]]
%%  S = [[wetter=trocken,lufttemperatur=x,wassertemperatur=x,wind=ja]]
%%
%%  %% Eingabe des 4. Beispiels:
%%
%%  Beispiel: [wetter=sonnig,lufttemperatur=x,wassertemperatur=warm,wind=nein].
%%  Klasse:   negativ.
%%
%%  G = [[wetter=trocken,lufttemperatur=x,wassertemperatur=x,wind=ja]]
%%  S = [[wetter=trocken,lufttemperatur=x,wassertemperatur=x,wind=ja]]
%%
%%  Loesung = [[wetter=trocken,lufttemperatur=x,wassertemperatur=x,wind=ja]] 
%%
%%
%%  Das letzte Beispiel (Beispiel Nr. 3) wird nicht mehr gebraucht, da
%%  bereits nach den ersten vier Beispielen (Beispiele Nr. 1, 2, 5, 4)
%%  die Loesung eindeutig bestimmt worden ist.
%%
%% ------------------------------------------------------------------