ALD

Antwort: Korrektheit, Laufzeit, Speicherplatz, Kommunikationszeit, G¨ute u.a

Antwort: Laufzeiten messen und vergleichen bringt nichts aufgrund unterschiedlich schneller

Hardware, unterschiedlich guter Compiler, unterschiedlicher Betriebssysteme und Laufzeitum-

gebungen, unterschiedlichen Eingabedarstellungen und Datenstrukturen usw

Antwort:

• Wir verwenden idealisierte Rechenmodelle wie die Registermaschine (Random Access

Machine, RAM): festgelegter Befehlssatz (Assembler-¨ahnlich), abz¨ahlbar unendlich viele

Speicherzellen.

Die Laufzeit ist dann die Anzahl ausgef¨uhrter RAM-Befehle, der Speicherbedarf ist die

Anzahl der ben¨otigten Speicherzellen.

• Bei den einzelnen Problemstellungen ermitteln wir charakteristische Parameter. Beim

Sortieren sind dies bspw. die Anzahl der Schl¨usselvergleiche bzw. Vertauschungen, bei

arithmetischen Problemen bspw. die Anzahl der Additionen oder Multiplikationen.

Laufzeit und Speicherbedarf sind in der Regel abh¨angig von der Gr¨oße der Eingabe.

Antwort: Weil bei großen Laufzeiten weder schnellere Rechner noch verteilte bzw. parallele

Rechner eine signifikante Laufzeitverbesserung bringen. Bei exponentieller Laufzeit wie 2n kann

ein doppelt so schneller Rechner nur eine um eins gr¨oßere Eingabe in der gleichen Zeit bearbei-

ten, da 2 · 2n = 2n+1 ist. Analog verhalten sich parallele Algorithmen, wo im Mittel nie mehr

als ein linearer Speedup erreicht werden kann.

Antwort: O(g) = {f | ∃c ∈ R+ ∃n0 ∈ N ∀n ≥ n0 : 0 ≤ f (n) ≤ c · g(n)}. Dabei betrachten

wir nur Funktionen mit nat¨urlichen Funktionswerten, also f, g : N → N, weil wir die Anzahl

von Schritten oder benutzten Speicherzellen angeben. Konstante Faktoren c werden bei Auf-

wandsabschätzungen vernachlässigt; es wird nur das asymptotische Wachstum der Funktionen

betrachtet, also das Verhalten bei großen Werten von n.

Antwort: Nein. Es können auch obere Schranken für Average- oder Best-Case-Abschätzungen angegeben werden. Groß-O heißt nicht automatisch Worst-Case, es beschreibt lediglich obere Schranken.

Antwort: Die Menge der zulässigen Eingaben der Länge n bezeichnen wir mit Wn, die Anzahl der Schritte von Algorithmus A für Eingabe w mit A(w).

Dann ist die Worst-Case-Komplexität definiert als TA(n) = sup{A(w) | w ∈ Wn} und ist eine obere Schranke für die maximale Anzahl der Schritte, die Algorithmus A benötigt, um Eingaben der Größe n zu bearbeiten.

Antwort: Divide-and-conquer, dynamische Programmierung, Greedy, Backtracking, Branch-

and-Bound und lokale Suche.

Antwort:

• Divide the problem into subproblems.

• Conquer the subproblems by solving them recursively.

• Combine subproblem solutions.

Antwort: Bei Divide-And-Conquer entstehen in den rekursiven Aufrufen Teillösungen, die wir im Combine-Schritt zusammen fügen müssen. Damit wir nicht dieselben Teilprobleme immer wieder rekursiv lösen, werden bereits berechnete Teillösungen in Tabellen gespeichert. Diesen

Ansatz nennt man memorieren.

Anstatt die Teillösungen rekursiv zu berechnen, kann man aber auch einen Bottom-Up-Ansatz wählen: Aus Rekursion wird Iteration, indem wir aus kleinen Teillösungen größere Lösungen zusammensetzen.

Da wir nicht von vorneherein wissen, welche Teillösungen wir benötigen, berechnen wir einfach alle. Dieses Verfahren wird oft bei Optimierungsproblemen eingesetzt und heißt dynamische Programmierung.

Antwort: Unter anderem beim 0/1-Rucksack-Problem, beim Wechselgeld-Problem, bei der Levenshtein-Distanz und bei einigen Graphalgorithmen wie z.B. die transitive Hülle oder all-pairs-shortest-path.

Antwort: Das Optimalitätsprinzip von Bellman: Eine optimale Lösung kann aus optimalen Teillösungen zusammengesetzt werden; dies gilt z.B. bei kürzesten Wegen: Jeder Teilweg

(vi, . . . , vj ) eines kürzesten Weges (v1, . . . , vi, . . . , vj , . . . , vk) ist ebenfalls ein kürzester Weg.

Antwort: Es werden rein ”lokale Entscheidungen“ getroffen, bei denen nach einem gegebenen Kostenmaß das jeweils nächste Element gewählt wird. Das Verfahren ist iterativ.

Im Schritt i wird aus allen m¨oglichen ”Fortsetzungen Ai einer Teillösung“ diejenige ausgewählt, die momentan den besten Erfolg bringt. Es werden also nicht verschiedene Kombinationen von Teillösungen getestet, sondern nur eine einzige ausgewählt. Diese Lösung ist ggf. nicht optimal.

Probleme: Rucksack-Problem, Handlungsreisenden-Problem (nur approximativ), Wechselgeld-Problem (ist nicht für alle Münzsysteme exakt), Präfix-Code nach Huffman und bei einigen Graphalgorithmen wie z.B. minimaler Spannbaum nach Kruskal

Antwort: Die M¨unzen seien abfallend sortiert nach ihrer Gr¨oße, also

d1 ≥ d2 ≥ . . . ≥ dk = 1.

In der Regel wird dk = 1 vorausgesetzt, damit jeder Betrag ausgezahlt werden kann.

Rekursiv: Der auszuzahlende Betrag sei p. Dann lautet der initiale Aufruf Geld(1, p).

Im folgenden Algorithmus bezeichnet div die ganzzahlige Division.

function Geld(i, p : int) : int

if p = 0 then

return 0

return p div di + Geld(i + 1, p mod di)

Iterativ: Nimm möglichst wenige Münzen, indem der Betrag zunächst um das maximale Vielfache ci der größten Münze reduziert wird. Setze das Verfahren mit der nächst kleineren Münze und dem Restbetrag fort. Gib schließlich die Summe c1 + c2 + . . . + ck aus.

s := 0, i := 1

while r > 0 do ⊲ r ist der Restbetrag bzw. initial der auszuzahlende Betrag

ci := r div di ⊲ ci ist die Anzahl, wie oft M¨unze di ben¨otigt wird

s := s + ci ⊲ Anzahl der M¨unzen insgesamt

r := r mod di ⊲ Restbetrag

i := i + 1

Gib die Anzahl s sowie die Anzahlen ci der einzelnen Münzen aus

Problem hierbei: Funktioniert nicht bei allen Münzfolgen: Bei den Münzen 11,7,1 wird der

Betrag 14 als 1 · 11 + 3 · 1 ausgezahlt, aber 2 · 7 wäre besser, da anstelle von vier Münzen nur

zwei Münzen benötigt werden. Beim europäischen und dem US-amerikanischen Münzsystem liefert der Greedy-Ansatz optimale Lösungen.

Antwort: Das Master-Theorem gibt die L¨osung einer allgemeinen Rekursionsgleichung der

folgenden Form an: T (n) = a · T (n/b) + Θ(n^k)

Es lässt sich oft auf Rekursionsgleichungen anwenden, die bei Divide-And-Conquer-Algorithmen entstehen, z.B. Laufzeit der binären Suche, Best-Case-Laufzeit von Quicksort oder der Laufzeit von Mergesort.

Es ist immer dann anwendbar, wenn a viele Teilprobleme jeweils der Größe n/b zu lösen sind und der Divide- und der Combine-Schritt zusammen einen Aufwand von Θ(n^k)

haben.

• Binäre Suche:

T (n) = 1 · T (n/2) + Θ(1), also ein rekursiver Aufruf (a = 1); die zu

durchsuchende Folge wird in jeder Runde halbiert (b = 2); das Aufteilen in Teilprobleme

bzw. das Zusammenfassen von Teillösungen dauert nur konstante Zeit

(k = 0).

a = bk → T ∈ Θ(nk · log(n)) = Θ(log(n))

• Mergesort:

T (n) = 2 · T (n/2) + Θ(n), also zwei rekursive Aufrufe (a = 2); die zu sortie-renden Teilfolgen werden in jeder Runde halbiert (b = 2); das Aufteilen in Teilfolgen ist in konstanter Zeit möglich, aber das Mischen der sortierten Teilfolgen zu einer einzigen sortierten Folge kostet lineare Zeit (k = 1).

a = bk → T ∈ Θ(nk · log(n)) = Θ(n · log(n))

Antwort: naiver Algorithmus

for i := 1 to n do

for j := 1 to n do

c[i][j] := 0

for k := 1 to n do

c[i][j] := c[i][j] + a[i][k] * b[k][j]

Die Laufzeit liegt in Θ(n3), denn es müssen n2 viele Elemente cij berechnet werden; die Berechnung jedes einzelnen Elements cij dauert Zeit Θ(n).

Antwort: Es ist ein Divide-And-Conquer Algorithmus: Teile die gegebene Folge mittels eines Pivot-Elements p auf in zwei Teilfolgen: Folge K enthält nur Elemente kleiner gleich p und Folge G enthält nur Elemente größer gleich p. Sortiere anschließend die Teilfolgen rekursiv, sodass sich insgesamt eine sortierte Folge ergibt: sorted(K), p, sorted(G)

1. Divide: Wähle aus allen Werten einen beliebigen Wert p, das Pivotelement aus und teile die Folge in zwei Teilfolgen K und G auf:

• K enth¨alt Werte die kleiner oder gleich p sind,

• G enth¨alt Werte die gr¨oßer oder gleich p sind.

<= p p >= p

2. Conquer: Sortiere K und G rekursiv

3. Combine: trivial (entf¨allt)

Antwort:

Wähle ein Pivot-Element p. Suche das erste Element (von links), das größer als p ist, und suche das erste Element (von rechts), das kleiner als p ist, und vertausche die beiden Elemente. Wiederhole das Suchen und Vertauschen jeweils ab der Stelle, wo der letzte Tausch stattgefunden hat. Tausche zum Schluss das Pivot-Element an die richtige Stelle.

function Partition(a : sequence; ℓ, r: Integer)

p := a[ℓ], i := ℓ + 1, j := r

repeat

while i < r and a[i] ≤ p do

i := i + 1

while j > ℓ and a[j] ≥ p do

j := j − 1

if i < j then

SwapAt(a, i, j)

until j ≤ i

SwapAt(a, ℓ, j)

return j

Antwort: Die Wahrscheinlichkeit, dass die Folge an Position p aufgeteilt wird, ist 1/n. Das

Aufteilen in zwei Teilfolgen erfolgt in Zeit O(n).

Antwort:

• Worst-Case-Laufzeit ist O(n2)

• stark vorsortierte Folgen oder solche Folgen, die viele gleiche Elemente enthalten

Antwort: Mittels einer Zufallsstrategie kann Quicksort verbessert werden: W¨ahle als Pivot-

Element ein zuf¨alliges Element aus A[l...r] und vertausche es mit A[l].

⇒ Laufzeit ist unabh¨angig von der zu sortierenden Folge

⇒ mittlere/erwartete Laufzeit: Θ(n · log(n))

Antwort: 3-Wege-Split Quicksort:

Teile die Folge a[l], . . . , a[r] in drei Folgen Fl, Fm, Fr auf.

• Fl enth¨alt die Elemente mit Schl¨ussel < k.

• Fm enth¨alt die Elemente mit Schl¨ussel = k.

• Fr enth¨alt die Elemente mit Schl¨ussel > k.

Sortiere Fl und Fr auf dieselbe Weise.

Idee: Die Pivotelemente werden zuerst am Rand gesammelt (zwischen l und l2 sowie zwischen

r2 und r) und vor dem rekursiven Aufruf in die Mitte transportiert.

während der Aufteilung (Partitionierung) sind drei Fälle zu unterscheiden, der vierte Fall wird

wie im urspr¨unglichen Quicksort behandelt:

Antwort: Im ung¨unstigen Fall ist die

Rekursionstiefe O(n).

Wir k¨onnen die Rekursionstiefe aber wie folgt

auf O(log(n)) beschr¨anken:

• löse das kleinere Teilproblem rekursiv

und

• löse das größere Teilproblem iterativ

direkt.

quicksort(int l, int r)

while l < r

m := partition(l, r)

if (m-l) < (r-m) then

quicksort(l, m-1)

l := m + 1

else

quicksort(m+1, r)

r := m - 1

Antwort: Mergesort und Heapsort

• Teile die Folge in zwei etwa gleich große Teilfolgen.

• Sortiere die Teilfolgen rekursiv.

• Mische die sortierten Teilfolgen zu einer Folge zusammen.

– Zun¨achst werden die Werte in ein Hilfsarray kopiert.

– Durchlaufe die Hilfsarrays jeweils elementweise von vorne nach hinten.

– Das jeweils kleinere der beiden Elemente wird in das originale Array an die nächste

Stelle zurück kopiert.

→ T (n) = 2 · T (n/2) + c · n ∈ O(n · log n)

Antwort:

• Erstelle einen initialen Max-Heap. Anschließend wird in Runde k das oberste Element

mit dem Element an Position n − k getauscht und das nun oberste Element versickert.

• Es werden n Runden ben¨otigt, jeweils mit der Laufzeit O(log n), da der Heap nur loga-

rithmische Tiefe hat. Aufbauen des initialen Heaps erfolgt in Zeit O(n).

• Das Erstellen des initialen Heaps erfolgt, indem wir die Elemente kn/2−1, . . . , k0 nach-

einander versickern lassen. Dabei m¨ussen n/4 Elemente nur um eine Ebene im Baum

verschoben werden, n/8 viele Elemente nur um 2 Ebenen usw.

Antwort: Allgemeine Sortierverfahren verwenden ausschließlich Vergleichsoperationen zwischen Schlüsseln, um die Positionen der Werte in der sortierten Folge zu bestimmen, aber keine arithmetischen Operationen oder ähnliches.

Jedes allgemeine Sortierverfahren benötigt zum Sortieren von n verschiedenen Schlüsseln im

schlechtesten Fall und im Mittel wenigstens Ω(n · log(n)) Schl¨usselvergleiche.

Antwort: Man zeigt das ¨uber die H¨ohe von Entscheidungsb¨aumen.

Worst-Case-Analyse:

• es gibt n! verschiedene Permutationen über n Zahlen

• ein Entscheidungsbaum hat mindestens n! Blätter

• ein Binärbaum der Höhe h hat maximal 2h − 1 Blätter

• es muss also gelten: 2h ≥ n!

h ≥ log(n!) log ist monoton steigend

≥ log((n/e)n) Stirling-Formel

= log(nn) − log(en)

= n · log(n) − n · log(e)

∈ Ω(n · log(n))

Antwort: Ja, mittels Counting-Sort bzw. Radix-Sort. Die funktionieren aber nur gut f¨ur

Integer-Werte. Zusammengesetzte Datentypen wie double (setzt sich aus Mantisse und Ex-

ponent zusammen) bereiten bei Radix-Sort Probleme, Counting-Sort ist nicht brauchbar bei

großen Wertebereichen.

Antwort: Gleiche Elemente stehen nach dem Sortieren in der gleichen relativen Reihenfolge

zueinander wie vor dem Sortieren

Antwort: O(n + k) bei n Elementen und k Schl¨usselwerten.

• Initialisieren des Count-Arrays: O(k)

• Durchlaufen der Werte zum Erstellen der Counts: O(n)

• Count aufsummieren: O(k)

• Einsortieren der Werte: O(n)

Frage 40 Wie funktioniert Radix-Sort?

Antwort: Sortiere die Zahlen anhand der einzelnen Ziffern, beginnend mit der niederwertigsten

Stelle. Verwende ein stabiles Sortierverfahren wie Countingsort. Falls n¨otig, m¨ussen f¨uhrende

Nullen eingef¨ugt werden. Dieser Ansatz ist f¨ur ganze Zahlen geeignet, aber nicht f¨ur reelle

Zahlen, da es ¨uberabz¨ahlbar viele reelle Zahlen gibt

Antwort: Fasse jeweils r Bit einer Zahl zu einer Ziffer zusammen. Bei einer Wortl¨ange von

b Bit m¨ussen b/r Phasen durchlaufen werden. Countingsort hat Laufzeit Θ(n + k), wobei n

die Anzahl der Zahlen und {0, . . . , k − 1} der Wertebereich der Zahlen ist. Bei b/r Phasen

erhalten wir als Laufzeit von Radix-Sort Θ(b/r · (n + 2r)). In der Praxis fasst man bspw. 32-

Bit-W¨orter in Gruppen zu 8 Bit zusammen und erh¨alt damit vier Phasen und insgesamt als

Laufzeit Θ(4 · (n + 28)) = Θ(n).

Antwort: Sortiert Zahlen aus dem Bereich [0, 1), also reelle Zahlen, wobei das Verfahren nur

dann eine lineare Laufzeit hat, wenn die Zahlen ungef¨ahr gleichverteilt sind.

Die n Werte des Arrays werden in verschiedene F¨acher einsortiert. Der Wert A[i] wird in das

Fach B[⌊n · A[i]⌋] eingef¨ugt. Sind alle Werte in die jeweiligen F¨acher eingef¨ugt, entnimmt man

die Werte nacheinander aus den F¨achern B[0], . . . , B[n − 1] und f¨ugt sie in dieser Reihenfolge

in das Array A ein.

Antwort: Im Worst-Case werden alle Werte in dasselbe Fach einsortiert und es ergibt sich

als Laufzeit O(n2). Werden die Listen nicht sortiert gehalten sondern anschließend sortiert,

erhalten wir im Worst-Case die Laufzeit O(n · log(n)).

Im Best-Case verteilen sich die Werte auf alle F¨acher, sodass genau ein Wert pro Fach abgelegt

wird. Dann erhalten wir eine lineare Laufzeit O(n).

Auch im Average-Case erhalten wir eine lineare Laufzeit. Sei Xi eine Zufallsvariable, die die

Anzahl der Elemente im Fach B[i] beschreibt. F¨ur jedes Element A[j] gilt dann: Die Wahr-

scheinlichkeit, dass das Element A[j] im Fach i abgelegt wird, ist P (A[j] f¨allt in Fach i) = 1/n.

Aus diesem Bernoulli-Experiment ergibt sich dann die lineare Laufzeit.

Antwort:

12

• Lineare Suche: O(n), ¨uberpr¨uft ein Element nach dem anderen und findet damit im

Durchschnitt nach n/2 Versuchen das gesuchte Element.

• Bin¨are Suche: O(log(n)). Beginne mit linker Grenze ℓ := 1 und rechter Grenze r := n.

Vergleiche das Element in der Mitte m := ⌊ℓ+r

2 ⌋ mit dem gesuchten Element. Ist das

gesuchte Element kleiner, dann setze r := m − 1, sonst setze ℓ := m + 1. In jeder Runde

wird das zu durchsuchende Intervall halbiert.

Die Anzahl der Schritte ist damit die durchschnittliche Tiefe eines entsprechenden Such-

baums, also O(log(n)), da ungef¨ahr die H¨alfte der Zahlen in der letzten Ebene und die

andere H¨alfte oberhalb davon liegt. Deshalb braucht man im durchschnittlichen Fall nur

einen Schritt weniger als im schlechtesten Fall.

Antwort: Die Zahlen sind so gew¨ahlt, dass kein Taschenrechner ben¨otigt wird!

i : 0 1 2 3 4 5 6 7 8 9 10

a[i] : 1 3 5 8 11 17 25 29 37 39 41

l = 0, r = 10, m = 0 + (17- 1) * 10 / (41- 1), m = 4, a[4] = 11

l = 5, r = 10, m = 5 + (17-17) * 5 / (41-17), m = 5, a[5] = 17

Antwort: best-case: Θ(1). Das Element wird direkt beim ersten Zugriff gefunden. Wird nur

erreicht, wenn die Werte gleichverteilt sind und keine H¨aufungen in den Werten enthalten sind.

worst-case: Θ(n). Wenn die Werte am Rand extrem von den anderen Werten abweichen, also

wenn die Werte sehr ungleichm¨aßig verteilt sind. Dann l¨auft der Algorithmus alle Positionen

im Array durch.

Antwort:

i : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

a[i] : 1 3 5 7 9 11 25 37 49 61 73 85 87 91 93 95 99 ...

Zun¨achst muss der Suchbereich eingegrenzt werden:

i = 1: a[i] = 1 < 91 ? Ja --> i *= 2

i = 2: a[i] = 3 < 91 ? Ja --> i *= 2

i = 4: a[i] = 7 < 91 ? Ja --> i *= 2

i = 8: a[i] = 37 < 91 ? Ja --> i *= 2

i = 16: a[i] = 95 < 91 ? Nein

Der Bereich zwischen l := i/2 + 1 und r := i wird mittels bin¨arer Suche durchsucht:

l = 9, r = 16, m = 12, a[m] = 85 --> l := m+1

l = 13, r = 16, m = 14, a[m] = 91 --> gefunden

Antwort: Eine Laufzeitabsch¨atzung ist nur m¨oglich, falls die Werte im Array streng monoton

steigen, also keine Werte mehrfach enthalten sind. Das Eingrenzen des Suchbereichs hat dann

Laufzeit O(log(k)). Da der Bereich h¨ochstens k Elemente enth¨alt, erfolgt die anschließende

bin¨are Suche ebenfalls in Zeit O(log(k)).

Antwort: Bei einer Ringliste enth¨alt das letzte Element einen Zeiger auf den Anfang der Liste.

Antwort: Eine Queue arbeitet nach dem FIFO-Prinzip (First-In, First-Out), ein Stack nach

dem LIFO-Prinzip (Last-In, First-Out).

Antwort: 44, 39, 20, 3, 25, 42, 67, 60, 59, 65, 75, 72, 89

Antwort: Ohne Balancierung w¨urde durch das Einf¨ugen von aufsteigend sortierten Werten ein

zu einer Liste degenerierter Baum entstehen. Beim Einf¨ugen eines Wertes m¨usste ggf. immer

bis ans Ende der Liste gelaufen werden. Als Laufzeit zum Einf¨ugen von n Elementen in einen

solchen Baum erhalten wir daher

Das Balancieren der Bäume führt zu einer besseren Worst-Case-Laufzeit für das Einfügen und

Löschen von sowie dem Suchen nach Objekten.

Antwort: Beim erfolgreichen Suchen eines Wertes werden gerade so viele Vergleiche ben¨otigt,

wie der gesuchte Knoten von der Wurzel entfernt ist. Die interne Pfadl¨ange (internal path

length) eines Baums ist:

Wenn wir die interne Pfadl¨ange durch die Anzahl der Knoten N im Baum dividieren, so erhalten

wir die durchschnittliche Anzahl der ben¨otigten Vergleiche. Sei CN die durchschnittliche interne

Pfadl¨ange eines bin¨aren Suchbaums mit N Knoten. Dann gilt:

Analog zu der Rekursionsformel von Quicksort gilt CN ∈ Θ(N log N ). Dividieren wir durch N

so erhalten wir die durchschnittliche Anzahl Vergleiche bei einer erfolgreichen Suche: Θ(log N )

Antwort: In einem AVL-Baum unterscheiden sich die Tiefen des linken und des rechten Teil-

baums f¨ur jeden Knoten h¨ochstens um 1, sodass die B¨aume im wesentlichen balanciert sind.

Unterscheiden sich die Tiefen im AVL-Baum zwischen zwei Teilb¨aumen nach dem Einf¨ugen oder

Löschen eines Elements um 2, wird mit Hilfe von sogenannten Rotationen der Baum wieder

ausgeglichen. Eine Rotation hat konstante Laufzeit, das Aktualisieren der Differenzwerte kann

sich allerdings bis zur Wurzel fortsetzen.

Suchen nach sowie Einf¨ugen und L¨oschen von Objekten erfolgt in Zeit O(log(n)), wenn n die

Anzahl der Objekte im Baum bezeichnet.

Antwort: Ein minimaler AVL-Baum der H¨ohe t > 1 setzt sich aus einer Wurzel und einem

Teilbaum der H¨ohe t − 1 sowie einem Teilbaum der H¨ohe t − 2 zusammen. F¨ur die minimale

Anzahl n(t) von Knoten in einem Baum der H¨ohe t gilt also:

→ n(t) = 1 + n(t − 1) + n(t − 2) = f ib(t + 3) − 1 ≈ 1.61803t+4

Aus der Mathematik wissen wir, dass die Fibonacci-Zahlen f ib(i) exponentielles Wachstum haben.

→ Die Höhe eines AVL-Baumes mit n Knoten ist in O(log(n)).

Antwort:

Teilbaum A ist vor und nach der Rotation links von K2, ebenso ist Teilbaum C vorher und

nachher rechts von K1, sodass hier keine Erkl¨arung n¨otig ist. Da K2 vorher links von K1 ist,

gilt K2.key < K1.key, und damit ist die Anordnung von K1 und K2 nachher auch korrekt.

Bleibt nur noch der Teilbaum B. Die Werte der Knoten von B sind kleiner als K1.key und

größer gleich K2.key, also ist auch nach der Rotation die Suchbaumeigenschaft erf¨ullt.

Antwort: Es sind keine Bin¨arb¨aume! Ein B-Baum der Ordnung m hat folgende Eigenschaften:

• Alle Bl¨atter befinden sich in gleicher Tiefe.

• Alle inneren Knoten außer der Wurzel haben mindestens ⌈m/2⌉ Kinder. Besteht der Baum

nicht nur aus der Wurzel, dann hat die Wurzel mindestens 2 Kinder.

• Jeder innere Knoten hat h¨ochstens m Kinder. Ein Knoten mit k Kindern speichert k − 1

Schl¨usselwerte.

• Alle Schl¨usselwerte eines Knotens sind aufsteigend sortiert.

Seien k1, . . . , ks die Schl¨ussel eines inneren Knotens. Dann gibt es die Zeiger z0, z1, . . . , zs auf

die Kinder und es gilt:

• z0 zeigt auf einen Teilbaum mit Werten kleiner als k1.

• zi f¨ur i = 1, . . . , s − 1 zeigt auf einen Teilbaum mit Werten gr¨oßer als ki und kleiner als

ki+1.

• zs zeigt auf einen Teilbaum mit Werten gr¨oßer als ks.

Antwort:

Bestimme zunächst mittels einer Suche das Blatt, in dem der Wert abgelegt werden

muss. Wir unterscheiden zwei Fälle:

• Fall 1: Das Blatt hat noch nicht die maximale Anzahl m − 1 von Schl¨usseln gespeichert.

Dann f¨ugen wir den Wert entsprechend der Sortierung ein.

• Fall 2: Das Blatt hat bereits die maximale Anzahl m − 1 von Schl¨usseln gespeichert.

In diesem Fall ordnen wir den Wert wie im Fall 1 entsprechend seiner Gr¨oße ein und teilen

anschließend den zu groß gewordenen Knoten in der Mitte auf. Das mittlere Element wird

in den Vorg¨anger-Knoten eingef¨ugt.

Dieses Teilen wird solange l¨angs des Suchpfades bis zur Wurzel fortgesetzt, bis ein Knoten

erreicht ist, der noch nicht die maximale Anzahl von Schl¨usseln speichert, oder bis die

Wurzel erreicht wird.

Muss die Wurzel geteilt werden, so schafft man eine neue Wurzel, die den mittleren

Schl¨ussel als einzigen Schl¨ussel speichert.

inorder: 1, 4, 5, 6, 8, 10, 11, 12, 16

Preorder: 8, 4, 1, 6, 5, 10, 12, 11, 16

Postorder: 1, 5, 6, 4, 11, 16, 12, 10, 8

Levelorder: 8, 4, 10, 1, 6, 12, 5, 11, 16

Antwort: Strukturanpassung an unterschiedliche Zugriffsh¨aufigkeiten:

• Oft angefragte Schl¨ussel werden in Richtung Wurzel bewegt.

• Selten angefragte Schl¨ussel wandern zu den Bl¨attern hinab.

• Die Zugriffsh¨aufigkeiten sind vorher nicht bekannt.

Sei T ein Suchbaum und x ein Schl¨ussel. Dann ist splay(T,x) der Suchbaum, den man wie

folgt erh¨alt:

• Schritt 1: Suche nach x in T. Sei p der Knoten, bei dem die erfolgreiche Suche endet, falls

x in T vorkommt. Ansonsten sei p der Vorg¨anger des Blattes, an dem die Suche nach x

endet, falls x nicht in T vorkommt.

• Schritt 2: Wiederhole die Operationen zig (einzelne Rotation), zig-zig (zwei Rotationen

in die gleiche Richtung) und zig-zag (zwei Rotationen in entgegengesetzte Richtungen)

beginnend bei p solange, bis sie nicht mehr ausf¨uhrbar sind, weil p Wurzel geworden ist.

Antwort:

• Kommt x in T vor, so erzeugt splay(T,x) einen Suchbaum, der den Schl¨ussel x in der

Wurzel speichert.

• Kommt x nicht in T vor, so wird der in der symmetrischen Reihenfolge dem Schl¨ussel x

unmittelbar vorangehende oder unmittelbar folgende Schl¨ussel zum Schl¨ussel der Wurzel.

Antwort: Um x in T einzuf¨ugen, rufe splay(T,x) auf. Ist x nicht in der Wurzel, so f¨uge wie

folgt eine neue Wurzel mit x ein. Beachte obige zweite Aussage: Kommt x nicht in T vor, so

wird der in der symmetrischen Reihenfolge dem Schl¨ussel x unmittelbar vorangehende oder

unmittelbar folgende Schl¨ussel zum Schl¨ussel der Wurzel

Antwort: Ohne die additive Konstante w¨urde sich f¨ur alle durch 11 teilbaren Zahlen k keine

Sondierungsfolge ergeben, so ist z.B. f¨ur k = 22 der Wert der Hash-Funktion h′

2(22) = 0 und

damit w¨are h(22, i) = (h1(22) + i · h′2(22)) mod M = h1(22) mod M für alle i; es w¨urden also

keine Ausweichpl¨atze untersucht und der Wert k k¨onnte ggf. nicht eingefügt werden.

(1) h1(3) = 3 mod 13 = 3 → h2(3) = 1 + 3 mod 11 = 4, (3 + 1 · 4) mod 13 = 7

(2) h1(4) = 4 mod 13 = 4 → h2(4) = 1 + 4 mod 11 = 5, (4 + 1 · 5) mod 13 = 9

(3) h1(5) = 5 mod 13 = 5 → h2(5) = 1 + 5 mod 11 = 6, (5 + 1 · 6) mod 13 = 11

(4) h1(29) = 29 mod 13 = 3 → h2(29) = 1 + 29 mod 11 = 8, (3 + 1 · 8) mod 13 = 11 CRASH

→ (3 + 2 · 8) mod 13 = 6

(5) h1(17) = 17 mod 13 = 4 → h2(17) = 1 + 17 mod 11 = 7, (4 + 1 · 7) mod 13 = 11 CRASH

→ (4 + 2 · 7) mod 13 = 5 → (4 + 3 · 7) mod 13 = 12

(6) h1(18) = 18 mod 13 = 5 → h2(18) = 1 + 18 mod 11 = 8, (5 + 1 · 8) mod 13 = 0

Antwort: Ein gerichteter Graph G = (V, E) besteht aus

• einer endlichen Menge von Knoten V = {v1, . . . , vn} und

• einer Menge von gerichteten Kanten E ⊆ V × V .

Bei einem ungerichteten Graphen G = (V, E) sind die Kanten ungeordnete Paare:

E ⊆ {{u, v} | u, v ∈ V, u 6 = v}

Antwort: Sei G = (V, E) ein gerichteter Graph und seien u, v ∈ V . Dann ist p = (v0, v1, . . . , vk)

ein gerichteter Weg in G der L¨ange k von Knoten u nach Knoten w, falls gilt: v0 = u, vk = w

und (vi−1, vi) ∈ E f¨ur 1 ≤ i ≤ k.

Der Weg p ist einfach, wenn kein Knoten mehrfach vorkommt.

Oder: Sei G = (V, E) ein ungerichteter Graph und seien u, v ∈ V . p = (v0, v1, . . . , vk) ist ein

ungerichteter Weg in G der L¨ange k von Knoten u nach Knoten w, falls gilt: v0 = u, vk = w

und {vi−1, vi} ∈ E f¨ur 1 ≤ i ≤ k.

Antwort: Die Graphen G1 und G2 sind Teilgraphen von G, aber G1 und G2 sind keine indu-

zierten Teilgraphen von G, da in G1 die Kanten (6, 1) und (5, 7) fehlen und in G2 bspw. die

Kanten (1, 7) und (7, 2) fehlen.

• Ein Graph G′ = (V ′, E′) ist ein Teilgraph von G, geschrieben G′ ⊆ G, falls V ′ ⊆ V und

E′ ⊆ E.

• F¨ur einen induzierten Teilgraphen G′ von G fordern wir zus¨atzlich, dass eine Kante e =

(u, v) ∈ E mit u, v ∈ V ′, bei der also Start- und Endknoten in V ′ liegen, auch im

Teilgraphen G′ vorhanden ist

Antwort: Die einfache Tiefensuche soll alle von einem gegebenen Startknoten s aus erreichba-

ren Knoten finden.

Zun¨achst werden die globalen Variablen dfbZ¨ahler und dfeZ¨ahler mit 0 initialisiert. Außerdem

werden alle Knoten als unbesucht markiert. Die rekursive Funktion dfs ist wie folgt definiert.

Antwort: F¨ur einen Graphen G = (V, E) betr¨agt die Laufzeit O(|V | + |E|).

• Da die Knoten markiert werden und bereits besuchte Knoten nicht zweimal besucht wer-

den, werden maximal alle |V | Knoten besucht.

• Da die zu einem Knoten inzidenten Kanten aufgrund der Markierung der Knoten auch nur

einmal (bei gerichteten Graphen) oder zweimal (bei ungerichteten Graphen) betrachtet

werden, ergibt sich in Summe die Laufzeit O(|V | + |E|).

Antwort:

• Baumkante: Kante, der die Tiefensuche folgt.

• Vorw¨artskante: Kante (u, v) ∈ E mit dfb[v] > dfb[u], die aber keine Baumkante ist.

• Querkante: Eine Kante (u, v) ∈ E mit dfb[v] < dfb[u] und dfe[v] < dfe[u].

• R¨uckw¨artskante: Kante (u, v) ∈ E mit dfb[v] < dfb[u] und dfe[v] > dfe[u].

Antwort: Es entfallen die Querkanten und die Vorw¨artskanten.

• Querkanten existieren nicht, da dfs(u) innerhalb von dfs(v) aufgerufen w¨urde, siehe obige

grafische Darstellung.

• Vorw¨artskanten existieren nicht, weil bei dfs(v) die Kante {v, u} als R¨uckw¨artskante

entdeckt w¨urde: df b[v] > df b[u] und df e[v] < df e[u].

Es gibt also nur Baum- und R¨uckw¨artskanten bei einer Tiefensuche auf ungerichteten Graphen.

Antwort: Kreise k¨onnen mittels einer Tiefensuche (nicht die einfache Tiefensuche) gefunden

werden. ( ¨Uberlegen Sie sich, warum eine einfache Tiefensuche nicht ausreichend ist.)

markiere alle Knoten als unbesucht

solange ein unbesuchter Knoten v existiert:

dfs(v)

Satz: Ein gerichteter Graph G enthält genau dann einen Kreis, wenn die Tiefensuche auf G eine

Rüuckwärtskante liefert.

Antwort:

• Gegeben: Ein gerichteter Graph G = (V, E).

• Gesucht: Eine Nummerierung π(v1), . . . , π(vn) der Knoten, sodass gilt:

(u, v) ∈ E ⇒ π(u) > π(v)

Algorithmus: Tiefensuche

G ist kreisfrei ⇒ dfe-Nummern sind topologische Sortierung!

Antwort: Ein Baum ist ein zusammenh¨angender, kreisfreier Graph. Ein Spannbaum T =

(V, ET ) eines Graphen G = (V, E) ist ein Baum, der jeden Knoten aus V enth¨alt. Ein sol-

cher Baum besteht aus |V | − 1 Kanten. Die Kosten eines Spannbaums sind definiert als

Ein minimaler Spannbaum ist ein Spannbaum mit minimalen Kosten unter allen m¨oglichen

Spannb¨aumen des Graphen.

Antwort: Beweis durch Widerspruch:

Wir nehmen an, dass kein minimaler Spannbaum die

billigste Kante zwischen V1 und V2 enth¨alt. Dann

entsteht durch Hinzunahme der billigsten Kante

ein Kreis.

Durch streichen der teueren Kante zwischen V1 und V2 des Kreises entsteht wieder ein Spann-

baum, dessen Gewicht sogar geringer ist als der urspr¨ungliche Spannbaum.

Antwort: Sei Q eine Datenstruktur (Priority Queue) zum Speichern von Knoten. Die Knoten

sind mit den Kantenwerten gewichtet

Q := V

key[v] := ∞ for all v ∈ V

key[s] := 0 for some arbitrary s ∈ V

while Q 6 = ∅ do

u := minimum(Q)

extractMin(Q)

for all v ∈ Adj(u) do

if v ∈ Q and c((u, v)) < key[v]

then key[v] := c((u, v))

π[v] := u

decreaseKey(Q, v, key[v])

Laufzeit:

T = Θ(|V |) · Tminimum + Θ(|V |) · TextractM in + Θ(|E|) · TdecreaseKey

Antwort: Sei G = (V, E, c) ein ungerichteter Graph mit Kostenfunktion c : E → R+.

Nach Ablauf des Algorithmus enth¨alt die Menge A die Kanten eines minimalen Spannbaums.

Variante: Anstelle des Sortierens k¨onnen die Kanten auch in eine Priority-Queue Q eingef¨ugt

werden, sortiert nach dem Gewicht der Kanten. Die Schleife ¨andert sich dann zu:

Antwort: Insbesondere sollen die Funktionen findSet und union unterst¨utzt werden. Daher

wird die Datenstruktur Union-Find-Datenstruktur genannt. Sie unterst¨utzt die Speicherung

einer disjunkten Zerlegung einer Menge S = X1 ∪ X2 ∪ . . . ∪ Xk mit Xi ∩ Xj = ∅ f¨ur i 6 = j.

• Speichere jede Klasse Xi in einem Baum.

• Der Repr¨asentant einer Klasse Xi ist die Wurzel des Baums.

• Die Funktion findSet(v) liefert den Repr¨asentanten des Baums, in dem Knoten v ge-

speichert ist.

• Damit ein Knoten schnell gefunden werden kann, werden Zeiger auf alle Elemente v ∈ S

gespeichert.

• Die Funktion union h¨angt den kleineren (bzw. flacheren) Baum an die Wurzel des gr¨oßeren

(bzw. tieferen) Baums an

Antwort: Wir nutzen hier die Vereinigung zweier B¨aume anhand deren Rang, also der H¨ohe

der B¨aume. Die Wurzel des flacheren Baums wird unter die Wurzel des h¨oheren Baums geh¨angt.

Antwort: Die Kosten einer findSet-Operation sind abh¨angig von der H¨ohe der B¨aume.

• Es w¨are g¨unstig, alle Knoten direkt an die Wurzel zu h¨angen. Das aber w¨urde die union-

Operation teurer machen als bisher.

• Stattdessen: Verk¨urze w¨ahrend der findSet-Operation die Pfadl¨angen. Die Pfadkompri-

mierung macht die findSet-Methode ungef¨ahr doppelt so teuer wie vorher, die asympto-

tische Laufzeit bleibt gleich.

• Eine amortisierte Laufzeitanalyse liefert: Kruskals Algorithmus hat f¨ur alle praktischen

Eingaben eine lineare Laufzeit. Dabei gehen wir davon aus, dass die Kanten bereits sortiert

sind oder mittels Radix-Sort in linearer Zeit sortiert werden k¨onnen.

Antwort: Es werden alle k¨urzesten Wege von einem Startknoten aus gesucht (single source

shortest paths). Sei Q eine Datenstruktur (Priority Queue) zum Speichern von Knoten. Die

Knoten sind mit Distanzwerten gewichtet. Wichtig: Die Kantengewichte d¨urfen nicht negativ

sein!

Laufzeit:

T = Θ(|V |) · Tminimum + Θ(|V |) · TextractM in + Θ(|E|) · TdecreaseKey

Antwort: Jeder Teilweg eines k¨urzesten Weges ist ebenfalls ein k¨urzester Weg. Betrachten wir

einen k¨urzesten Weg (v0, v1, v2, . . . , vk) von v0 nach vk. Dann ist jeder Teilweg von vi nach vj

f¨ur i < j auch ein k¨urzester Weg von vi nach vj

Cut and paste: G¨abe es einen k¨urzeren Weg von vi nach vj , dann k¨onnte auch der Weg von v0

nach vk verkürzt werden.

Antwort: Wir zeigen, dass d[v] = δ(s, v) gilt, wenn v zur Menge S hinzu genommen wird. Da

die Werte von d[v] nur kleiner werden k¨onnen, ist damit die Aussage gezeigt.

Angenommen, u ist der erste Knoten, der zu S hinzu

genommen wird, f¨ur den d[u] 6 = δ(s, u) gilt. Sei y der

erste Knoten aus V − S auf einem k¨urzesten Weg von s

nach u, und sei x der Vorg¨anger von y auf diesem Weg

• Es gilt d[x] = δ(s, x), da u der erste Knoten ist, der die Invariante verletzt.

• Da Teilwege von k¨urzesten Wegen auch k¨urzeste Wege sind, wurde d[y] sp¨atestens dann

auf δ(s, x) + c((x, y)) = δ(s, y) gesetzt, als die Kante (x, y) nach Hinzunahme von x zu S

untersucht wurde. Also gilt d[y] = δ(s, y).

• Ferner gilt δ(s, y) ≤ δ(s, u), denn c : E → R+

0 .

• Außerdem gilt δ(s, u) ≤ d[u], weil der k¨urzeste Weg h¨ochstens so lang ist wie ein konkreter

Weg.

• Aber es gilt d[u] ≤ d[y], weil der Algorithmus u und nicht y w¨ahlt.

• Also muss d[y] = δ(s, y) = δ(s, u) = d[u] gelten CRASH

Antwort: Betrachten wir dazu ein Beispiel

• Der minimale Spannbaum im nebenstehenden Graphen ist ein-

deutig und durch die gr¨un markierten Kanten gekennzeichnet.

• Der k¨urzeste Weg von a nach d ist allerdings durch die Kante

{a, d} gegeben, die nicht zum minimalen Spannbaum geh¨ort.

Antwort: single source shortest paths

Antwort:

• Die ¨außere Schleife wird (V − 1)-mal durchlaufen.

• Die innere Schleife wird E-mal durchlaufen.

• Alle Operationen der inneren Schleife kosten Zeit O(1).

→ Gesamte Laufzeit in Θ(V · E).

Antwort: Ein k¨urzester Weg, der keine negativen Kreise enth¨alt, besucht keinen Knoten zwei-

mal. Daher besteht ein solcher Weg aus h¨ochstens V − 1 Kanten.

Der Graph G enthalte keine negativen Kreise.

• Sei v ∈ V ein beliebiger Knoten, und betrachte einen k¨urzesten Weg p von s nach v mit

minimaler Anzahl Kanten.

Da p k¨urzester Weg ist: δ(s, vi) = δ(s, vi−1) + c((vi−1, vi)).

• Initial gilt: d[v0] = 0 = δ(s, v0)

• Wir betrachten die Durchl¨aufe der ¨außeren Schleife:

– nach 1. Durchlauf durch E gilt: d[v1] = δ(s, v1).

– nach 2. Durchlauf durch E gilt: d[v2] = δ(s, v2).

...

– nach k. Durchlauf durch E gilt: d[vk] = δ(s, vk).

• Ein k¨urzester Weg besteht aus h¨ochstens V − 1 Kanten.

Antwort: Mittels dynamischer Programmierung all-pairs-shortest-path berechnen.

Sei dk

ij die L¨ange eines k¨urzesten Weges von i nach j, der nur ¨uber Knoten mit Nummern kleiner

gleich k l¨auft. Dann gilt:

Antwort: Weil es nicht funktioniert, da die k¨urzesten Wege nicht erhalten bleiben, wie folgendes

Beispiel zeigt.

• Der k¨urzeste Weg zwischen Startknoten s und Zielknoten z ist jeweils gr¨un markiert.

• Links ist der Originalgraph zu sehen, im rechten Graphen wurde auf jedes Kantengewicht

der Wert 4 addiert.

Antwort: Gegeben ist ein ungerichteter, gewichteter, vollst¨andiger Graph G = (V, E, c) und

eine Zahl k ∈ N. Die Frage ist, ob ein Hamilton-Kreis in G existiert, sodass die Summe der

Kantengewichte auf diesem Kreis h¨ochstens k ist? Ein Hamilton-Kreis ist ein Kreis im gegebenen

Graphen, der genau einmal durch jeden Knoten aus V l¨auft und wieder am Startknoten endet.

Greedy-Heuristik: W¨ahle vom letzten Punkt der Route den unbesuchten Punkt mit geringstem

Abstand aus. Die Laufzeit ist in O(V2).

Antwort: Gegeben ist ein ungerichteter Graph G = (V, E) und eine Zahl k ∈ N. Gesucht ist

eine Antwort auf die Frage, ob eine Menge V ′ ⊆ V der Gr¨oße h¨ochstens k existiert, sodass jede

Kante e = {u, v} ∈ E inzident zu einem Knoten in V ′ ist, dass also u ∈ V ′ oder v ∈ V ′ gilt

C := ∅

while es gibt noch Kanten in G do

nimm irgendeine Kante {u, v} von G

nimm u und v beide in C auf

entferne u und v und alle dazu inzidenten Kanten aus G

Sei F die Menge der ausgew¨ahlten Kanten, sei C das berechnete Vertex-Cover und sei {u, v} ∈

F . Jedes Vertex-Cover C′ muss u oder v enthalten, da sonst die Kante {u, v} nicht abgedeckt

w¨urde. Also gilt:

Antwort: Erweitere schrittweise eine Teill¨osung zu einer Gesamtl¨osung, ¨ahnlich wie bei Greedy,

aber getroffene Entscheidungen werden ggf. wieder r¨uckg¨angig gemacht.

• W¨ahle initial ein Element a1 ∈ A1 als m¨ogliche Teill¨osung.

• Solange a1, . . . , ai noch keine Gesamtl¨osung ist:

– W¨ahle ein Element ai+1 ∈ Ai+1 aus.

– Falls a1, a2, . . . , ai+1 konsistent ist, f¨uge ai+1 der Teill¨osung hinzu, sonst w¨ahle ein

anderes Element aus Ai+1 aus.

– Falls kein Element ai+1 gefunden wird, das zu einer Gesamtl¨osung f¨uhrt, gehe zur¨uck

(backtrack) und w¨ahle ai neu. (Falls kein ai mehr gew¨ahlt werden kann, gehe zur¨uck

zu ai−1 usw.)

• Gib die L¨osung a1, a2, . . . , am aus

Antwort: Anwendung bei Entscheidungs- bzw. Suchproblemen wie Graphf¨arbung, Sudoku

oder Brett-Solitaire, wenn keine Berechnungsvorschrift bekannt ist

Antwort: Findet eine L¨osung wie Backtracking, gibt sich aber nicht mit der ersten gefundenen

L¨osung zufrieden, sondern setzt die Suche fort, um ggf. eine bessere L¨osung zu finden. Wird

eingesetzt, um Optimierungsprobleme wie TSP zu l¨osen.

Branch-and-Bound besteht aus zwei Teilen.

• Branch: Verzweige wie Backtracking im Lösungsraum.

• Bound: Schneide bestimmte Zweige des Baumes ab, um den Rechenaufwand zu begrenzen.

→ Falls eine Teill¨osung nicht mehr zu einer optimalen L¨osung erweitert werden kann, beende

die Suche im aktuellen Zweig und gehe zur¨uck zu einer fr¨uheren Teill¨osung.

Antwort: Sch¨atzungen f¨ur die Restkosten bis zum Ziel vom Zustand s aus:

• h1(s): Anzahl Pl¨attchen, die an falscher Stelle liegen.

• h2(s): Summe der Entfernungen aller Pl¨attchen zu dessen Zielposition, also die Summe

der Manhatten-Distanzen.

Antwort: Absch¨atzung der Restkosten beim Traveling-Salesperson-Problem:

• Jede der noch nicht besuchten St¨adte muss besucht und auch wieder verlassen werden.

– Addiere jeweils die Werte der zwei kosteng¨unstigsten Kanten, die inzident zu einem

noch unbesuchten Knoten sind.

– Die Summe muss noch durch 2 dividiert werden, da jede Kante zweimal genutzt

wird, um einen Knoten zu verlassen und um den n¨achsten zu besuchen.

• oder: Berechne f¨ur die noch nicht besuchten Knoten einen minimalen Spannbaum.

– L¨asst man auf einer Rundreise eine Kante weg, erh¨alt man einen Spannbaum.

– Die Kosten eines minimalen Spannbaums sind also h¨ochstens so groß wie die Kosten

einer minimalen Rundreise.

Antwort: Basiert auf der Nachbarschaft N (s) von Zust¨anden s. Der Nachbar n ∈ N (s) eines

Zustands s beschreibt einen ”¨ahnlichen“ Zustand wie s.

Bestimme eine beliebige Startl¨osung s. Bestimme die Nachbarschaft N (s) von s. ¨Ubernehme

eine neue L¨osung aus der Nachbarschaft, falls diese besser ist als die alte L¨osung. Um lokale

Optima zu vermeiden, starte mit verschiedenen initialen L¨osungen