Künstliche Intelligenz und Prolog
Copyright © 2019 Jiri Kriz, www.nosco.ch

7    Problemlösung

Lösung der Aufgaben

7.1    Autofahren in der Schweiz (Graphensuche durch Prolog-Beweiser)

strasse( zuerich,    baden,     a, 22).
strasse( baden,      basel,     s, 83).
strasse( zuerich,    rotkreuz,  s, 39).
strasse( baden,      olten,     a, 43).
strasse( olten,      bern,      a, 67).
strasse( olten,      luzern,    a, 57).
strasse( olten,      basel,     a, 39).
strasse( rotkreuz,   luzern,    a, 18).
strasse( rotkreuz,   schwyz,    a, 26).
strasse( luzern,     altdorf,   a, 39).
strasse( schwyz,     altdorf,   s, 16).

tr( X, Y) :- 
    strasse( X, Y, _, _).
tr( X, Y) :- 
    strasse( Y, X, _, _).

distance( X, Y, L) :- 
    strasse( X, Y, _, L), !.
distance( X, Y, L) :- 
    strasse( Y, X, _, L).

path( Start, Start, Weg, Weg).
path( X, Y, Teilweg, Weg):- 
    tr( X, Z), 
    not( member( Z, Teilweg)), 
    path( Z, Y, [ Z| Teilweg], Weg).

weg( Start, Ziel, Weg, Laenge) :- 
    path( Start, Ziel, [ Start], Rueckweg),
    revl( Rueckweg, Weg, Laenge).

revl( [ X1| Xs], Y, L) :- 
    revl( Xs, [ X1], Y, 0, L).        

revl( [ X1| Xs], [ Y1| Ys], Y, L0, L) :- 
    distance( X1, Y1, DXY),
    L1 is L0 + DXY,
    revl( Xs, [ X1, Y1| Ys], Y, L1, L).
revl( [], Y, Y, L, L).

/* General problem solving: forward, depth-first */
/* Transitions: move( State, NewState, Transition_name) */
/* Start = initial state;  Goal = goal state */

solve( Start, Path) :- 
    solve( Start, [Start], Path).

solve( Goal, Visited, []) :- 
    goal( Goal).
solve( State, Visited, [ T| Path]):- 
    move( State, NewState, T), 
    not member( NewState, Visited),
    solve( NewState, [ NewState | Visited], Path).

write_list( []).
write_list( [ X1| Xs]) :- 
    nl, 
    write( X1), 
    write_list( Xs).

backtrack :- 
    nl, nl, 
    write( 'Further solutions? [y/n]: '), 
    read( A), (A = n ; A = no).

Back to example 7.1

7.2    Zwei Kanister

kanister :- 
    solve( k( 0, 0), Path), 
    nl, write_list( Path), 
    backtrack.

goal( k( 4, _)).

move( k( X, Y), k( 7, Y), 
    a( 'fill C7', state_c7( 7))).          
move( k( X, Y), k( X, 5),
    a( 'fill C5', state_c7( X))).
move( k( X, Y), k( 0, Y), 
    a( 'empty C7', state_c7( 0))).
move( k( X, Y), k( X, 0), 
    a( 'empty C5', state_c7( X))).

move( k( X, Y), k( 0, Y1), 
    a( 'empty C7 into C5', state_c7( 0))) :- 
    Y1 is Y + X, Y1 =< 5. 
move( k( X, Y), k( X1, 5), 
    a( 'fill C5 from C7', state_c7( X1))) :- 
    X1 is X + Y - 5, X1 >= 0. 
move( k( X, Y), k( X1, 0), 
    a( 'empty C5 into C7', state_c7( X1))) :- 
    X1 is X + Y, X1 =< 7.
move( k( X, Y), k( 7, Y1), 
    a( 'fill C7 from C5', state_c7( 7))) :- 
    Y1 is X + Y - 7, Y1 >= 0.

Back to example 7.2

7.3    Flussüberquerung

fluss :- 
    start_fl( Start), 
    solve( Start, Path), 
    nl, write_list( Path), 
    backtrack.

start_fl( 
f( bauer( L), schaf( L), ziege( L), heu( L))) 
:- 
    L = ufer1.

goal( 
f( bauer( R), schaf( R), ziege( R), heu( R))) 
:- 
    R = ufer2.

move( 
f( bauer( B), schaf( S),  
ziege( Z), heu( H)),
f( bauer( B1), schaf( S1), 
ziege( Z1), heu( H1)),
fahrt( von( B), nach( B1), mit( P))) 
:-
    ueber( B, B1),
    ( P = schaf, S = B, S1 = B1, Z1 = Z, H1 = H  ;
    P = ziege, Z = B, S1 = S, Z1 = B1, H1 = H  ;
    P = heu, H = B, S1 = S, Z1 = Z,  H1 = B1 ;
    P = nichts, S1 = S, Z1 = Z, H1 = H ),
    sicher( bauer( B1), schaf( S1), ziege( Z1), heu( H1)).

ueber( ufer1, ufer2).
ueber( ufer2, ufer1).

sicher( bauer( B), schaf( S), ziege( Z), heu( B)).
sicher( bauer( _), schaf( B), ziege( B), heu( H)) :- 
    ueber( B, H).

Back to example 7.3

7.4    Roboter

roboter :- 
    roboter0( Start), 
    solve( Start, Path), 
    write_list( Path), 
    backtrack.

roboter0( 
r( roboter( an_tuer, auf_boden), rampe( am_fenster), ventil( offen))).

goal( 
r( Roboter, Rampe, ventil( geschlossen))).

move( 
r( roboter( X, auf_boden), R, V), 
r( roboter( Y, auf_boden), R, V), 
laufe_nach( Y)) 
:- 
    position( Y), X \= Y.

move( 
r( roboter( X, auf_boden), rampe( X), V),
r( roboter( Y, auf_boden), rampe( Y), V), schiebe_nach( Y)) 
:- 
    position( Y), X \= Y.
    
move( 
r( roboter( X, auf_boden), rampe( X), V),
r( roboter( X, auf_rampe), rampe( X), V), 
steige_hinauf).

move( 
r( roboter( X, auf_rampe), rampe( X), V),
r( roboter( X, auf_boden), rampe( X), V), 
steige_hinunter).

move( 
r( roboter( in_ecke, auf_rampe), R, ventil( offen)),
r( roboter( in_ecke, auf_rampe), R, ventil( geschlossen)), 
schliesse).

move( 
r( roboter( in_ecke, auf_rampe), R, ventil( geschlossen)),
r( roboter( in_ecke, auf_rampe), R, ventil( offen)), 
oeffne).

position( an_tuer).
position( am_fenster).
position( in_ecke).

Back to example 7.4