<< zurück

Ikosaeder-Aufgabe

"Gegeben ist ein regelmäßiges Polyeder mit 20 Seitenflächen (Ikosaeder). Die Seitenflächen erhalten die Nummern 1 bis 20 gemäß folgender Abbildung:

Ikosaeder

Eine Reise über alle Seitenflächen des Ikosaeders darf nur über benachbarte Flächen erfolgen, und jede Fläche ist genau einmal zu betreten. Es sind folgende Fälle zu unterscheiden:

A. Zwei Flächen heißen benachbart, wenn sie eine gemeinsame Kante besitzen.

B. Zwei Flächen heißen benachbart, wenn sie eine gemeinsame Kante oder einen gemeinsamen Punkt besitzen.

Die Kosten K einer Reise werden durch das Skalarprodukt Kosten = 1*F1 + 2*F2 + ... + i*Fi + · · · + 20*F20 erklärt. Dabei ist Fi die Nummer der im i-ten Schritt betretenen Fläche.

Gib für die beiden Fälle alle Reisen an, für die die Kosten minimal sind. Sollte es nicht möglich sein, exakte Lösungen zu ermitteln (Zeit- oder Speicherplatzkomplexität der Algorithmen), so sind Algorithmen zum Berechnen von Näherungslösungen zu implementieren."

Die Ikosaeder-Aufgabe ist nach einem Bericht von Dr. Michael Fothe über die 1. Informatikolympiade 1989 zitiert.
Zum Fall A heißt es da:
"In diesem Fall gibt es zu jeder Fläche genau drei Nachbarflächen. Beim vollständigen Durchsuchen aller möglichen Reisen (mittels Backtracking) werden folgende beiden Reisen mit minimalen Kosten K = 1963 ermittelt."
Unser Prologprogramm findet beide Lösungen in wenigen Sekunden, denn die Aufgabe ist aus drei Gründen einfach.

Im Prolog-Programm sind die Nachfolgerflächen der Größe nach geordnet.
Ein Lösungspfad enthält stets 20 Flächen.
Es gibt nur 3240 verschiedene Pfade.

Zum Fall B heißt es:
"Da es in diesem Fall zu jeder Fläche genau neun Nachbarflächen gibt, ist ein vollständiges Durchsuchen aller möglichen Reisen nicht mehr machbar (Zeitkomplexität). Näherungsalgorithmen finden jedoch z. B. folgende beiden Reisen mit den Kosten K = 1575:"
1989 wurde meistens in Pascal programmiert. Mit SWI-Prolog wird im Fall B auf einem Celeron-Computer mit 333MHz die erste Lösung sofort, die zweite nach einer und die dritte und vierte Lösung werden nach 5 Minuten gefunden. Nach 12 Minuten ist der gesamte Lösungsbaum durchsucht, so dass es keinen Weg mit geringeren Kosten geben kann.
Natürlich ist die Zeitkomplexität auch für PCs im Jahre 2002 zu groß, aber mit geeigneter Begrenzung der Suche klappt es doch.

Aufgabe

Zeigen Sie, dass es keine Wege mit geringeren Kosten als 1575 gibt! Laden Sie das Prolog-Programm IkosaederB und ergänzen Sie es so, dass eine Suche immer dann abgebrochen wird, wenn die Summe aus bisherigen Kosten plus die Mindestkosten für den Rest des Wegs größer als 1575 werden würden.

Prologprogramm Fall A Prologprogramm Fall B

% Beschreibung der Lage der Flächen
% Jede Fläche hat drei Nachbarn
nachbar(20, [14, 8, 2]).
nachbar(19, [ 9, 3, 1]).
nachbar(18, [ 5, 4, 2]).
nachbar(17, [10, 7, 3]).
nachbar(16, [ 8, 6, 3]). 
nachbar(15, [12, 7, 5]).
nachbar(14, [20, 6, 4]).
nachbar(13, [11, 5, 1]).
nachbar(12, [15,10, 2]).
nachbar(11, [13, 9, 4]).
nachbar(10, [17,12, 8]).
nachbar( 9, [19,11, 6]).
nachbar( 8, [20,16,10]).
nachbar( 7, [17,15, 1]).
nachbar( 6, [14,16, 9]). 
nachbar( 5, [18,15,13]).
nachbar( 4, [18,14,11]).
nachbar( 3, [19,17,16]).
nachbar( 2, [20,18,12]).
nachbar( 1, [19,13, 7]).

% Ein Zug ist ganz einfach programmiert
zug(Pos, Nachf) :-
  nachbar(Pos, Nachbarn),
  member(Nachf, Nachbarn).

start :-
  nachbar(Startpos, _),
  weg([Startpos], Startpos, Loesung, Kosten),
  write(Loesung), nl, 
  write(Kosten), nl,
  fail.

% Die Wegsuche als einfache begrenzte Tiefensuche
weg(Pfad, Kosten, Pfad, Kosten) :-
  Kosten < 1964,
  length(Pfad, 20).

weg([P | Anfang], Kosten, Loesung, Ergebnis) :-
  Kosten < 1944, % <=Ist diese Grenze sinnvoll???
  zug(P, Nachf),
  \+ member(Nachf, Anfang),
  length(Anfang, Tiefe),
  KostenNeu is Kosten + Nachf*(Tiefe + 2),
  weg([Nachf, P | Anfang], KostenNeu, Loesung, Ergebnis).

wieoft :- % zeigt, dass es 3240 Wege gibt.
  findall(-,
          (nachbar(S,_), weg([S],0,_,_)),
          Liste),
  length(Liste, N),
  write(N).