DE → EN A-AA+ Inhalt Suche

# 7    Problemlösung

## 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