Nachdem Algatha nun sicher ist, dass sie sich keine »unlösbaren« Probleme eingehandelt hat, beginnt die große Diskussion in ihrer Abteilung: Wie gehen wir vor? Wie speichern wir die Daten im Computer? Wenn Algatha fünf Kollegen um ihre Meinung bittet, bekommt Sie wenigstens sieben Lösungsideen an den Kopf geworfen. Also entschließt sie sich, nach dem Motto »Erst tun, dann denken!« zu handeln. Sie beginnt einfach mit den einfachsten Ansätzen für die Lösung der Probleme.
Transcript
Nachdem Algatha nun sicher ist, dass sie sich keine »unlösbaren« Probleme eingehandelt hat,beginnt die große Diskussion in ihrer Abteilung: Wie gehen wir vor? Wie speichern wir die Datenim Computer? Wenn Algatha fünf Kollegen um ihre Meinung bittet, bekommt Sie wenigstenssieben Lösungsideen an den Kopf geworfen.
Also entschließt sie sich, nach dem Motto »Erst tun, dann denken!« zu handeln. Sie beginnteinfach mit den einfachsten Ansätzen für die Lösung der Probleme.
.
3 Einfache Ansätze
Joe Turner: These things are really pretty simple– they just look complicated.
Bei dem Mengenproblem müssen verschiedene Datenelemente so gespei-chert werden, dass die Menge leicht verwaltbar ist. In Definition 1.1 wurdedieses Problem so eingeführt, dass doppelte Schlüssel nicht erlaubt sind.Zur Vereinfachung wollen wir in diesem Kapitel diese Forderung nicht be-achten. Andernfalls müsste bei jedem Einfügen geprüft werden, dass dasElement noch nicht enthalten ist – was gerade bei den einfachen Verfahrenden Blick auf die wesentliche Vorgehensweise der Algorithmen verstellt.Stattdessen nehmen wir einfach an, dass der Nutzer die vorgestellten Da-tenstrukturen korrekt benutzt und doppelte Schlüssel vermeidet.
3.1.1 Unsortierte Ablage in einem Feld
Zunächst betrachten wir die in den meisten Sprachen schon vorgeseheneDatenstruktur des Felds (engl. Array). Um den Ansatz zunächst möglichst
5 6 7 81 2 3 4
3 9 5 1
Von vorn gefülltes Feld.einfach zu halten, legen wir die gespeicherten Elemente in einer beliebigen,unsortierten Reihenfolge ab – füllen unser Feld aber immer lückenlos vonvorn.
Neben dem eigentlichen Feld A wird die Anzahl der gespeicherten Ein-träge in einer Variablen belegteFelder abgelegt. Für einen Feldeintrag A[i]bezeichnen ferner A[i].wert den Schlüssel des Elements und A[i].daten daszugehörige Datenobjekt.
Die Suche nach einem bestimmten Element gestaltet sich so, dass nach-einander von vorn nach hinten jedes Element betrachtet wird (Algorith-mus 3.1). Sobald das Element gefunden ist, bricht die Suche ab. Falls es
nicht vorhanden ist, werden alle belegteFelder Elemente betrachtet und ei-ne entsprechende Fehlermeldung zurückgegeben.
Beispiel 3.1:
5 6 7 81 2 3 4
3 9 5 1
Suche nach der 5.Der Ablauf von Algorithmus 3.1 ist beispielhaft für die Suche nach demElement mit dem Schlüssel 5 rechts dargestellt. �
Satz 3.2:
Die Laufzeit für Suchen-Feld beträgt im Worst-Case und im Average-CaseΘ(n).
Beweis 3.3:
Im ungünstigsten Fall ist das gesuchte Element ganz rechts (oder gar nichtenthalten). Dann müssen alle n Elemente der Reihe nach überprüft werden.Für den Average-Case bilden wir den Mittelwert der Laufzeit über alle ent-haltenen Elemente:
T (n) =1n·
n∑i=1
i =1n· n · (n+1)
2∈ Θ(n)
In Einfugen-Feld (Algorithmus 3.2) wird das neue Element an die erste freieStelle im Feld eingefügt – sofern das Feld nicht voll ist. Diese Stelle kannman direkt mittels der Variablen belegteFelder identifizieren. Die Laufzeitbeträgt Θ(1).
Beispiel 3.4:
Im nebenstehenden Beispiel fügen wir das Element mit dem Schlüssel 7ein. �
5 6 7 8
5 6 7 81 2 3 4
3 9 5 1
belegteFelder = 4
1 2 3 4
3 9 5 1
belegteFelder = 5
Einfugen
7
Ablauf von Algorithmus 3.2.
Beim Löschen (Loschen-Feld in Algorithmus 3.3) muss zunächst das zu lö-schende Element gesucht werden, welches dann durch das ganz rechts ste-hende Element ersetzt wird. Die Laufzeit ergibt sich wie bei der Suche alsO(n).
Algorithmus 3.1 Suchen in der Datenstruktur Feldwww
Feld.javaSuchen-Feld(Schlüssel gesucht)
Rückgabewert: gesuchte Daten bzw. Fehler falls nicht enthalten1 index← 12 while index ≤ belegteFelder und gesucht � A[index].wert3 do � index← index+1�4 if index > belegteFelder5 then � error “Element nicht gefunden”�6 else � return A[index].daten�
�
�
Prüfe Elementevon links nachrechts
�
�
Ausgabe
3.1. Datenstrukturen für das Mengenproblem 45
Algorithmus 3.2 Einfügen in die Datenstruktur Feldwww
Rückgabewert: nichts falls erfolgreich bzw. Fehler sonst1 if belegteFelder = A.lange2 then � error “Feld ist voll”�3 else � A[belegteFelder+1].wert← neuerWert4 A[belegteFelder+1].daten← neueDaten5 belegteFelder← belegteFelder+1�
�
�
hinten anfügen
Algorithmus 3.3 Löschen in der Datenstruktur Feldwww
Feld.javaLoschen-Feld(Schlüssel loschWert)
Rückgabewert: nichts falls erfolgreich bzw. Fehler sonst1 index← 12 while index ≤ belegteFelder und loschWert � A[index].wert3 do � index← index+1�4 if index > belegteFelder5 then � error “ Element nicht gefunden ”�6 else � A[index]← A[belegteFelder]7 belegteFelder← belegteFelder−1�
�
�
schonenthalten?
�
�
Element entfernen
Beispiel 3.5:
Im nebenstehenden Beispiel löschen wir das Element mit dem Schlüssel 9ein. Das letzte Element wird an die frei gewordene Stelle kopiert. �
5 6 7 8
5 6 7 81 2 3 4
3 7 5 1
belegteFelder = 4
1 2 3 4
3 9 5 1
belegteFelder = 5
Ersetzen mitSuchen
7
Ablauf von Algorithmus 3.3.
Sollen alle Elemente des Felds ausgegeben werden, kann dies wie in Algo-rithmus 3.4 ebenfalls durch sequentielle Ausgabe der Elemente von linksnach rechts geschehen. Die Laufzeit ist ebenfalls Θ(n).
3.1.2 Unsortierte Ablage in einer verketteten Liste
Während die Anzahl der speicherbaren Elemente beim Feld anfangs einmalfestgelegt wird, können in den meisten Programmiersprachen über sog. Zei-ger dynamische Datenstrukturen für theoretisch unbegrenzt viele Elementedefiniert werden.
Algorithmus 3.4 Alle Elemente der Datenstruktur Feld ausgebenwww
Feld.javaAlle-Feld()
Rückgabewert: nichts, da direkte Ausgabe1 index← 12 while index ≤ belegteFelder3 do � drucke: A[index].daten4 index← index+1�
46 Kapitel 3. Einfache Ansätze
Definition 3.6: Dynamische Datenstruktur
Eine dynamische Datenstruktur ist dadurch charakterisiert, dass der Spei-�dynamische Datenstruktur
cher für jedes Element wenn benötigt einmal angelegt wird und zusätzlichdie Anordnung/Struktur der Elemente durch Verweise (oder Zeiger) jeder-zeit änderbar ist.
Wir betrachten in diesem Abschnitt die verkettete Liste als ein Beispiel füreine dynamische Datenstruktur.
Definition 3.7: Verkettete Liste
Eine verkettete Liste ist eine dynamische Datenstruktur, in der die Elemen-�verkettete Listete linear angeordnet sind. Jedes Element e� der Liste enthält einen Schlüs-sel e�.wert, die zugehörigen Daten e�.daten sowie einen Verweis, den sog.Zeiger, auf das nächste Element e�.nachstes. Eine Liste besteht dann ausdem Verweis anker auf das erste Element der Liste und allen Elemente, die
3 9anker
5
Schlussel
nachstes Element
Aufbau einer verketteten Liste.durch die Verweise erreichbar sind.
Um die Operationen der verketteten Liste vorzustellen, betrachten wir eini-ge Besonderheiten der Zeiger. Während »normale« Variablen einen in sich�Zeiger
abgeschlossenen Wert, z.B. eine ganze Zahl, aufnehmen können, verwei-sen Zeiger auf eine Information, die an einer anderen Stelle im Speicherliegt. Da dies in den Algorithmen, insbesondere bei Zuweisungen, immerwieder zu Verständnisproblemen führen kann, möchten wir in der Notationdes Pseudo-Codes die Art der Zuweisung reflektieren. So wird eine norma-le Wertzuweisung wie in den bereits vorgestellten Algorithmen durch denPfeil nach links dargestellt.
wert← 127summe← wert+42
Der links stehenden Variable wird der Wert zugewiesen, der sich bei derAuswertung des rechts stehenden Ausdrucks ergibt. Bekommt wert spätereinen anderen Wert zugewiesen, ändert sich der Inhalt von summe nicht.
Bei Variablen, die einen Zeiger enthalten, ist dies nicht so einfach: Daes sich nur um Verweise handelt, können verschiedene Zeigervariablen aufdieselben Speicherstellen zeigen und es kann passieren, dass sich durcheinen Zeiger die Speicherstelle ändert, ohne dass der andere Zeiger ange-fasst wird. Als Konsequenz kann sich der durch die andere Zeigervariableerreichbare »Wert« ändern. Daher wird in diesem Buch im Weiteren eineZuweisung an eine Zeigervariable durch einen Pfeil nach rechts dargestellt.
Algorithmus 3.5 Suchen eines Elements in einer verketteten Listewww
Liste.javaSuche-Liste(Schlüssel gesucht)
Rückgabewert: gesuchte Daten bzw. Fehler falls nicht enthalten1 e�→ anker2 while e� � null3 do � if e�.wert = gesucht4 then � return e�.daten�5 else � e�→ e�.nachstes��6 error “Element nicht gefunden”
�
�nächstes Element untersuchen
�
�gefundenes Element zurückgeben
�
�Ende der Liste erreicht?
Nach der Zuweisung zeigt die links stehende Variable auf die Speicherstelle,die sich aus der Auswertung des rechts stehenden Ausdrucks ergibt. In derersten Zeile wird eine neue Speicherstelle für ein Listenelement angefordertund mit dem Wert 5, den daten und der Zeigervariable null belegt, wobeider spezielle Wert null bedeutet, dass diese Variable im Moment auf keineSpeicherstelle verweist. anker zeigt auf dieses Listenelement. Der Ablaufdes kleinen Beispiels wird in vier Bildern auf dem Rand veranschaulicht.
5anker
Beispiel nach Zeile 1.
In der zweiten Zeile wird ein weiteres Listenelement mit dem Wert 7,den daten′ und dem Zeiger auf den alten anker angelegt. anker zeigt jetztauf dieses Element. In diesem Fall ist sofort deutlich, dass sich das Element,auf das anker zeigt, geändert hat.
7 5anker
Beispiel nach Zeile 2.
In der dritten Zeile jedoch wird eine weitere Zeigervariable e� eingeführt,die auf dasselbe Element zeigt wie anker. In der vierten Zeile wird über 7 5
anker
e�Beispiel nach Zeile 3.
den Zeiger e� der Zeiger des Elements mit dem Wert 7 auf null gesetzt.Hierdurch ändert sich das Element, auf das anker verweist, ohne dass esdirekt für anker deutlich wird. 7 5
anker
e�Beispiel nach Zeile 4.Das kenne ich aus dem echten Leben! Wenn ich ein Textdoku-
ment per E-Mail an meinen Chef schicke, dann ist das wie eine»Zuweisung« – ich kann seine Änderungen nicht direkt sehen.Aber als ich in der Firma zum Projektleiter befördert wurde,wurde wie bei einer Zeigervariablen nur ein neuer Alias »Pro-jektleiterin Algatha« eingeführt – und wenn ich mir die Haareschneide, ändert sich der Zustand sowohl aus der Sicht »Pro-jektleiterin Algatha« als auch aus der Sicht meines Freundes(und wie er mich nennt, werde ich hier nicht verraten!)
Das Suchen eines Elements in einer verketteten Liste wird hier in zweiVersionen behandelt. Wir betrachten zunächst Algorithmus 3.5 (Suche-Liste).Dieser geht iterativ vor, d.h. in einer Schleife wird eine Variable e� immer �iterativso weiter gesetzt, dass sie nacheinander auf die einzelnen Elemente zeigt.
Beispiel 3.8:
Im nebenstehenden Beispiel wird bei einer Suche nach dem Element 9 dieVariable e� auf die angezeigten Elemente gesetzt. �
3
21
anker5
e�
9
Ablauf von Algorithmus 3.5.
48 Kapitel 3. Einfache Ansätze
Die Laufzeit ist in O(n) bei einer Liste mit n Elementen, da die Zahl derIterationen der While-Schleife durch die Länge der Liste begrenzt ist.
Der zweite Ansatz zum Suchen in einer Liste arbeitet rekursiv. Da diesein sehr wichtiges Konzept der Informatik und auch insbesondere der Algo-rithmik ist, wollen wir uns genauer damit beschäftigen. Im weiteren Verlaufdes Buchs viele der Algorithmen sind rekursiv formuliert.
Definition 3.9: Rekursive Algorithmen
Ein Algorithmus heißt rekursiv, wenn er sich (direkt oder indirekt) selbst�rekursivaufruft.
Die zwei wichtigen Bestandteile eines rekursiven Algorithmus sind
• die eigentliche Berechnung, die insbesondere auch den rekursiven Auf-ruf enthält, – diese Berechnung entspricht inhaltlich einer Iteration imäquivalenten iterativen Algorithmus – und• die Abbruchbedingung, die prüft, ob überhaupt noch eine Berechnung
notwendig ist, und ggf. die Rekursion beendet.
Soll also das Suchen in einer Liste rekursiv umgesetzt werden, entsprichtder Aufruf der Funktion dem Überprüfen eines einzelnen Elements in derListe. Die Abbruchbedingung berücksichtigt zwei verschiedene Situatio-nen: Falls erstens das Ende der Liste erreicht ist, kann der gesuchte Schlüs-sel gar nicht mehr überprüft werden – die Suche bricht mit einer entspre-chenden Misserfolgsmeldung ab. Falls zweitens das betrachtete Elementden gesuchten Schlüssel aufweist, kann die Suche ebenfalls beendet wer-den – allerdings jetzt mit einer Erfolgsmeldung. Stimmt der Schlüssel nichtüberein, kommt die Rekursion zum Tragen, die in diesem Algorithmusdenkbar einfach ist: Durch den rekursiven Aufruf wird die Suche beimnächsten Element fortgesetzt.
Suche-Liste-Rek (Algorithmus 3.6) zeigt die rekursive Beschreibung imDetail. Die eigentlich Rekursion steckt dabei im Algorithmus Suche-Liste-R, der den Verweis auf das nächste zu betrachtende Element als Parameterübergeben bekommt. Der Algorithmus Suche-Liste-Rek stellt lediglich dieeinheitliche Schnittstelle wie bei den anderen Such-Algorithmen zur Verfü-gung, in dem die Daten des in Suche-Liste-R gefundenen Elements ausgege-ben werden.
Es schwieriger ist, einen rekursiven als einen iterativen Algorithmusnachzuvollziehen, da man den Überblick über mehrere Aufrufe des Algo-rithmus behalten muss. Wir möchten daher in den Erklärungen des nach-folgenden Beispiels darauf zurückgreifen, wie der Computer selbst die ver-schiedenen Aufrufe verwaltet. Jeder Aufruf wird auf einem sog. Laufzeit-stapel abgelegt – einschließlich der übergebenen Parameterwerte, der Werte�Laufzeitstapel
der lokalen Variablen und der Information, welche Anweisung zuletzt be-arbeitet wurde. Wird aus einem Algorithmus A ein anderer Algorithmus B
3.1. Datenstrukturen für das Mengenproblem 49
Algorithmus 3.6 Rekursives Suchen eines Elements in einer verketteten Listewww
Liste.javaSuche-Liste-Rek(Schlüssel gesucht)
Rückgabewert: gesuchte Daten bzw. Fehler falls nicht enthalten1 return Suche-Liste-R(gesucht, anker).daten
Suche-Liste-R(Schlüssel gesucht, Element e�)Rückgabewert: Element mit gesuchten Daten bzw. Fehler
1 if e� � null2 then � if e�.wert = gesucht3 then � return e��4 else � return Suche-Liste-R(gesucht, e�.nachstes)��5 else � error “Element nicht gefunden”�
�
� nächstesElement untersuchen
�
�gefundenes Element zurückgeben
�
�Ende der Liste erreicht?
aufgerufen, liegen die Informationen übereinander, wie bei einem Papier-stapel (vgl. nebenstehende Abbildung). Wird der Algorithmus B beendet,
wachst
in
diese
Richtung
A
B
Laufzeitstapel.
setzt Algorithmus A seine Ablauf nach dem Aufruf von B fort. Bei einemrekursiven Algorithmus befinden sich also mehrere Aufrufinstanzen des Al-gorithmus mit unterschiedlichem Status der Variablen etc. auf dem Lauf-zeitstapel.
Beispiel 3.10:
Wir setzen das Beispiel 3.8 fort und betrachten die rekursive Suche nachdem Element 9. Bild 3.1 zeigt von links nach rechts, welche Aufrufe aufdem Laufzeitstapel abgelegt werden: Der Aufruf Suche-Liste-Rek reicht denVerweis auf das erste Element als Parameter des ersten Aufrufs von Suche-Liste-R weiter. Da das Element nicht übereinstimmt, folgt ein zweiter Auf-ruf von Suche-Liste-R, der das Nachfolgeelement mit dem Schlüssel 9 über-geben bekommt. Da der Schlüssel mit dem gesuchten Schlüssel überein-stimmt, bricht die Rekursion ab. Der Verweis auf das gesuchte Element
S-L
S-L-R
S-L
S-L-R
S-L-R
S-L
3anker
59
S-L
S-L-R
S-L
Bild 3.1: Für Suche-Liste-Rek (Algorithmus 3.6) werden die Veränderungen aufdem Laufzeitstapel dargestellt. Die Zeit schreitet von links nach rechtsvoran und S-L steht für Suche-Liste-Rek während S-L-R eine Abkür-zung für Suche-Liste-R ist. Der Aufrufparameter wird jeweils direkt mitangegeben, die Rückgabewerte in den orangefarbigen Kästchen.
50 Kapitel 3. Einfache Ansätze
Algorithmus 3.7 Einfügen in eine verkettete Listewww
wird als Rückgabewert über die Return-Anweisung an den vorherigen Al-gorithmusaufruf auf dem Laufzeitstapel zurückgegeben. �
Auch das kenne ich! Wenn ich ein Kochrezept nicht finde, rufeich bei meiner Mutti an – die dann bei meiner Tante fragt, diewiederum bei ihrer Nachbarin. . .
Da die Elemente bei der rekursiven Variante in genau der gleichen Rei-henfolge wie beim iterativen Algorithmus besucht werden, ergibt sich auchhier eine Laufzeit in O(n). Im Worst-Case muss bis zum Ende der Listegesucht werden, wodurch sich Laufzeit Θ(n) ergibt.
Als technologische Grundlage für rekursive Programmierung wurdeder Laufzeitstapel – auch als Keller, Kellerspeicher oder Stack be-zeichnet – von Samelson & Bauer (1959) erfunden. Darauf basiertauch die Datenstruktur des Stacks, die in den Übungsaufgaben 3.6und 3.7 behandelt wird und in den weiteren Kapiteln immer wiederals Hilfsdatenstruktur benutzt wird.
Auch beim Einfügen in die Liste lassen wir in diesem Kapitel zunächstdoppelte Schlüssel zu. Dadurch können wir ein neues Element ungeachtetdes Rests der Liste vorn einhängen. Einfugen-Liste in Algorithmus 3.7 zeigt,wie dies umgesetzt wird. Die Laufzeit ist Θ(1).
Beispiel 3.11:
Im nebenstehenden Beispiel für den Algorithmus 3.7 wird das Element 8in die Liste eingefügt. �
3anker
59
8
Ablauf von Algorithmus 3.7.
Beim Löschen muss zunächst das zu entfernende Element gesucht wer-den. Anschließend kann es aus der Liste entfernt werden, indem der Zeigernachstes des Vorgängerelements auf das Nachfolgerelement gesetzt wird.
Beispiel 3.12:
Dies ist im nebenstehenden Beispiel für das Löschen des Elements 9 gut zuerkennen. �
38 59
anker
Ablauf von Algorithmus 3.8.
Hierfür betrachten wir eine iterative und eine rekursive Variante des Algo-rithmus, um beide im Vergleich sehen zu können. Insbesondere soll ein
3.1. Datenstrukturen für das Mengenproblem 51
Gefühl für die rekursive Vorgehensweise entstehen, da im weiteren Verlaufdes Buches viele Algorithmen rekursiv formuliert sind.
Der iterative Algorithmus 3.8 behandelt zunächst zwei Sonderfälle: ei-nerseits den Fall, dass die Liste leer ist, und andererseits das Löschen desersten Elements, wodurch sich der Verweis in der Variablen anker ändert.Anschließend wird der Zeiger e� durch die Liste geschoben und sucht denVorgänger des zu löschenden Elements.
Die Behandlung von Sonderfällen ist immer ärgerlich. Wie wir im nach-folgenden Kapitel bei der sortierten Liste sehen werden, kann die gesonder-te Behandlung des ersten Elements entfallen, wenn wir ein leeres Blindele-ment am Anfang einfügen.
Der rekursive Algorithmus 3.9 ist etwas eleganter als obige iterative Vari-ante, da er den Sonderfall des ersten Elements durch den Aufruf in Loschen-Liste-Rek abdeckt und der Fall der leeren Liste durch dieselbe Anweisungwie der Abbruch der Suche behandelt wird.
Beide Algorithmen besitzen die Laufzeit O(n).
Algorithmus 3.8 Löschen in einer verketteten Listewww
Liste.javaLoschen-Liste(Schlüssel loschWert)
Rückgabewert: nichts falls erfolgreich bzw. Fehler sonst1 switch
2 case anker = null : error “Element nicht enthalten”3 case anker � null und anker.wert = loschWert :4 anker→ anker.nachstes5 case anker � null und anker.wert � loschWert :6 e�→ anker7 while e�.nachstes � null und e�.nachstes.wert � loschWert8 do � e�→ e�.nachstes�9 if e�.nachstes � null
10 then � e�.nachstes→ e�.nachstes.nachstes�11 else � error “Element nicht gefunden”�
�
�Element entfernen
�
�
Element suchen
�
�
Sonderfall:erstes Element
�
�
Sonderfall:leere Liste
Algorithmus 3.9 Rekursives Löschen in einer verketteten Listewww
Liste.javaLoschen-Liste-Rek(Schlüssel loschWert)
Rückgabewert: nichts falls erfolgreich bzw. Fehler sonst1 anker→ Loschen-Liste-R(loschWert, anker)
Loschen-Liste-R(Schlüssel loschWert,Element e�)Rückgabewert: neues erstes Element bzw. Fehler sonst
1 if e� � null2 then � if e�.wert = loschWert3 then � return e�.nachstes�4 else � e�.nachstes→ Loschen-Liste-R(loschWert, e�.nachstes)5 return e���6 else � error “Element nicht gefunden”�
�
�erster Aufruf derrekursiven Funktionsetzt ggf. den Anker neu
�
�Element entfernen�
�
rekursiv im Rest der Liste
52 Kapitel 3. Einfache Ansätze
Algorithmus 3.10 Ausgabe aller Elemente einer verketteten Listewww
Liste.javaAlle-Liste()
Rückgabewert: nichts, da direkte Ausgabe1 e�→ anker2 while e� � null3 do � drucke: e�.daten4 e�→ e�.nachstes�
Algorithmus 3.10 zur Ausgabe aller Elemente ist der Vollständigkeit hal-ber ebenfalls mit angeführt.
3.1.3 Unsortierte Ablage in einem dynamischen Feld
Felder haben gegenüber Listen den großen Vorteil, dass man direkt mitkonstantem Aufwand Θ(1) auf jedes beliebige Element A[i] mit seinemIndex i zugreifen kann. Einzig die vorgegebene Feldgröße wurde im Ab-schnitt 3.1.1 als nachteilig erkannt. Daher soll in diesem Abschnitt das Stan-dardfeld so modifiziert werden, dass sich die Größe dynamisch anpasst.
Dabei ändert sich am Aufbau der Datenstruktur zunächst nichts – wirmachen uns lediglich die in der Programmiersprache Java typische Eigen-schaft der Felder zu nutzen, welche dort als Objekte behandelt werden. Dasbedeutet, ein Feld A ist eigentlich ein Zeiger auf einen dynamisch angeleg-ten Speicherbereich. Dieser kann folglich auch gegen einen größeren oderkleineren Speicherbereich ausgetauscht werden.
Das Einfügen ist in Algorithmus 3.11 beschrieben: Wenn für ein neuesElement kein Platz vorhanden ist, wird ein größeres Feld angelegt, die altenWerte umkopiert und das neue Element hinten angehängt. In der Versiondes Algorithmus in diesem Buchs wird das Feld um 50% vergrößert.
Beispiel 3.13:
Im nebenstehenden Beispiel ist das Feld der Länge 6 voll, sodass das Ele-ment mit dem Schlüssel 2 nicht eingefügt werden kann. Daher wird einneues Feld der Länge 9 angelegt und alle Elemente umkopiert. Anschlie-ßend kann das neue Element problemlos eingefügt werden. �
1 2 3 4
3 9 5 1
5 6
8 7
1 2 3 4
9 5 1
5 6 7 8 9
8 23
A
7Ablauf von Algorithmus 3.11.
Algorithmus 3.11 Einfügen in ein dynamisches Feldwww
Rückgabewert: nichts falls erfolgreich bzw. Fehler sonst1 if belegteFelder = A.lange2 then � B→ allokiere Feld der Länge � 3
2 ·A.lange�3 for index← 1, . . . , belegteFelder4 do � B[index].wert← A[index].wert5 B[index].daten← A[index].daten�6 A→ B�7 Einfugen-Feld(neuerWert, neueDaten)
�
�
Lege eingrößeres Feld an
�
�
Kopieren derbisherigen Werte
�
�neues Feld ersetzt altes
3.1. Datenstrukturen für das Mengenproblem 53
Moment mal, der Name »dynamisches Feld« ist aber schlechtgewählt: Da meint man ja gleich, dass es eine dynamische Da-tenstruktur ist! Aber das gilt ja gar nicht, weil immer wiederalle Werte umkopiert werden.
Es bleibt hier die Frage, inwieweit das Umkopieren in ein größeres Feld,die Laufzeit für das Einfügen verändert.
Satz 3.14:
Werden n Elemente in ein dynamisches Feld eingefügt, so ist der Gesamt-aufwand für das Umkopieren in O(n).
Beweis 3.15:
Nehmen wir zunächst an, dass beim letzten Element das Feld vergrößertund n−1 Elemente umkopiert wurden. Vorausgesetzt, dass zuvor des Feldauch schon vergrößert wurde, so wurden beim Mal davor � 2
3 · (n− 1)� Ele-mente kopiert. Damit können wir die gesamten umkopierten Elemente wiefolgt nach oben abschätzen.
T (n) ≤∞∑i=0
�(
23
)i· (n−1)� ≤ (n−1) ·
∞∑i=0
(23
)i︸���︷︷���︸
geometrische Reihe
= (n−1) · 11− 2
3
= 3 · (n−1) ∈ O(n).
Das benutzte Ergebnis der geometrischen Reihen kann Satz B.3 (Seite 339)entnommen werden.
Der Faktor 3 vor dem n−1 (bei n Elementen) zeigt an, dass sich die Laufzeitim Durchschnitt für jedes Einfügen eines Elements nur um einen konstan-ten Faktor erhöht.
Beim Löschen in Algorithmus 3.12 verfahren wir genau umgekehrt: Wirdder Füllgrad des Felds zu gering, wird es verkleinert, um den belegten Spei-cherplatz wieder frei zu geben. In dem hier präsentierten Algorithmus wirddas Feld um 1
3 verkleinert, wenn es weniger als 50% gefüllt ist.
Beispiel 3.16:
Wird im nebenstehenden Feld das Element mit dem Schlüssel 4 gelöscht,fällt der Füllgrad auf 4
9 . Dadurch wird das Feld von der Länge 9 auf einFeld der Länge 6 verkleinert. �
1 2 3 4
9 5 1
5 6 7 8 9
3 4
1 2 3 4
3 9 5 1
5 6
Ablauf von Algorithmus 3.12.
Bezüglich der Laufzeit gelten ähnliche Überlegungen wie beim Vergrößerndes Felds. Zusätzlich sieht man leicht ein, dass die Konstanten für das Ver-kleinern so gewählt wurden, dass nach einem Verkleinern des Felds erst
54 Kapitel 3. Einfache Ansätze
Algorithmus 3.12 Löschen im dynamischen Feldwww
DynFeld.javaLoschen-DynFeld(Schlüssel loschWert)
Rückgabewert: nichts falls erfolgreich bzw. Fehler sonst1 Loschen-Feld(loschWert)2 if belegteFelder < 1
2 ·A.lange und A.lange > 53 then � B→ allokiere Feld der Länge � 2
3 ·A.lange�4 for index← 1, . . . , belegteFelder5 do � B[index].wert← A[index].wert6 B[index].daten← A[index].daten�7 A→ B�
�
�
Füllgrad zu gering?
�
�
Lege einkleineres Feld an�
�
Kopieren derbisherigen Werte
�
�neues Feld ersetzt altes
16 · n Elemente eingefügt werden müssen, bis das Feld wieder vergrößertwird. Daher kann der mittlere Aufwand auch bei beliebiger Anordnung vonEinfüge- und Löschvorgängen auf einen konstanten Faktor pro Operationbeschränkt werden.
Die Algorithmen 3.1 (Suchen-Feld) für die Suche eines Elements und 3.4(Alle-Feld) für die Ausgabe aller Elemente werden unverändert aus Ab-schnitt 3.1.1 übernommen.
So wie die Firma expandiert, wissen wir oft nicht im Voraus,wie viele Daten anfallen. Dann sind natürlich Datenstrukturenmit variabler Größe eine tolle Sache! Das bietet sowohl dieverkettete Liste (als dynamische Datenstruktur) als auch dasdynamische Feld.
3.1.4 Laufzeitvergleich von Feld und Liste
Bisher lässt sich aus den Beschreibungen der Datenstrukturen keine verglei-chende, qualitative Aussage ableiten. Daher wollen wir in diesem Abschnittein kleines Laufzeitexperiment durchführen, um die Stärken und Schwä-chen der verschiedenen Verfahren auszuloten.
Hierzu benutzen wir einen Prozessor mit 1,6 GHz und eine Java-Runtime-Umgebung mit 512MB Heap-Speicher – das ist der frei verfügbare Spei-cher, aus dem Blöcke (nahezu) beliebiger Größe durch eine Speicherverwal-tung für neue Datenobjekte wie Felder oder Listenelemente zur Verfügunggestellt werden.
In dem Experiment speichern wir eine große Anzahl an ganzen Zahlenvom Typ long, d.h. mit 8 Bytes darstellbare Zahlen.
Betrachten wir zunächst Datenstrukturen, die bereits mit 21 500 000 Ele-menten befüllt wurden. Im letzten Element des Feldes bzw. der Liste befin-det sich derjenige Schlüsselwert, der gesucht wird. Wir messen die Zeit, diebenötigt wird, um alle Elemente mit dem gesuchten Wert zu vergleichen.Die gemessenen Laufzeiten sind in Tabelle 3.1 dargestellt. Man erkennt,
3.1. Datenstrukturen für das Mengenproblem 55
dass das Feld mit 164,8 ms die deutlich schnellste Variante darstellt. Beider Liste unterscheiden wir zwei Fälle:
1. Die einzelnen Datenobjekte wurden so allokiert, dass die Verkettungder Elemente linear wie eine Perlenkette im Speicher liegt. Dann be-trägt die Laufzeit 243,2 ms. Der Unterschied zum Feld rührt daher,dass man neben dem Zugriff auf die eigentliche Speicherstelle jedes-mal noch den Zeiger zum nächsten Element auswerten muss.
2. Die Datenobjekte der Liste sind so verzeigert, dass aufeinanderfol-gende Elemente der Liste in unterschiedlichen Bereichen des Heap-Speichers liegen und nur durch größere Sprünge erreicht werden. Dadann häufiger neue Speicherblöcke in den Hauptspeicher des Compu-ters geladen werden müssen, erhöht sich die Laufzeit auf 2,151 Sekun-den.
Wir halten fest: Die Liste ist von der Laufzeit her teurer und die konkreteLaufzeit hängt maßgeblich davon ab, an welchen Stellen die Objekte imSpeicher liegen.
Ferner hat uns interessiert, wie es sich mit den Laufzeiten beim Einfü-gen von 15 000 000 Elementen verhält. Die gemessenen Werte sind in deroberen Zeile von Tabelle 3.2 dargestellt. Bei den Laufzeiten zeigt erneutdas Feld die beste Laufzeit mit 380,6 ms, da dort nur einmal ein Feld ent-sprechender Größe im Speicher allokiert wird. Beim dynamischen Feld ver-fünffacht sich in unserem Beispiel der Laufzeitaufwand durch die mehrfa-che Allokation von Speicher und das Umkopieren der bereits gespeicherten
Tabelle 3.1: Laufzeiten beim kompletten Durchsuchen der Datenstruktur mit21 500 000 Elementen.
Datenstruktur Feld Liste(linearallokiert)
Liste(andersverzeigert)
Laufzeit 164,8 ms 243,2 ms 2,151 sec
Tabelle 3.2: Laufzeiten beim Einfügen von 15 000 000 Elementen und die Größen-ordnung der im Heap-Speicher speicherbaren Elemente.
Datenstruktur Feld Liste dynamischesFeld
Laufzeit beim Einfügenvon 15 000 000 Elemen-ten
380,6 ms 14,881 sec 1,819 sec
insgesamt speicherbareAnzahl an Elementen
43 000 000 21 619 000 20 767 725
56 Kapitel 3. Einfache Ansätze
Elemente. Bei der Liste jedoch wird mit 14,881 Sekunden eine fast nichtmehr akzeptierbare Größenordnung erreicht, die durch den Aufwand fürdie Speicherallokation für jedes einzelne Element erklärbar ist. Hierbei istes im Wesentlichen egal, wie die Speicherallokation der Liste strukturiertist.
Die untere Zeile von Tabelle 3.2 zeigt, wie viele Elemente mit der jewei-ligen Datenstruktur überhaupt im Speicher abgelegt werden konnten. Da-bei gehen wir von einem noch völlig unbenutzten Speicher aus. Dann kannein Feld für 43 000 000 Elemente allokiert werden. Bei der Liste sinkt dieAnzahl auf 21 619 000, da für jedes Element durch die Verzeigerung mehrPlatz benötigt wird. Beim dynamischen Feld, kann ein Feld für 20 767 725Elemente allokiert werden, da für die nächste Feldvergrößerung zwischen-zeitlich dieses und ein um 50% größeres Feld im Speicher Platz findenmüssten, wozu der Speicherplatz nicht ausreicht.
Das sieht ja, wie eine Bankrotterklärung für die Liste aus. Injeder Hinsicht ist das Feld überlegen! Eine lineare Liste werdeich nur für wenige Elemente benutzen.
Der wesentliche Vorteil der verketteten Liste ist die Flexibilität. Die Rei-henfolge der Elemente in einer Liste lässt sich mit wenig Aufwand ändern,solange die Stellen durch Zeiger direkt erreicht werden. Solche Änderun-gen benötigen in einem Feld oft mehr Zeit, da dann Elemente umkopiertwerden müssen.
Ein zweiter Vorteil der Liste ist der kleinteilige Speicherbedarf. Ist ineiner laufenden Anwendung der Speicher bereits stark fragmentiert, dannkann oft nur durch großen Aufwand ein passender zusammenhängenderSpeicherbereich für ein großes Feld bereit gestellt werden. Die Liste hatden Vorteil, dass sie sich aus vielen einzelnen verteilt im Speicher liegendenDatenobjekten zusammensetzt und damit weniger häufig Probleme mit derSpeicherverwaltung hat.
Letztendlich muss ein Programmierer entscheiden, ob er für die Vorteileder Liste mit der erhöhten Laufzeit bezahlen möchte oder ob er die mögli-chen Nachteile des Felds für die Laufzeitvorteile in Kauf nimmt.
3.2 Ein einfaches Sortierverfahren: Bubblesort
Eines der einfachsten Sortierverfahren, das sowohl auf Feldern als auchauf Listen mit gleichem Aufwand arbeitet, ist Bubblesort (Sortieren durchVertauschen von Nachbarn). Im Folgenden ist es für ein Feld formuliert.
Im Algorithmus 3.13 wird in den Zeilen 2–5 das Feld von links nachrechts nach benachbarten Feldern durchsucht, deren Inhalt falsch sortiertist. Diese Inhalte werden durch Aufruf von Algorithmus 3.14 vertauscht.Die Repeat-Until-Schleife wiederholt dies solange, bis das Feld sortiert ist.
3.2. Ein einfaches Sortierverfahren: Bubblesort 57
Algorithmus 3.13 Sortieren durch Vertauschen von Nachbarnwww
Bubblesort.javaBubblesort(Feld A)
Rückgabewert: nichts; Seiteneffekt: A ist sortiert1 repeat � warSortiert← true
2 for i← 1, . . . , A.lange−13 do � if A[i].wert > A[i+1].wert4 then �warSortiert← false
5 Vertausche(A, i, i+1)���6 until warSortiert
�
�
unsortierte Nachbarn tauschen�
�Ende, wenn keine Vertauschung mehr
Algorithmus 3.14 Vertauschen zweier Einträge im FeldVertausche(A[], i, j)
Rückgabewert: nichts; Seiteneffekt: A ist verändert1 h← A[i]2 A[i]← A[ j]3 A[ j]← h
Beispiel 3.17:
Bild 3.2 zeigt den Ablauf für zehn Elemente. Jede Zeile stellt das Feld nacheinem Durchlauf durch die Zeilen 2–5 dar. In diesem Beispiel wird dieRepeat-Until-Schleife 9 Mal durchlaufen, wodurch sich 9 · 9 = 81 Schlüs-selvergleiche ergeben. Zudem wird 60 Mal schreibend auf das Feld zuge-griffen. �
Beispiel 3.18:
Bild 3.3 zeigt mehrere Momentaufnahmen beim Sortieren von 80 Zahlen.Deutlich erkennt man, wie die größeren Elemente nach rechts »durchge-schoben« werden. �
Trotz der Einfachheit des Algorithmus ist ein Korrektheitsbeweis von Bub-blesort nicht gänzlich trivial. Bei iterativen Algorithmen, d.h. Abläufen, diedurch eine oder mehrere Schleifen organisiert sind, bietet sich der Beweisüber sog. Invarianten an. �Invariante
Definition 3.19: Schleifeninvariante
Eine Schleifeninvariante ist eine logische Aussage, die vor dem Betreten �Schleifeninvarianteder Schleife und nach jedem Durchlauf des Schleifenkörpers wahr ist.
Aus einer geeignet gewählten Schleifeninvariante und der Abbruchbedin-gung der Schleife kann i.d.R. die Korrektheit bewiesen werden. Dies wirdim folgenden Satz für Bubblesort beispielhaft gezeigt.
Satz 3.20: Korrektheit
Bubblesort (Algorithmus 3.13) sortiert die Elemente in A aufsteigend.
58 Kapitel 3. Einfache Ansätze
Schlussel-
vergleiche
Schreib-
zugriffe24 15420 28 1531 14395
39 152820 31 545 11424
9 10
9 8
9 6
9 6
9 2
9 2
9 0
9 10
9 16
2 101 3 4 5 6 7 8 9
2820 5
20
24
24
24
24
24
24 31 14 1 15 39 54
5 24 28 14 1 15 31 39 54
5 20 24 14 1 15 28 31 39 54
5 20 14 1 15 28 31 39 54
5 14 1 15 20 28 31 39 54
5 1 14 15 20 28 31 39 54
1 5 14 15 20 28 31 39 54
1 5 14 15 20 28 31 39 54
Bild 3.2: Der Ablauf von Algorithmus 3.13 wird an einem Beispiel demonstriert.Die farbigen Doppelpfeile markieren die Vertauschungsoperationen, dievon links nach rechts durchgeführt werden.
Bild 3.3: Bubblesort (Algorithmus 3.13) wird auf ein Feld mit 80 Elementen angewandt. Die einzelnen Bilderzeigen von links nach rechts das Feld vor dem Sortieren, nach 20, nach 40 und nach 60 Iterationen sowienach dem Sortieren. Die X-Achse entspricht den Feldindizes und die Y-Achse dem gespeicherten Wert.
Beweis 3.21:
Betrachten wir zunächst die For-Schleife in den Zeilen 2–5: Die Invariantelautet »Das größte Element aus A[1], . . . , A[i+1] befindet sich in A[i+1]«.Dies gilt trivialerweise vor Beginn der Schleife für i = 0, da es sich nur umein Element handelt. Für jeden beliebigen Durchlauf durch den Schleifen-körper mit dem Index i gilt nun: Wenn beim Eintritt die Invariante galt, steht
3.3. Backtracking als allgemeine Lösungsstrategie 59
das größte Element aus A[1], . . . , A[i] in A[i]. Dann wird A[i] mit A[i+ 1]verglichen. Ist das Element A[i+1] größer, wird nichts weiter durchgeführtund die Invariante gilt auch nach diesem Schleifendurchlauf. Ist A[i+ 1]kleiner, werden beide Elemente vertauscht und das größere Element stehtjetzt ebenfalls in A[i+1].
Die äußere (Repeat-Until-)Schleife besitzt nun die Invariante »nach demk-ten Durchlauf stehen die k größten Elemente in A[n− k + 1], . . . , A[n]«.Dies gilt wieder trivialerweise für k = 0 vor dem ersten Schleifendurchlauf.Im allgemein k-ten Durchlauf, wissen wir wegen der Invariante aus demvorhergehenden Schleifendurchlauf, dass die k−1 größten Elemente hintenim Feld stehen. Nun gilt mit der Invariante des (n− k)-ten Durchlaufs derinneren Schleife, dass das größte Element der n− k+1 ersten Feldeinträgenach A[n−k] geschoben wurde. Da auf den hinteren Plätzen keine kleinerenElemente folgen können, muss dies auch noch am Ende des Schleifendurch-laufs in Zeile 6 gelten. Es folgt damit die äußere Schleifeninvariante.
Aus der Schleifeninvariante folgt sofort, dass spätestens nach dem (n−1)-ten Durchlauf das Feld sortiert ist. Dann ist die Variable warSortiertwahr und der Algorithmus terminiert.
Die Laufzeit von Sortierverfahren wird häufig mit der Anzahl der Schlüs-selvergleiche angegeben. Aus obigem Beweis der Korrektheit ergeben sichmaximal n Durchläufe durch die äußere Schleife, woraus die LaufzeitO(n2)folgt.
Da gleiche Element sich beim nach rechts Schieben nicht überholen, istBubblesort ein stabiles Sortierverfahren. Allerdings ist es nicht ordnungs-verträglich, weil die Folge 〈2, 3, 4, . . . , n, 1〉 die Inversionszahl n−1 hat, derAlgorithmus aber Laufzeit Θ(n2) benötigt.
Algorithmus 3.13 kann noch verbessert werden, was in Übungsaufga-be 3.2 thematisiert wird.
Die Geschichte von Bubblesort wird in der Arbeit von Astrachan(2003) sehr ausführlich »rekonstruiert«. Die erste bekannte Referenzstammt demnach von Friend (1956).
Das ist zwar nicht unbedingt das Verfahren, nach dem ichselbst etwas sortieren würde, doch für den Computer, dem derÜberblick fehlt, ist dies sehr einfach umzusetzen.
3.3 Backtracking als allgemeine Lösungsstrategie
Für die Graphenprobleme Rundreise, kürzester Weg und maximaler Flussverfallen wir hier zunächst auf den sogenannten Backtracking-Ansatz, der
60 Kapitel 3. Einfache Ansätze
alle möglichen Rundreisen, Wege und Flüsse erzeugt, sodass die beste Al-ternative gewählt werden kann.
Um allgemein einen Backtracking-Algorithmus umsetzen zu können,muss sich ein Lösungskandidat Schritt für Schritt konstruieren lassen. Fallsdurch alle möglichen Entscheidungen die Gesamtheit aller Lösungskandi-daten aufgespannt wird, kann man wie folgt, am Beispiel des Rundreise-problems gezeigt, vorgehen: Ausgehend von einer fest gewählten Startstadttrifft man für den ersten Konstruktionsschritt eine Entscheidung (z.B. dieerste zu besuchende Stadt) und konstruiert rekursiv alle Lösungskandida-ten, die auf diese Entscheidung aufbauen. Danach nimmt man diese Ent-scheidung zurück und versucht es mit einer Alternative. Algorithmus 3.15(Backtracking-TSP) setzt dies für das Handlungsreisendenproblem um.
Dabei wird in der global sichtbaren Variable rundreise eine Rundreiseaufgebaut. Der Aufrufparameter i für die Tiefe in Backtracking-TSP-R be-zeichnet den Index der nächsten zu wählenden Stadt. Daher ist immer (wie
nebenstehend dargestellt) der linke Teil von rundreise bereits gewählt, abdem Index i stehen die noch frei verfügbaren Städte.
Beispiel 3.22:
Im nebenstehenden Graphen soll die kürzeste Rundreise gesucht werden –
v2
v4
v1
v3
v5
4
4
43
4
3
3
6
5
7
Graph für dasRundreiseproblem.
die auch schon farbig gekennzeichnet ist. Dann ergibt sich der in Bild 3.4dargestellte Entscheidungsbaum. Jeder Knoten entspricht einem Funktions-aufrufe von Backtracking-TSP-R und jeder Weg von der Wurzel zu einemBlatt konstruiert eine Rundreise. Der Algorithmus erzeugt die möglichenWege von links nach rechts. Die farbig markierten Längen der Rundreisen
Algorithmus 3.15 Vollständige Aufzählung aller Rundreisenwww
Backtrack.javaBacktracking-TSP(Graph G mit n Knoten)
Rückgabewert: Reihenfolge der Knoten in kurzesteRundreise1 minLange←∞2 for k← 1, . . . , n3 do � rundreise[k]← k�4 Backtracking-TSP-R(n,2)5 return kurzesteRundreise
�
�
initialisiere erste Rundreise�
�suche ab 2. Stadt
Backtracking-TSP-R(Anzahl n,Tiefe i)Rückgabewert: nichts; Seiteneffekt: Änderung in kurzesteRundreise
1 if i ≤ n2 then � for a← i, . . . , n3 do �Vertausche(rundreise, i, a)4 Backtracking-TSP-R(n, i+1)5 Vertausche(rundreise, i, a)��6 else � if (Kosten von rundreise) < minLange7 then �minLange← Kosten von rundreise8 for i← 1, . . . , n9 do � kurzesteRundreise[i]← rundreise[i]���
�
�Rundreise noch nicht komplett?
�
�
probiere alle nochfreien Städte
�
�setze Stadt zurück
�
�
speichere neugefundenekürzeste Reise
3.3. Backtracking als allgemeine Lösungsstrategie 61
Bild 3.4: Entscheidungsbaum von Algorithmus 3.15. Rechts ist jeweils farbig die Anzahl der Funktionsaufrufepro Ebene eingetragen und zu jedem Blatt wird die resultierende Länge der Rundreise unten angezeigt.
entsprechen den von links nach rechts jeweils als aktuell kürzeste bekannteRundreise übernommenen Routen. �
Backtracking ist damit das systematische Durchsuchen allerMöglichkeiten. Das kenne ich auch, wenn mein Freund malwieder etwas »verlegt« hat und das dann irgendwo wieder auf-taucht. Die Suche danach ist in aller Regel sehr aufwendig.
Satz 3.23:
Die Laufzeit von Backtracking-TSP ist in Θ((n−1)!).
Beweis 3.24:
Wir schätzen die Laufzeit über die Anzahl der Aufrufe von Backtracking-TSP-R ab, da der Aufwand jedes Aufrufs (bei geschickter Implementierung)in Θ(1) ist. Damit ergibt sich:
T (n) = 1+n−1∑i=1
((n−1) · · · i) =n−1∑i=1
(n−1)!i!
Im Weiteren schätzen wir T (n) nach oben und nach unten ab. Durch dasgrößte Summenglied gilt nach unten T (n) > (n − 1)! und damit: T (n) ∈Ω((n− 1)!). Für die Abschätzung nach oben, schreiben wir die Summe zu-nächst als
62 Kapitel 3. Einfache Ansätze
T (n) =(n−1)!
1!+
(n−1)!2!
+(n−1)!
3!+ . . .+
(n−1)!(n−1)!
= (n−1)! ·(11+
12!+
13!+ . . .+
1(n−1)!
)
und schätzen jeden Summanden nach oben ab, indem wir nur durch diebeiden jeweils größten Faktoren teilen.
< (n−1)! ·(11+
11 ·2 +
12 ·3 + . . .+
1(n−2) · (n−1)
).
Jeder Term wird dann als Subtraktion formuliert
= (n−1)! ·(11+(11− 1
2
)+(12− 1
3
)+ . . .+
( 1n−2
− 1n−1
))
und durch eine geschickte andere Klammerung fallen die meisten Termeweg (eine sog. Teleskopsumme).
= (n−1)! ·(1+1+
(− 1
2+
12
)︸������︷︷������︸
=0
+(− 1
3+
13
)︸������︷︷������︸
=0
+ . . .− 1n−1
)
< 2 · (n−1)!
Damit gilt für T (n) ∈ O((n−1)!), woraus mit obiger Abschätzung nach un-ten sofort die Aussage folgt (gemäß der Definition von Θ).
Die Laufzeit kann z.T. drastisch verkürzt werden, wenn frühzeitig ineinem Teil des Entscheidungsbaums zu erkennen ist, dass kein Wegzu einem Blatt des Baums zu einer Verbesserung des aktuell bestenbekannten Lösungskandidaten führen kann. Dann werden ganze Teiledes Entscheidungsbaums abgeschnitten und das Verfahren in der Li-teratur entsprechend auch als Branch-and-Bound bezeichnet. FrüheVeröffentlichungen zu Backtracking gibt es von Walker (1960) undGolomb & Baumert (1965). Die Namensgebung »Backtrack« wirddabei immer wieder Derrick H. Lehmer aus Berkley zugesprochen.
3.4 Bedeutung für das Anwendungsszenario
Da es für einen Einsteiger auf dem Gebiet der »Algorithmen und Daten-strukturen« sehr schwierig ist, diese hier vorgestellten Lösungen einzuord-nen und zu bewerten, wollen wir uns hierfür an dieser Stelle die Zeit undden Platz nehmen.
Dabei soll es nicht auf einen exakten Vergleich der verschiedenen Tech-niken untereinander (dynamisches Feld vs. verkettete Liste) ankommen als
3.4. Bedeutung für das Anwendungsszenario 63
auf die Frage, wie sich die Laufzeiten bei zunehmender Problemgröße än-dern. Dabei gehen wir vereinfachend davon aus, dass die Dauer der Ein-zelschritte der Algorithmen jeweils genau 0,01 Millisekunden beträgt. Diebetrachteten Einzelschritte sind:
• Vergleich eines Schlüsselwerts mit einem Element in einer verkettetenListe,• Vergleich und ggf. Vertauschen zweier Elemente in Bubblesort und
und• der lokale Berechnungsaufwand für einen Aufruf von Backtracking-
TSP-R ohne die Zeit der rekursiven Aufrufe.
Ferner rufen wir uns die Anzahl der Filialen in’s Gedächtnis zurück, dieja die betrachtete Problemgröße bestimmt: letztes Jahr 50, heute 120, ineine paar Jahren 10 000. Und zusätzlich schauen wir uns noch 1 Million an.
Dann ergeben sich die geschätzten Laufzeiten in Tabelle 3.3.Beim Mengenproblem sehen wir, dass für kleine Problemgrößen eine
verkettete Liste mit Laufzeiten im Millisekundenbereich völlig ausreichendist. Auch die Laufzeit von einer Sekunde mag noch akzeptabel sein, abererfahrungsgemäß regt sich schon ab einigen wenigen Sekunden der Unmutbeim potentiellen Nutzer einer Software.
Das Sortierproblem ist ebenfalls für kleine Problemgrößen durch Bub-blesort leicht bewältigbar. Durch die quadratische Laufzeit benötigt der Al-gorithmus allerdings für wenig mehr als n = 10 000 Elemente über eineStunde. Dies ist für einen praktischen Einsatz nicht geeignet.
Und beim Rundreiseproblem erweist sich Backtracking-TSP als gänzlichungeeignet: Selbst ein kleines Problem mit n = 50 Städten wäre nicht in derseit dem Urknall verstrichenen Zeit gelöst worden – dies ergibt sich auchbereits aus den Überlegungen in Beispiel 2.9.
Auweia! Dann bin ich ja tatsächlich mit der Lösung meinerProbleme noch gar nicht weiter gekommen!
Tabelle 3.3: Geschätzte Laufzeiten der einfachen Algorithmen.
n = 50 n = 120 n = 104 n = 106
Operation auf der verkettetenListe (Worst-Case)
0,5 ms 1,2 ms 100 ms 10 s
Bubblesort (Worst-Case) 24,5 ms 142,8 ms 16 min 39 s ca. 57 Tage
Rundreiseproblem mit Back-tracking
>1050 Jahre ? ? ?
64 Kapitel 3. Einfache Ansätze
Eine Reihe an eher intuitiven bzw. in ihrer Herangehensweise sehr ein-fach gehaltenen Algorithmen wurde präsentiert und bezüglich ihrer Lauf-zeit analysiert. Besonders sei hier nochmals auf das Prinzip des Back-trackings verwiesen, welches für nahezu alle Probleme geeignet ist – eineAufzählbarkeit der möglichen Lösungen vorausgesetzt. In den weiterenKapiteln werden wir uns bemühen, durch algorithmische Ideen die hiervorgelegten, für große Anwendungen inakzeptablen Laufzeiten zu schla-gen.
Übungsaufgaben
Aufgabe 3.1: Verkettete Listen vereinigen
Beschreiben Sie einen Algorithmus im Pseudo-Code der Vorlesung, derzwei Listen in eine Liste überführt. Welche asymptotische Laufzeit er-gibt sich?
Aufgabe 3.2: Bubblesort anwenden
Sortieren Sie das folgende Feld mit Bubblesort (Algorithmus 3.13) auf-steigend. Dokumentieren Sie alle Teilschritte. Wie viele Schlüsselver-gleiche und Schreibzugriffe auf das Feld werden durchgeführt?
4 19 11 2 5 20 1 15
Aufgabe 3.3: Bubblesort verbessern
Formulieren Sie Bubblesort (Algorithmus 3.13) so um, dass in jederIteration diejenigen Elemente, die sicher an ihrem Platz stehen, nichtmehr verglichen werden.
Wie viele Vergleiche resultieren für das Beispiel aus Aufgabe 3.2.Bestimmen Sie die exakte Anzahl an Vergleichen für n Elemente imWorst-Case, d.h. einer absteigend sortierten Liste, und vergleichen Siediese mit dem ursprünglichen Algorithmus.
Aufgabe 3.4: Dynamische Felder
Betrachten Sie ein dynamisches Feld, das Anfangs mit der Größe 8 an-gelegt wurde und das immer auf die Länge � 3
2 ·alteLange� »vergrößert«wird (d.h. neuen Speicher anlegen und vollständigen Inhalt – einschließ-lich leerer Einträge – kopieren), wenn der Zugriffsindex zu groß ist.
Vollziehen Sie nach, was in den folgenden Algorithmen passiert –wie groß ist jeweils die Laufzeit, d.h. die Anzahl der Speicherzugriffeauf das Feld einschließlich des Umkopierens?
3.4. Bedeutung für das Anwendungsszenario 65
Variante1()Rückgabewert: –
1 A[] = neues dynamisches Feld2 for i← 1, . . . ,203 do � A[i]← i�
Variante2()Rückgabewert: –
1 A[] = neues dynamisches Feld2 for i← 1, . . . ,103 do � A[i∗ i]← i�
Aufgabe 3.5: Programmierung: Liste implementieren
Programmieren Sie eine verkettete Liste mit einer Einfügeoperation undje einer Methode für das rekursive und das iterative Suchen eines Ele-ments. Erzeugen Sie eine Liste mit n Elementen und messen Sie dieLaufzeiten der beiden Suchvarianten. Was beobachten Sie für unter-schiedlich großes n?
Aufgabe 3.6: Stack mit verketteter Liste
Die Datenstruktur Stack bzw. Kellerspeicher ist eine sog. lifo-Schlange: �Stack
Mit der Operation Push können neue Elemente addiert werden, mit derOperation Pop werden Elemente in der umgekehrten Reihenfolge desEinfügens wieder entfernt. Dabei steht lifo für »Last in, first out«. Über-legen Sie, wie Sie den Stack über eine einfach verkettete Liste realisie-ren können, sodass die Operationen konstante Zeit benötigen.
Aufgabe 3.7: Stack mit dynamischem Feld
Realisieren Sie den Stack aus Aufgabe 3.6 mit einem dynamischen Feld.Argumentieren Sie, ob im Durchschnitt ebenfalls konstante Zeit mög-lich ist.
Aufgabe 3.8: Warteschlange mit verketteter Liste
Die Datenstruktur Warteschlange ist eine sog. fifo-Schlange. Mit der �Warteschlange
Operation Enqueue werden neue Elemente in der Warteschlange hinten»angestellt« und mit der Operation Dequeue können Elemente wiederherausgenommen werden – sofern die Warteschlange nicht leer ist. Ausder Bezeichnung fifo (»first in, first out«) folgt, dass die Elemente in ge-nau derselben Reihenfolge entfernt werden, mit der sie eingestellt wur-den. Skizzieren Sie, wie eine Warteschlange über eine einfach verketteteListe realisiert wird. Auch hier sollen die Operationen in konstanter Zeitablaufen.
Aufgabe 3.9: Warteschlange mit dynamischem Feld
Realisieren Sie die Warteschlange aus Aufgabe 3.6 mit einem dynami-schen Feld. Erneut soll die Laufzeit im Durchschnitt konstant sein undder Platzbedarf nur um einen multiplikativen konstanten Faktor vomPlatzbedarf der verketteten Liste abweichen.
66 Kapitel 3. Einfache Ansätze
Aufgabe 3.10: Backtracking für Graphfärbung
Betrachten Sie das folgende Problem der Zweifärbbarkeit eines Gra-phen. Jedem Knoten soll eine der Farben {rot, blau} zugeordnet werden,sodass keine Kante zwei Knoten der gleichen Farbe verbindet. PassenSie den Backtracking-Algorithmus aus der Vorlesung für dieses Pro-blem an, wobei der erste Rekursionsaufruf eine Farbentscheidung fürKnoten 1, der zweite für Knoten 2 etc. trifft. Wenden Sie den Algorith-mus auf den folgenden Graphen an und brechen Sie die Rekursion dannab, wenn eine Färbung gegen obige Regel der Färbbarkeit verstößt odereine gültige Färbung gefunden wurde. Die Reihenfolge, in der die zweiFarben ausprobiert werden, ist dabei immer gleich.
1
6 3 5
7
2
4
Aufgabe 3.11: Entwurf eines rekursiven Algorithmus
Durch einen rekursiven Algorithmus soll eine Liste umgedreht werden,sodass das bisher letzte Element vorn steht etc. Überlegen Sie, wie beimrekursiven Abstieg die Zeiger verändert werden können.
Aufgabe 3.12: Alle Permutationen aufzählen
Als alternative Lösung zum Backtracking gibt es zahlreiche Algorith-men, die alle Permutationen aufzählen. So können ebenfalls z.B. alleRundreisen geprüft werden. Vollziehen Sie folgenden Algorithmus vonHeap (1963) für n = 3 auf dem Startfeld A = 〈1,2,3〉 nach.
Erzeuge-Alle-Permutationen(n)Rückgabewert: –
1 if n = 12 then � drucke: Inhalt von A�3 else � for index← 1, . . . , n4 do �Erzeuge-Alle-Permutationen(n−1)5 if n ist gerade6 then �Vertausche(A, index, n)�7 else �Vertausche(A,1, n)���
