Lösungsvorschlag zur Aufgabe 1-5.

Beweisskizzen:

a) Die Aussage kann bewiesen werden dadurch, daß man zuerst eine Induktion
   über die Anzahl der rekursiven Aufrufe in DFS-Contour durchführt und
   zeigt, daß der Eingabewert von `f-limit' immer kleiner ist als der
   Ausgabewert von `f-limit', wenn der Ausgabewert von `solution = null'
   ist. Mit diesem Argument kann man eine Induktion über die Anzahl der
   Schleifendurchläufe im Algorithmus IDA* durchführen.

   Zum Induktionsbeweis der Aussage über DFS-Contour: Ist die Anzahl der
   rekursiven Aufrufe gleich 0, d.h. terminiert der Algorithmus unmittelbar,
   so ist der zurückgegebene Wert für `f-limit' bei `solution = null' immer
   `f-Cost[node] > f-limit'. Andernfalls wird in der for-each-Schleife beim
   rekursiven Aufruf (nach Induktionsvoraussetzung) jedenfalls ein größerer
   Wert als das aktuelle `f-limit' zurückgegeben.

b) Das Problem beim Beweis dieser Aussage liegt darin, daß "Speicher" in
   dem in der Vorlesung vorgestellten Algorithmus keine explizit gegebene
   Größe ist. Im folgenden soll angenommen werden, daß in der Funktion
   DFS-Contour vor dem rekursiven Aufruf eine explizite Abfrage durchgeführt
   wird, ob genügend Speicher zum Anlegen eines neuen Knotens vorhanden ist.
   Nach Voraussetzung gelingt diese Abfrage immer, wenn `f-limit <= f*' ist.

   Die Vollständigkeit des Algorithmus besagt, daß er einen Lösungsknoten
   findet, soweit eine Lösung innerhalb der gegebenen Speicherschranke
   existiert. Da, wie soeben gezeigt, der rekursive Aufruf für alle `f-limit
   <= f*' erfolgreich ist, werden alle Knoten n mit Kosten `f(n) <= f*' besucht
   zumindest solange, bis ein Lösungsknoten gefunden wurde.

   Zur Optimalität: Angenommen, die Funktion DFS-Contour gibt einen
   solution-Knoten nach `n' Schleifendurchläufen zurück (und nicht `null' -- in
   diesem Fall terminiert der Algorithmus). Wie in Teil 1. gezeigt, wächst
   der Wert von `f-limit' während der Schleifendurchläufe monoton. Daraus kann
   man schließen, daß für alle Werte von `f-limit_i' in den
   Schleifendurchläufen `i := 1 \dots (n-1)' keine Lösung gefunden
   wurde. Daher ist der Wert `f-limit_n' der kleinste Wert der Kostenfunktion,
   für die eine Lösung existiert. Damit ist die gegebene Lösung
   optimal. (Das ist nur ein Plausibilitätsargument -- man muß zudem
   noch zeigen, daß in jedem Schleifendurchlauf die Grenze `f-limit' so wenig
   wie möglich hochgesetzt wurde -- dies geschieht durch Berechnung des
   Minimums in der Schleife von DFS-Contour).