Das Bootstourproblem

Eine Bootsfahrt über Flüsse in Deutschland

Hier noch einmal das eingangs formulierte Bootstourproblem: Kann man von StadtA (z.B. Saarbrücken) aus eine Bootsfahrt nach StadtB (z.B. Köln oder Frankfurt oder Regensburg) machen? Die Bootsfahrt soll dabei nur über Flüsse führen. Wir setzen voraus, dass alle (größeren) Flüsse in Deutschland mit einem kleinen Boot befahrbar sind.

Wir betrachten die folgende Wissensbasis zur Miniwelt "Städten an Flüssen". Beachte, dass hier nur wenige Flüsse und wenige Städte an diesen Flüssen aufgeführt sind. Beachte auch, dass die Mündung eines Flusses in einen anderen Fluss hier immer an einer bestimmten Stadt liegt (z.B. mündet die Saar bei Konz in die Mosel).

% Fakten zu Städten an Flüssen

staedte_am_fluss(mosel, [metz, konz, trier, bernkastel, cochem, koblenz]).
staedte_am_fluss(saar, ['Saarbrücken', saarburg, konz]).
staedte_am_fluss(rhein, [basel, mannheim, mainz, koblenz, 'Köln', 'Düsseldorf']).
staedte_am_fluss(donau, [ulm, ingolstadt, regensburg, wien, budapest]).
staedte_am_fluss(main, [schweinfurt, 'Würzburg', offenbach, frankfurt, mainz]).

Aus der Wissensbasis soll mit Hilfe geeigneter Anfragen ermittelt werden, ob eine Bootsfahrt von StadtA nach StadtB möglich ist. In diesem Fall sollen die Stationen der Bootsfahrt mit bestimmt werden.

Prädikate zur Listenverarbeitung

Zur Bearbeitung des Problems benötigt man eine Reihe von Hilfsprädikaten zur Listenverarbeitung. Die Festlegung dieser Prädikate kann so erfolgen:

% Listenverarbeitung

element(E, [K|R]) :- E = K.
element(E, [K|R]) :- E \== K, element(E, R).

zusammenfuegen([], L, L).
zusammenfuegen([K|R], L, [K|RL]) :- zusammenfuegen(R, L, RL).

letztes_element([E], E).
letztes_element([K|R], E) :- letztes_element(R, E).

mit_letztem_element([], E, [E]).
mit_letztem_element([K|R], E, [K|L]) :- mit_letztem_element(R, E, L).

umkehren([], []).
umkehren([K|R], L) :- umkehren(R, U), mit_letztem_element(U, K, L).

vorletztes_element([E1, E2], E1).
vorletztes_element([K1,K2|R], E) :- vorletztes_element([K2|R], E).

zweites_element([E1, E2|R], E2).

teilliste_bis_element([], Element, []).
teilliste_bis_element([K|R], Element, [Element]) :-
  K = Element.
teilliste_bis_element([K|R], Element, [K|Teilliste]) :-
  K \== Element,
  element(Element, R),
  teilliste_bis_element(R, Element, Teilliste).
teilliste_bis_element([K|R], Element, []) :-
  K \== Element,
  not(element(Element, R)).

teilliste_von_element_bis_element(L, Anfang, Ende, []) :- not(element(Anfang, L)).
teilliste_von_element_bis_element(L, Anfang, Ende, []) :- element(Anfang, L), not(element(Ende, L)).
teilliste_von_element_bis_element([K|R], Anfang, Ende, [K|Teilliste])  :-
  element(Anfang, [K|R]), element(Ende, [K|R]),
  K = Anfang,
  element(Ende, R),
  teilliste_bis_element(R, Ende, Teilliste).
teilliste_von_element_bis_element([K|R], Anfang, Ende, [K])  :-
  element(Anfang, [K|R]), element(Ende, [K|R]),
  K = Anfang,
  not(element(Ende, R)).
teilliste_von_element_bis_element([K|R], Anfang, Ende, Teilliste)  :-
  element(Anfang, [K|R]), element(Ende, [K|R]),
  K \== Anfang,
  element(Anfang, R),
  teilliste_von_element_bis_element(R, Anfang, Ende, Teilliste).

Prädikate zur Bootstourbestimmung

Es ist gar nicht so einfach, Bootstouren auf Flüssen zu ermitteln. Man muss eine Reihe von Fällen und Schwierigkeiten beachten, z.B.:

Liegen Start und Ziel am selben Fluss, oder gelangt man nur über verschiedene Flüsse ans Ziel? Erfolgt die Bootsfahrt flussabwärts oder flussaufwärts oder erst flussabwärts und dann flussaufwärts?

Die folgenden Aufgaben sollen dich schrittweise zur Lösung des Bootstourproblems führen.

Aufgabe 1

Entwickle Fakten und Regeln zur Festlegung des Prädikats liegen_am_selben_fluss_flussabwaerts/2. Der folgende Dialog zeigt das gewünschte Verhalten des liegen_am_selben_fluss_flussabwaerts-Prädikats anhand einiger Anfragebeispiele auf.

?- liegen_am_selben_fluss_flussabwaerts(trier, cochem).

Yes
?- liegen_am_selben_fluss_flussabwaerts(trier, trier).

No
?- liegen_am_selben_fluss_flussabwaerts(trier, mainz).

No

Aufgabe 2

Entwickle Fakten und Regeln zur Festlegung des Prädikats liegen_flussabwaerts/2. Der folgende Dialog zeigt das gewünschte Verhalten des liegen_flussabwaerts-Prädikats anhand einiger Anfragebeispiele auf.

?- liegen_flussabwaerts(trier, cochem).

Yes
?- liegen_flussabwaerts(trier, trier).

No
?- liegen_flussabwaerts(trier, 'Köln').

Yes
?- liegen_flussabwaerts('Köln', trier).

No

Aufgabe 3

Entwickle Fakten und Regeln zur Festlegung des Prädikats liegen_flussaufwaerts/2. Der folgende Dialog zeigt das gewünschte Verhalten des liegen_flussaufwaerts-Prädikats anhand einiger Anfragebeispiele auf.

?- liegen_flussaufwaerts('Köln', trier).

Yes
?- liegen_flussaufwaerts(trier, trier).

No
?- liegen_flussaufwaerts(trier, cochem).

No

Aufgabe 4

Entwickle Fakten und Regeln zur Festlegung des Prädikats liegen_flussabwaerts_flussaufwaerts/3. Der folgende Dialog zeigt das gewünschte Verhalten des liegen_flussabwaerts_flussaufwaerts-Prädikats anhand einiger Anfragebeispiele auf.

?- liegen_flussabwaerts_flussaufwaerts(mainz, saarburg, Stadt).

Stadt = koblenz ;

Stadt = 'Köln' ;

Stadt = 'Düsseldorf' ;

No
?- liegen_flussabwaerts_flussaufwaerts(mainz, 'Köln', Stadt).

No

Aufgabe 5

Entwickle Fakten und Regeln zur Festlegung des Prädikats fahrt_abwaerts_ueber_denselben_fluss/3. Der folgende Dialog zeigt das gewünschte Verhalten des fahrt_abwaerts_ueber_denselben_fluss-Prädikats anhand einiger Anfragebeispiele auf.

?- fahrt_abwaerts_ueber_denselben_fluss(basel, 'Köln', F).

F = [basel, mannheim, mainz, koblenz, 'Köln'] ;

No
?- fahrt_abwaerts_ueber_denselben_fluss(basel, trier, F).

No

Aufgabe 6

Entwickle Fakten und Regeln zur Festlegung des Prädikats fahrt_abwaerts/3. Der folgende Dialog zeigt das gewünschte Verhalten des fahrt_abwaerts-Prädikats anhand einiger Anfragebeispiele auf.

?- fahrt_abwaerts('Saarbrücken', 'Köln', F).

F = ['Saarbrücken', saarburg, konz, konz, trier, bernkastel, cochem, koblenz, koblenz, 'Köln'] ;

No
?- fahrt_abwaerts(basel, koblenz, F).

F = [basel, mannheim, mainz, koblenz] ;

No
?- fahrt_abwaerts(trier, mainz, F).

No

Aufgabe 7

Entwickle Fakten und Regeln zur Festlegung des Prädikats fahrt_aufwaerts/3. Der folgende Dialog zeigt das gewünschte Verhalten des fahrt_aufwaerts-Prädikats anhand einiger Anfragebeispiele auf.

?- fahrt_aufwaerts(koblenz, basel, F).

F = [koblenz, mainz, mannheim, basel] ;

No
?- fahrt_aufwaerts(basel, koblenz, F).

F = [] ;

No
?- fahrt_aufwaerts(basel, trier, F).

No

Aufgabe 8

Entwickle Fakten und Regeln zur Festlegung des Prädikats fahrt/3. Der folgende Dialog zeigt das gewünschte Verhalten des fahrt-Prädikats anhand einiger Anfragebeispiele auf.

?- fahrt('Saarbrücken', 'Köln', F).

F = ['Saarbrücken', saarburg, konz, konz, trier, bernkastel, cochem, koblenz, koblenz, 'Köln'] ;

No
?- fahrt('Saarbrücken', frankfurt, F).

F = ['Saarbrücken', saarburg, konz, konz, trier, bernkastel, cochem, koblenz, koblenz, mainz, mainz, frankfurt] ;

No
?- fahrt('Saarbrücken', regensburg, F).

No

Eine mögliche Lösung findet man in der Datei stadtfluss.pl.