5Cut und Not, Backtracking

Lösungen

5.1Ein Tennisturnier

An einem Nachmittag spielen Adam, Beat, Carlo und Daniel einige Tennisspiele. Die Resultate werden als Prolog Fakten gespeichert:

schlaegt( adam, beat).
schlaegt( adam, carlo).
schlaegt( beat, daniel).
schlaegt( carlo, daniel).

Die Spieler einigen sich auf die Klassifizierung in 3 Kategorien:

klasse( S, 1) /* S hat alle Spiele gewonnen */

klasse( S, 2) /* S hat einige Spiele gewonnen, einige verloren */

klasse( S, 3) /* S hat alle Spiele verloren */

Implementieren Sie das Prädikat klasse( Spieler, Klasse) auf zwei Arten: einmal nur mit cuts, einmal nur mit nots. Testen Sie Ihre Implementationen mit den Abfragen:

1. Welcher Kategorie gehört Adam an?
2. Welche Spieler gehören der Kategorie 2 an?
3. Gehört Adam der Kategorie 1 an? Gehört er der Kategorie 2 an? Gehört er der Kategorie 4 an?
4. Welcher Kategorie gehört Thomas an?
5. Wer hat gespielt und welcher Kategorie gehört er an?

Bemerkung: Beide Lösungen können nicht alle Fragen vollständig beantworten.

Lösung 5.1

5.2Drei Freunde

Beat, Daniel und Michael wohnen in verschiedenen Städten und haben verschiedene Berufe. Sie treffen sich jedes Jahr beim Silvesterlauf in Zürich, wo auch ein von ihnen wohnt. Diesmal wurde Michael vor dem Berner klassiert. Daniel war schneller als der Beamte. Am besten war aber, wie immer, der Sportlehrer. Daniel wohnt in Basel und Michael ist Arzt.

Who is who ?

Lösung 5.2

5.3Das Damenproblem

Auf einem N x N Schachbrett sollen N Damen positioniert werden, sodass sie sich nicht gegenseitig bedrohen (nach den Schachregeln).

5.3.1Generate and Test

Die einfachste (jedoch nicht effiziente) Lösung ist das "Generate and Test" Verfahren der AI, das in Prolog folgendermassen schematisch formuliert werden kann:

solve( Problem, Solution) :- 
    generate( Problem, Solution), 
    test( Solution).

Für das Damenproblem wäre es etwa:

solve( N, Position) :- 
    generate( N, Position),
    test( Position).

Das Prädikat generate generiert durch Backtracking alle möglichen Positionen der Damen, das Prädikat test testet, ob diese Positionen zulässig sind.

Eine Position kann z.B. als [p(1,D1), p(2,D2), ..., p(N,DN)] repräsentiert werden. Die Struktur p(1,D1) bedeutet, dass eine Dame in der Kolonne 1 und der Reihe D1 steht, etc. Die möglichen Werte von D1, D2, ..., DN ergeben sich durch Permutationen der Zahlen 1, 2, ...N.

5.3.2Schrittweises Generate and Test

Eine effizientere Methode ist, die Damen schrittweise in die Kolonnen zu plazieren und dabei sofort zu testen, ob die Position zulässig ist. Wenn die Position nicht zulässig ist, wird sofort das Backtracking in den belegten Kolonnen ausgelöst und erst dann weitergefahren. Versuchen Sie, diese Methode zu implementierten.

Eine partielle Lösung mit den besetzten Kolonnen 1, 2, …, k wird durch die Liste B der besetzten Reihen und die Liste F der freien Reihen repräsentiert.

Beispiel: N = 5, B = [1, 3, 5], F = [2, 4].

Lösung 5.3