Algorithmen und Programmieren III, WS 1999/2000 — 8. Übungsblatt

Abgabe bis Dienstag, 18. Jänner 2000.

41. (13 Punkte) Graphenalgorithmen in der künstlichen Intelligenz. Die folgende Aufgabe findet sich in einer Sammlung von Rechenaufgaben mit dem Titel Propositiones ad acuendos juvenes (Aufgaben zur Schärfung des Geistes der Jugend), die wahrscheinlich um das Jahr 800 am Hof Karls des Großen entstanden ist und Alkuin von York zugeschrieben wird: Die Aufgabe vom Wolf, der Ziege und dem Kohlkopf. Ein Mann musste einen Wolf, eine Ziege und einen Kohlkopf über einen Fluss übersetzen; er konnte aber nur ein Boot auftreiben, das gerade zwei von ihnen tragen konnte. Wie konnte er alles unversehrt hinüberbringen?^{1}

(a) Modellieren Sie diese Aufgabe durch einen Graphen. Die Knoten sollen den möglichen Zuständen des ”Systems“ Mann–Ziege–Wolf–Kohlkopf–Boot–Fluss entsprechen, und die Kanten den erlaubten Übergängen: Zum Beispiel würde der Wolf die Ziege oder die Ziege den Kohlkopf fressen, wenn sie ohne Aufsichtig gelassen würden; der Mann, der das Boot rudert, kann nur einen Gegenstand oder ein Tier zusätzlich mitnehmen. Eine Lösung soll einem Weg in diesem Graphen entsprechen.

(b) Schreiben Sie ein Programm, das diesen Graphen erstellt. Wie viele Knoten und wie viele Kanten hat der Graph? Schreiben Sie eine Programm, das mit Breitensuche einen Weg in diesem Graphen findet, der einer Lösung des Problems entspricht.

(c) (0 Punkte) Ist die Lösung eindeutig? Wie kann man feststellen, ob es in einem Graphen nur einen einzigen Weg von s nach t gibt?

42. (0 Punkte) Das 14-15-Spiel von Sam Loyd besteht aus 15 nummerierten quadratischen Blöcken, die auf einem 4 × 4-Spielfeld beweglich angeordnet sind. Eines der 16 Felder ist frei. Ein Zug besteht darin, dass man einen Stein von einem benachbarten Feld auf das freie Feld verschiebt. Das Ziel ist, von einer gegebenen Ausgangsposition ausgehend, die Steine in die sortierte Reihenfolge zu bringen, sodass das freie Feld am Ende rechts unten ist.

5 3 2 13 7 1 12 15 14  8 10 4 9 6 14 → 5 3 2 13 7 1 12 15 14 9 8 10 4  6 14 → ⋯ → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Diskutieren Sie, wie man dieses Problem als Wegeproblem in einem Graphen modellieren

könnte. Wie viele Knoten und wie viele Kanten hätte der Graph? Welche Schwierigkeiten können bei diesem Problem auftreten?

43. (0 Punkte) Konstruieren Sie ein Beispiel eines Graphen mit negativen Kantenlängen, bei dem der Algorithmus von Dijkstra nicht den kürzesten Weg findet.

1PROPOSITIO DE LUPO ET CAPRA ET FASCICULO CAULI. Homo quidam debebat ultra fluvium transferre lupum et capram et fasciculum cauli, et non potuit aliam navem invenire, nisi quae duos tantum ex ipsis ferre valebat. Praeceptum itaque ei fuerat, ut omnia haec ultra omnino illaesa transferret. Dicat, qui potest, quomodo eos illaesos ultra transferre potuit. SOLUTIO. Simili namque tenore ducerem prius capram et dimitterem foris lupum et caulum. Tum deinde venirem lupumque ultra transferrem, lupoque foras misso rursus capram navi receptam ultra reducerem, capraque foras missa caulum transveherem ultra, atque iterum remigassem, capramque assumptam ultra duxissem. Sicque faciente facta erit remigatio salubris absque voragine lacerationis.