2Backtracking
Lösungen
2.1Notenwechsel
Auf welche Arten kann eine 100Fr.-Note in 10Fr.-, 20Fr.- und 50Fr.-Noten gewechselt werden?
Hinweis: Formulieren Sie das Prädikat
wechsel( N10, N20, N50)
das durch Backtracking alle Lösungen findet, sodass 10*N10 + 20*N20 + 50*N50 = 100. Speichern Sie die möglichen Werte für N10, N20, N50 im voraus ab, z.B. N10 kann 0, 1, 2, .., 10 sein.
Lösung 2.1
2.2Das 4-Farben Problem
Eine Karte soll "zulässig" gefärbt werden, d.h. je zwei benachbarte Länder sollen eine verschiedene Farbe haben. Schon sehr lange wurde vermutet, dass eine solche Färbung bereits mit 4 Farben möglich ist. Die Vermutung wurde im Jahr 1852 mathematisch exakt formuliert (F. Guthrie), aber erst im Jahr 1976 von K. Appel und W. Haken durch ein Computerprogramm (!) bewiesen.
Schreiben Sie ein Prolog Programm, welches durch Backtracking alle möglichen zulässigen Färbungen der folgenden Karte mit den Farben rot, blau, gelb und grün angibt.
Fig. 2.1: Eine Karte
Hinweis: Die Karte kann durch die folgende Regel spezifiziert werden:
karte( A, B, C, D, E) :-
nachbar( A, B),
nachbar( A, D),
nachbar( A, E),
nachbar( B, C),
nachbar( B, D),
nachbar( B, E),
nachbar( C, D),
nachbar( C, E),
nachbar( D, E).
Die Frage
?- karte( A, B, C, D, E)
sollte durch Backtracking alle zulässigen Farben der einzelnen Länder liefern.
Lösung 2.2
2.3Europa
Schreiben Sie eine Datenbank mit Staaten:
flaeche( d, 357).
flaeche( f, 547).
flaeche( gb, 244).
flaeche( ch, 41).
. . .
einwohner( d, 78).
einwohner( f, 55).
einwohner( gb, 56).
einwohner( ch, 7).
. . .
nachbar( ch, d).
nachbar( ch, f).
nachbar( d, f).
. . .
Ergänzen Sie die Datenbank mit Deduktionsregeln, z. B.
dichte( S, D)
/* D ist die Einwohnerdichte des Staates S */
sodass die folgenden Abfragen möglich sind:
- Wer ist der Nachbar der Schweiz?
- Wer ist der Nachbar von Frankreich?
- Hat ein Nachbar von Deutschland mehr Einwohner und grössere Fläche als Deutschland?
- Gibt es einen Nachbarn der Schweiz, der höhere Dichte als die Schweiz hat?