Post on 05-Apr-2015
transcript
Komplexität von Algorithmen und Problemen
Klaus Becker
2010
2 Komplexität
3 Teil 1
Fallstudie - SortierenPräzisierung von Berechnungskomplexität
4 Das Sortierproblem
5
Das Sortierproblem - formal betrachtet
Gegeben ist eine Liste von Datensätzen [D0, D1, ..., Dn-2, Dn-1].
Die Datensätze sollen über eine Ordnungsrelation < verglichen werden können. Es soll also möglich sein, Vergleiche wie D0 < D1 eindeutig zu entscheiden.
Mit der Ordnungsrelation ≤ erfassen wir die Möglichkeit, dass zwei Datensätze in dem zu vergleichenden Merkmal übereinstimmen können. Es soll D1 ≤ D0 gelten, wenn D0 < D1 nicht gilt.
Gesucht ist eine neue Anordnung der Datensätze
[Dp(0), Dp(1), ..., Dp(n-2), Dp(n-1)]
mit der Eigenschaft, dass
Dp(0) ≤ Dp(1) ≤ ... ≤ Dp(n-2) ≤ Dp(n-1) gilt.
Die neue Anordnung der Datensätze wird hier durch eine bestimmte Anordnung (man sagt auch Permutation) p(0), p(1), ..., p(n-2), p(n-1) der Indexwerte 0, 1, ..., n-2, n-1 beschrieben.
6 Sortieralgorithmen - Selectionsort
Sortieren durch
Auswählen /
Selectionsort
7
# ALGORITHMUS selectionsort(L)
unsortierter Bereich ist die gesamte Liste L
SOLANGE der unsortierte Bereich mehr als ein Element hat:
suche das kleinste Element im unsortierten Bereich
tausche es mit dem ersten Element des unsortierten Bereichs
verkleinere den unsortierten Bereich
# Rückgabe: L
Sortieralgorithmen - Selectionsort
8 Sortieralgorithmen - Quicksort
Sortieren durch
Zerlegen / Quicksort
9
# ALGORITHMUS quicksort(L)
wenn die Liste L mehr als ein Element hat:
# zerlegen
wähle als Pivotelement p das erste Element der Liste aus
erzeuge Teillisten K und G aus der Restliste L ohne p mit
- alle Elemente aus K sind kleiner als das Pivotelement p
- alle Elemente aus G sind nicht kleiner als das Pivotelement p
# Quicksort auf die verkleinerten Listen anwenden
KSortiert = quicksort(K)
GSortiert = quicksort(G)
# zusammensetzen
LSortiert = KSortiert + [p] + GSortiert
# Rückgabe: LSortiert
Sortieralgorithmen - Quicksort
10
# ALGORITHMUS quicksort(L)
wenn die Liste L mehr als ein Element hat:
# zerlegen
wähle als Pivotelement p das erste Element der Liste aus
tausche Elemente innerhalb L so, dass eine Zerlegung L = K + [p] + G entsteht mit
- alle Elemente aus K sind kleiner als Pivotelement p
- alle Elemente aus G sind nicht kleiner als das Pivotelement p
# Quicksort auf die verkleinerten Listen anwenden
quicksort(K)
quicksort(G)
# Rückgabe: L
Sortieralgorithmen - Quicksort
11
Anzahl der Listenelemente: 1000
Rechenzeit: 0.204296356101
Anzahl der Listenelemente: 2000
Rechenzeit: 0.809496178984
Anzahl der Listenelemente: 3000
Rechenzeit: 1.83842583345
Anzahl der Listenelemente: 4000
Rechenzeit: 3.23999810032
Anzahl der Listenelemente: 5000
Rechenzeit: 5.16765678319
Anzahl der Listenelemente: 6000
Rechenzeit: 7.2468548377
Anzahl der Listenelemente: 7000
Rechenzeit: 9.91592506869
Anzahl der Listenelemente: 8000
Rechenzeit: 12.9162480148
Anzahl der Listenelemente: 9000
Rechenzeit: 16.3896752241
...
Laufzeitmessungen - Selectionsort
*2
*2
*2
12
Anzahl der Listenelemente: 1000
Rechenzeit: 0.0178980848125
Anzahl der Listenelemente: 2000
Rechenzeit: 0.0625291761942
Anzahl der Listenelemente: 3000
Rechenzeit: 0.133521718542
Anzahl der Listenelemente: 4000
Rechenzeit: 0.176368784301
Anzahl der Listenelemente: 5000
Rechenzeit: 0.351487409713
Anzahl der Listenelemente: 6000
Rechenzeit: 0.330103965727
Anzahl der Listenelemente: 7000
Rechenzeit: 0.58496680444
Anzahl der Listenelemente: 8000
Rechenzeit: 0.854964248249
Anzahl der Listenelemente: 9000
Rechenzeit: 0.942683218119
...
Laufzeitmessungen - Quicksort
*2
*2
*2
# ALGORITHMUS quicksort(L)
wenn die Liste L mehr als ein Element hat:
# zerlegen
wähle als Pivotelement p das erste Element d. Liste aus
erzeuge Teillisten K und G aus "L ohne p" mit
- alle Elemente aus K sind kleiner als das Pivotelement p
- alle Elemente aus G sind nicht kleiner als p
# Quicksort auf die verkleinerten Listen anwenden
KSortiert = quicksort(K)
GSortiert = quicksort(G)
# zusammensetzen
LSortiert = KSortiert + [p] + GSortiert
# Rückgabe: LSortiert
13
Anzahl der Listenelemente: 1000
Rechenzeit: 0.00662849607981
Anzahl der Listenelemente: 2000
Rechenzeit: 0.0137794049244
Anzahl der Listenelemente: 3000
Rechenzeit: 0.0227299838387
Anzahl der Listenelemente: 4000
Rechenzeit: 0.031230226188
Anzahl der Listenelemente: 5000
Rechenzeit: 0.0419377323096
Anzahl der Listenelemente: 6000
Rechenzeit: 0.0518194351517
Anzahl der Listenelemente: 7000
Rechenzeit: 0.0589655947893
Anzahl der Listenelemente: 8000
Rechenzeit: 0.069147894495
Anzahl der Listenelemente: 9000
Rechenzeit: 0.0784993623491
...
Laufzeitmessungen - Quicksort
*2
*2
*2
# ALGORITHMUS quicksort(L)
wenn die Liste L mehr als ein Element hat:
# zerlegen
wähle als Pivotelement p das erste Element d. Liste aus
tausche Elemente innerhalb L so, dass eine Zerlegung L = K + [p] + G entsteht mit
- alle Elemente aus K sind kleiner als Pivotelement p
- alle Elemente aus G sind nicht kleiner als p
# Quicksort auf die verkleinerten Listen anwenden
quicksort(K)
quicksort(G)
# Rückgabe: L
14
StartStoppRechenzeit: 3.27038296767StartStoppRechenzeit: 3.23336066455StartStoppRechenzeit: 3.25390210208StartStoppRechenzeit: 3.2653359575StartStoppRechenzeit: 3.24174441165StartStoppRechenzeit: 3.25976206473StartStoppRechenzeit: 3.2584529598StartStoppRechenzeit: 3.26073537279StartStoppRechenzeit: 3.23565201723StartStoppRechenzeit: 3.23315561056
Schwierigkeiten bei Laufzeitmessungen
StartStoppRechenzeit: 3.2807468547StartStoppRechenzeit: 3.41092736647StartStoppRechenzeit: 3.4124093984StartStoppRechenzeit: 5.37245627587StartStoppRechenzeit: 6.69305316737StartStoppRechenzeit: 6.70120168904StartStoppRechenzeit: 6.67988976253StartStoppRechenzeit: 6.67656727321StartStoppRechenzeit: 6.70371150523StartStoppRechenzeit: 4.73779544607
Selectionsort - wiederholte
Durchführung einer
Laufzeitmessung
Selectionsort - wiederholte
Durchführung einer
Laufzeitmessung
15
Problematik von Laufzeitmessungen
Laufzeitmessungen werden in der Praxis durchgeführt, um das Laufzeitverhalten eines Programms unter Realbedingungen zu ermitteln.
Aus systematisch durchgeführten Laufzeitmessungen kann man oft Gesetzmäßigkeiten erschließen, wie die Laufzeit von den zu verarbeitenden Daten abhängt.
Bei Laufzeitmessungen muss man aber sehr genau darauf achten, dass sie unter gleichen Bedingungen erfolgen. Ein Wechsel des Rechners führt in der Regel zu anderen Ergebnissen. Auch Änderungen in der Implementierung wirken sich in der Regel auf die Messergebnisse aus. Selbst bei ein und demselben Rechner und derselben Implementierung können sich die Bedingungen ändern, da oft mehrere Prozesse gleichzeitig ablaufen.
Ergebnisse von Laufzeitmessungen sind also kaum auf andere Systeme (andere Rechner, andere Programmiersprachen) übertragbar. Um diese Schwierigkeit zu überwinden, soll im Folgenden ein anderer Weg zur Beschreibung der Berechnungskomplexität beschritten werden.
16 Kostenabschätzung
def selectionsort(L): n = len(L) i = 0 while i < n-2: minpos = i m = i while m < n: if L[m] < L[minpos]: minpos = m m = m+1 h = L[i] L[i] = L[minpos] L[minpos] = h i = i+1 return L
Bei der Ausführung des Algorithmus (bei vorgegebenen Problemgröße) spielt es eine Rolle, wie viele Operationen ausgeführt werden müssen. Operationen sind im vorliegenden Algorithmus u.a. das Ausführen eines Vergleichs und das Ausführen einer Zuweisung. Als Kostenmaß zur Beschreibung des zeitlichen Aufwands könnte man also die Gesamtanzahl der auszuführenden Vergleiche und Zuweisungen wählen. Bei der Festlegung eines Kostenmaßes müssen Annahmen über den Aufwand der
verschiedenen auszuführenden Operationen gemacht werden. Zwei ganz unterschiedliche Wege kann man dabei bestreiten. Ein Weg besteht darin, unterschiedliche Aufwände von Operationen möglichst genau zu erfassen und im Kostenmaß zu berücksichtigen. Ein anderer Weg beschränkt sich darauf, dominante Operationen auszuwählen und die Kosten nur grob zuzuschätzen. Wir werden hier nur den zweiten Weg beschreiten.
17 Kostenmodellierung| 25 17 32 56 25 19 8 66 29 6 20 29 Vergleiche: 11 ^
6 | 17 32 56 25 19 8 66 29 25 20 29 ^
6 8 | 32 56 25 19 17 66 29 25 20 29 ^
6 8 17 | 56 25 19 32 66 29 25 20 29 ^
6 8 17 19 | 25 56 32 66 29 25 20 29 ^
6 8 17 19 20 | 56 32 66 29 25 25 29 ^
6 8 17 19 20 25 | 32 66 29 56 25 29 ^
6 8 17 19 20 25 25 | 66 29 56 32 29 ^
6 8 17 19 20 25 25 29 | 66 56 32 29 ^
6 8 17 19 20 25 25 29 29 | 56 32 66 ^
...
Problemgröße: n Datensätze
Kostenmaß:Anzahl der Vergleiche
Kostenfunktion:n -> (n-1)+(n-2)+...+1
Selectionsort
18 Kostenmodellierung
Genauere Analysen zeigen, dass bei längeren Listen die Verwaltung und die Verarbeitung dieser Listen sehr aufwendig ist und bei der Kostenmodellierung nicht vernachlässigt werden können.
# ALGORITHMUS quicksort(L)
wenn die Liste L mehr als ein Element hat:
# zerlegen
wähle als Pivotelement p das erste Element d. Liste aus
tausche Elemente innerhalb L so, dass eine Zerlegung L = K + [p] + G entsteht mit
- alle Elemente aus K sind kleiner als Pivotelement p
- alle Elemente aus G sind nicht kleiner als p
# Quicksort auf die verkleinerten Listen anwenden
quicksort(K)
quicksort(G)
# Rückgabe: L
# ALGORITHMUS quicksort(L)
wenn die Liste L mehr als ein Element hat:
# zerlegen
wähle als Pivotelement p das erste Element d. Liste aus
erzeuge Teillisten K und G aus "L ohne p" mit
- alle Elemente aus K sind kleiner als das Pivotelement p
- alle Elemente aus G sind nicht kleiner als p
# Quicksort auf die verkleinerten Listen anwenden
KSortiert = quicksort(K)
GSortiert = quicksort(G)
# zusammensetzen
LSortiert = KSortiert + [p] + GSortiert
# Rückgabe: LSortiertProblemgröße: n Datensätze
Kostenmaß:Anzahl der Vergleiche
Problemgröße: n Datensätze
Kostenmaß:???
19 Fachkonzept Kostenfunktion
Die Problemgröße ist eine präzise Beschreibung des Umfangs der zu verarbeitenden Daten, von dem das Zeit- bzw. Speicherverhalten von Lösungalgorithmen maßgeblich beeinflusst wird.
Bei der Beschreibung der Zeitkomplexität mit Hilfe einer Kostenfunktion werden in der Regel eine Reihe von Vereinfachungen vorgenommen sowie Annahmen gemacht. Die Festlegung einer Kostenfunktion kann somit als eine Form der Modellierung angesehen werden, weil hier ein Berechnungsmodell entwickelt werden muss, das den Berechnungsaufwand vereinfachend beschreibt.
Wie bei jeder Modellierung kann das entwickelte Modell mehr oder auch weniger geeignet sein, um die zu beschreibende Wirklichkeit darzustellen. Bei der Modellierung der Zeitkomplexität kommt es darauf an, "richtige" Annahmen über den Aufwand bestimmter, im Algorithmus vorkommender Operationen zu machen. Dass das manchmal schwierig ist, zeigen die Implementierungen des Quicksort-Algorithmus.
Ein Kostenmaß legt fest, in welchem Maße welche Operationen bei der Aufwandsbestimmung berücksichtigt werden. Eine Kostenfunktion ordnet der Problemgröße n die vom Algorithmus benötigten Gesamtkosten T(n) bzgl. des vorgegebenen Kostenmaßes zu.
20 Kostenanalyse 25 17 32 56 25 19 8 66 29 6 20 29 Vergleiche: 11 ^
17 19 8 6 20 | 25 | 32 56 25 66 29 29 Vergleiche: 9 ^ | | ^ | | 8 6 | 17 | 19 20 | | 25 29 29 | 32 | 56 66 Vergleiche: 5 ^ | | ^ | | ^ | | ^ | | | | | | 6 | 8|| ||19 | 20 | ||25 | 29 29 | ||56 | 66 Vergleiche: 1 | || | | | || | ^ | || | | || | | | || ||29 | 29 | || |
Quicksort - günstiger Fall
16 17 32 56 64 70 70 75 76 81 81 81 Vergleiche: 11 ^
||16 | 17 32 56 64 70 70 75 76 81 81 81 Vergleiche: ^|| ||| ||17 | 32 56 64 70 70 75 76 81 81 81 Vergleiche: ...
Quicksort - ungünstiger Fall
Tbest(1) = 0 und Tbest(n+1) ≤ 2*Tbest(n//2) + n
Tworst(n) = (n-1) + (n-2) + ... + 1
21 Kostenanalyse
best case (bester Fall): der Fall, in dem bei der Ausführung des Algorithmus die wenigsten Kosten anfallen
worst case (schlechtester Fall): der Fall, in dem bei der Ausführung des Algorithmus die meisten Kosten anfallen
average case (durchschnittlicher Fall): eine Mittelung der Kosten über alle Fälle
Die Anzahl der Datensatzvergleiche bei der Ausführung eines Sortieralgorithmus hängt manchmal nicht nur von der Problemgröße n (d.h. der Anzahl der Listenelemente) ab, entscheidend ist auch, wie stark die Liste bereits vorsortiert ist.
Selectionsort:
Tbest(n) = (n-1) + (n-2) + ... + 1
Tworst(n) = (n-1) + (n-2) + ... + 1
Taverage(n) = (n-1) + (n-2) + ... + 1
Quicksort:
Tbest(1) = 0 und Tbest(n+1) ≤ 2*Tbest(n//2) + n -> Tbest(n) ≤ n*log2(n)
Tworst(n) = (n-1) + (n-2) + ... + 1
Taverage(n) = n*log2(n)
22 Vergleich von Kostenfunktionen
Algorithmen sind in der Regel so konzipiert, dass sie eine Lösung für beliebige Problemgrößen liefern. Beim Vergleich zugehöriger Kostenfunktionen tritt die Schwierigkeit auf, dass globale Aussagen oft nicht möglich sind. Es kann vorkommen, dass in einem Bereich die eine Kostenfunktion günstiger ist, in einem anderen Bereich die andere Kostenfunktion.
T1(n) = 0.01*n2
T2(n) = 100*n*log10(n)
23 Vergleich von Kostenfunktionen
Oft ist der Problembereich, für den Algorithmen benötigt werden, nicht klar vorgegeben. Man benötigt dann ein Vergleichsverfahren für Kostenfunktionen, das auch mit Situationen wie in der Abbildung klarkommt.
Eine Grundidee des in der Informatik gängigen Vergleichsverfahrens besteht darin, dass kleine Problemgrößen meist von geringerem Interesse sind als große Problemgrößen. Bei kleinen Problemgrößen unterscheiden sich Laufzeiten von Algorithmen z.B. nur im Millisekunden-bereich, während die Unterschiede bei großen Problemgrößen im Sekunden-, Minuten-, Stunden-, Tage- oder gar Jahrebereich liegen können. Verbesserungen von Algorithmen zeigen sich in der Regel insbesondere bei großen Problemgrößen.
Mathematisch präzisiert man diese Idee, indem man das Wachstumsverhalten von Kosten-funktionen vergleicht. Dabei idealisiert man, indem man das Grenzwertverhalten für gegen unendlich strebende Problemgrößen betrachtet.
T1(n) = 0.01*n2
T2(n) = 100*n*log10(n)
T2(n) / T1(n) -> 0
24 Vergleich von Kostenfunktionen
Eine (Kosten-) Funktion f wächst schneller als eine (Kosten-) Funktion g, wenn der Quotient f(n)/g(n) mit wachsendem n gegen unendlich strebt.
Eine (Kosten-) Funktion f wächst langsamer als eine (Kosten-) Funktion g, wenn der Quotient f(n)/g(n) mit wachsendem n gegen 0 strebt.
Eine (Kosten-) Funktion f wächst genauso schnell wie eine (Kosten-) Funktion g, wenn der Quotient f(n)/g(n) mit wachsendem n gegen eine Konstante c strebt.
Selectionsort:
Tselectionsort(n)
= (n-1) + (n-2) + ... + 1
= n*(n-1)/2
= n2/2 - n/2
Tquicksort(n) = n*log2(n)
Beispiele:
Tselectionsort(n) wächst genauso schnell wie T(n) = n2.
Tselectionsort(n) wächst langsamer als Tquicksort(n).
25 Wachstumsprototypen
Prototyp Grundeigenschaft
logarithmisches Wachstum:f(n) = log(n) Wenn n sich verdoppelt, dann wächst f(n) um einen konstanten Betrag.
lineares Wachstum:f(n) = n Wenn n sich verdoppelt, dann verdoppelt sich f(n) ebenfalls.
logarithmisch-lineares Wachstumf(n) = n*log(n)
quadratisches Wachstum:f(n) = n2 Wenn n sich verdoppelt, dann vervierfacht sich f(n).
kubisches Wachstum:f(n) = n3 Wenn n sich verdoppelt, dann verachtfacht sich f(n).
polynomiales Wachstumf(n) = nk Wenn n sich verdoppelt, dann vervielfacht sich f(n) mit 2k.
exponentielles Wachstum:f(n) = bn Wenn n sich um 1 erhöht, dann vervielfacht sich f(n) mit b.
26 Wachstumsprototypen
aus: P. Breuer: Praktische Grenzen der Berechenbarkeit. siehe: http://informatik.bildungrp.de/fileadmin/user_upload/informatik.bildung-rp.de/Weiterbildung/pdf/WB-X-6-PraktischeGrenzen.pdf
27 Wachstumsklassen
Eine (Kosten-) Funktion f wächst nicht schneller als eine (Kosten-) Funktion g, wenn f genauso schnell oder langsamer als g wächst.
Die Klasse aller Funktionen, die nicht schneller wachsen als eine vorgegebene (Kosten-) Funktion f, wird mit O(f) bezeichnet. Man liest das so: "Groß O von f".
Eine genaue Zuordnung zu einem der Wachstumsprototypen geling manchmal nicht. Dennoch ist ein Vergleich mit den Wachstumsprototypen sinnvoll.
Beispiel: T2(n) = n2*(log2n)3
Die Klasse O(n3) umfasst alle (Kosten-) Funktionen, die nicht schneller wachsen als f(n) = n3. Zu dieser Klasse gehören also alle linearen, alle logarithmisch-linearen, alle quadratischen und alle kubischen Funktionen. Zu dieser Klasse gehört aber auch die Funktion T2(n) = n2*(log2n)3.
28 Wachstumsprototypen
aus: P. Breuer: Praktische Grenzen der Berechenbarkeit.
Wir nehmen hier an, dass zur Verarbeitung einer Kosteneinheit eine Millisekunde benötigt wird.
Algorithmen, deren Zeitkomplexität durch eine Kostenfunktion beschrieben wird, die exponentiell oder noch schneller wächst, gelten als praktisch nicht anwendbar.
29 Komplexität von Problemen
Der Algorithmus selectionsort hat - im günstigsten wie auch ungünstigsten Fall - eine quadratische Zeitkomplexität. Die zur Beschreibung des Laufzeitverhalten gewählte Kostenfunktion gehört zur Klasse O(n2) der asymptotisch quadratisch wachsenden Funktionen.
Der Algorithmus quicksort hat - im günstigsten (und auch durchschnittlichen) Fall - eine logischmisch-lineare Zeitkomplexität. Die zur Beschreibung des Laufzeitverhalten gewählte Kostenfunktion gehört hier zur Klasse O(n*log2(n)).
Es gibt eine Vielzahl an weiteren Sortieralgorithmen. Die "schnelleren" dieser Algorithmen haben alle eine logischmisch-lineare Zeitkomplexität. Es stellt sich die Frage, ob es nicht noch schnelleren Sortieralgorithmen gibt - z.B. solche mit einer linearen Zeitkomplexität - und, ob es auch eine Art untere Schranke für die Zeitkomplexität gibt, die von keinem Sortieralgorithmus unterschritten werden kann. Diese Fragen betreffen die Komplexität des Sortierproblems.
Zur Beschreibung der Komplexität eines Problems muss man folglich Aussagen über alle möglichen Algorithmen zur Lösung des Problems machen, indem man zeigt, dass ein bestimmter Ressourcenverbrauch bei all diesen Algorithmen erforderlich ist und von keinem Algorithmus unterschritten werden kann. Die Schwierigkeit beim Nachweis solcher Aussagen besteht darin, dass man den Nachweis über alle denkbaren - d.h. bis jetzt gefundenen und auch noch nicht bekannten - Algorithmen führen muss.
Die (Zeit-)Komplexität eines Problems beschreibt man durch Komplexitätsklassen, die untere Schranken für die Komplexität der Algorithmen, die das Problem lösen, bilden.
30 Problem - Sortieren{abcd,abdc,acbd,acdb,adbc,adcb,bacd,badc,bcad,bcda,bdac,bdca, cabd,cadb,cbad,cbda,cdab,cdba,dabc,dacb,dbac,dbca,dcab,dcba}[a, b, c, d]a < b?T: {abcd,abdc,acbd,acdb,adbc,adcb,cabd,cadb,cdab,dabc,dacb,dcab} [a, b, c, d] a < c? T: {abcd,abdc,acbd,acdb,adbc,adcb,dabc,dacb} [a, b, c, d] a < d? T: {abcd,abdc,acbd,acdb,adbc,adcb} [a, b, c, d] b < c? T: {abcd,abdc,adbc} [a, b, c, d] b < d? T: {abcd,abdc} [a, b, c, d] c < d? T: {abcd} [a, b, c, d] F: {abdc} [a, b, d, c] F: {adbc} [a, d, c, b] c < b? T: {} [a, d, c, b] F: {adbc} [a, d, b, c] F: {acbd,acdb,adcb}
| 25 32 56 27 ^
25 | 32 56 27 ^
25 27 | 56 32 ^
25 27 32 | 56Selectionsort
31 Problem - Sortieren ... F: {dabc,dacb} [d, b, c, a] b < c? T: {dabc} [d, b, c, a] b < a? T: {} c < a? T: {} F: {} F: {dabc} [d, a, c, b] c < b? T: {} F: {dabc} [d, a, b, c] F: {dacb} [d, b, c, a] c < a? T: {} b < a? T: {} F: {} F: {dacb} [d, a, c, b] c < b? T: {dacb} [d, a, c, b] F: {} ...
| 25 32 56 27 ^
25 | 32 56 27 ^
25 27 | 56 32 ^
25 27 32 | 56
Selectionsort
Wenn ein Sortieralgorithmus die Sortierung nur über Vergleiche von Listenelementen erzeugt, dann lässt sich die Ausführung des Algorithmus bei beliebigen Ausgangslisten über einen Entscheidungsbaum darstellen. Die "Tiefe des Baumes" (erkennbar an den Einrückungen) zeigt dabei, wie viele Entscheidungen im ungünstigsten Fall auszuführen sind. Im Fall des Algorithmus selectionsort beträgt die Tiefe des Baumes 6.
Am Entscheidungsbaum zeigt sich also, wie gut oder schlecht ein Algorithmus ist. Wenn die Tiefe des Entscheidungsbaums groß bzw. klein ist, dann ist das worst-case-Verhalten des Algorithmus schlecht bzw. gut.
32
{abcd,abdc,acbd,acdb,adbc,adcb,bacd,badc,bcad,bcda,bdac,bdca, cabd,cadb,cbad,cbda,cdab,cdba,dabc,dacb,dbac,dbca,dcab,dcba}a < b?T: {abcd,abdc,acbd,acdb,adbc,adcb,cabd,cadb,cdab,dabc,dacb,dcab} c < d? T: {abcd,acbd,acdb,cabd,cadb,cdab} a < c? T: {abcd,acbd,acdb} b < c? T: {abcd} F: {acbd,acdb} b < d? T: {acbd} F: {acdb} F: {cabd,cadb,cdab} b < d? T: {cabd} F: {cadb,cdab} a < d? T: {cadb} F: {cdab} F: {abdc,adbc,adcb,dabc,dacb,dcab} a < d? T: {abdc,adbc,adcb} b < d? T: {abdc} F: {adbc,adcb} b < c? T: {abdc} F: {adcb} F: ...
Problem - Sortieren
Am Entscheidungsbaum kann auch aufgezeigt werden, wie gut das worst-case-Verhalten eines Sortieralgorithmus überhaupt sein kann: Bei 24 möglichen Anordnungen benötigt man mindestens einen Entscheidungsbaum der Tiefe 5, um alle Anordnungen durch Entscheidungen erzeugen zu können. Das sieht man so ein: Durch 1 Entscheidung erhält man eine Aufteilung der Anordnungen in 2 Teilmengen, durch 2, 3, 4, 5, ... Entscheidungen in 4, 8, 16, 32, ... Teilmengen. Um alle 24 Anordnungen mittels Entscheidungen auseinander zu bekommen, sind daher mindestens 5 Entscheidungen im Entscheidungsbaum erforderlich. Das Baumdiagramm zeigt, wie man mit 5 geschachtelten Entscheidungen tatsächlich alle Anordnungen erhält.
33 Komplexität des Sortierproblems
Die Betrachtungen oben verdeutlichen, dass es zu jedem vergleichsbasierten Sortieralgorithmus (für jede Listenlänge) einen zugehörigen Entscheidungsbaum gibt. Die Tiefe des Entscheidungsbaum (in Abhängigkeit der Listenlänge) legt das worst-case-Verhalten des Algorithmus fest.
Um eine untere Schranke für das worst-case-Verhalten von Sortieralgorithmen zu gewinnen, schauen wir uns die Tiefe von "optimalen Entscheidungsbäumen" (in Abhängigkeit der Listenlänge) an.
Um k verschiedene Anordnungen nur mit Entscheidungen zu erzeugen, benötigt man einem Entscheidungsbaum mit einer Tiefe der Größenordnung log2(k). Wenn k = 2m eine Zweierpotenz ist, dann reicht die Tiefe m. Ansonsten benötigt man als Tiefe den Exponenten von der von k aus nächst größeren Zweierpotenz.
Wenn beispielsweise k = 24, dann benötigt man eine Tiefe log2(32), also die Tiefe 5.
Um eine Aussage über Listen beliebiger Länge treffen zu können, muss man wissen, wie viele Anordnungen jeweils möglich sind: Bei n Listenelementen gibt es n! = 1*2*...*n verschiedene mögliche Anordnungen der Listenelemente.
Fasst man beide Ergebnisse zusammen, so erhält man folgende Aussage: Um eine Liste mit n Elementen zu sortieren, benötigt man einen Entscheidungsbaum, der eine Tiefe der Größenordnung log2(n!) hat.
34 Komplexität des Sortierproblems
Jeder vergleichsbasierte Sortieralgorithmus hat demnach ein worst-case-Verhalten, das durch die Funktion K(n) = log2(n!) abgeschätzt werden kann.
Mathematiker haben gezeigt, dass n! ≥ (n/2)(n/2) gilt.
Mit dieser Abschätzung erhält man log2(n!) ≥ (n/2)*log2(n/2).
Hieraus ergibt sich, dass jeder vergleichsbasierte Sortieralgorithmus ein worst-case-Verhalten hat, das nach unten durch die Funktion K(n) = (n/2)*log2(n/2) abgeschätzt werden kann. Betrachtet man - wie üblich - nur das asymptotische Verhalten, so zeigt dies, dass das worst-case-Verhalten eines beliebigen Sortieralgorithmus von der Ordnung n*log2(n) sein muss.
Damit ist eine Schranke zur Beschreibung der Komplexität des Sortierproblems gefunden. Die Komplexität des Sortierproblems ist von der Ordnung n*log2(n) - sofern man ein vergleichsbasiertes Berechnungsmodell zu Grunde liegt.
35 Teil 2
Fallstudie - Das AffenpuzzlePraktische Anwendbarkeit von Algorithmen
36 Das Affenpuzzle
37
Algorithmus zur Lösung d. Affenpuzzles
ALGORITHMUS affenpuzzle(n):
erzeuge n*n Karten
erzeuge die Startpermutation der Karten
SOLANGE die letzte Permutation noch nicht erreicht und noch keine Lösung gefunden ist:
erzeuge eine Startorientierung der Karten
SOLANGE die letzte Orientierungen noch nicht erreicht ist:
erzeuge das Kartenfeld zur Permutation und zur Orientierung
überprüfe das Kartenfeld
WENN ok:
Lösung = Kartenfeld
erzeuge die nächste Orientierung
erzeuge die nächste Permutation
Rückgabe: (Karten, Lösung)
Idee:
Man wählt eine bestimmte Kartenreihenfolge aus (eine sog. Permutation der Ausgangskartenreihe). Zudem wählt man eine bestimmte Orientierung der einzelnen Karten (jede Karte kann ja in 4 unterschiedlichen Ausrichtungen hingelegt werden). Wenn man jetzt die zur Permutation und Orientierung gehörende Kartenreihe in das 3x3-Kartenfeld legt (z.B. von links oben nach rechts unten), dann kann man anschließend überprüfen, ob die Kartenübergänge alle stimmen.
38 Aufgabe
Benutze eine Implementierung des Algorithmus "affenpuzzle". Du must nicht alle Details der Implementierung verstehen. Wichtig für die Benutzung ist vor allem die Funktion affenpuzzle(n). Der Parameter n steht hier für die "Größe" des Puzzles. Bei einem 3x3-Puzzle beträgt die Größe n = 3.
(a) Beim Testen ist die Größe n = 2 voreingestellt. Führe die Testanweisungen mehrere Male aus und versuche zu verstehen, wie die Karten im Implementierungsprogramm dargestellt werden. Beachte, dass es vorkommen kann, dass die erzeugten Karten keine Puzzle-Lösung haben.
(b) Stelle beim Testen die Größe n = 3 ein. Wenn du jetzt die Ausführung startest, musst du erst einmal sehr lange warten. Wenn du ungeduldig wirst, dann versuche mit folgender Strategie die Wartezeit abzuschätzen:
Schritt 1: Berechne, wie viele Konfigurationen erzeugt werden. Überlege dir, wie viele Permutationen der Ausgangskartenreihe möglich sind und wie viele Orientierungen jede Permutation zulässt. Zur Kontrolle: 95126814720
Schritt 2: In der Implementierung ist bereits eine Variable zaehler vorgesehen, die die erzeugten Konfigurationen mitzählt. Ergänze im Programm eine Ausgabeanweisung, die bei jeweils 1 Million überprüfter Konfigurationen eine Ausgabe auf dem Bildschirm macht. Stoppe dann die Zeit, die für 1 Million Konfigurationsüberprüfungen benötigt wird.
Schritt 3: Mit den Ergebnissen aus Schritt 1 und Schritt 2 kannst du jetzt eine Hochrechnung machen.
39 Problemgröße / Kostenfunktion
Problemgröße n: Anzahl der Karten, die eine Seite des Kartenfeldes bilden
Kostenfunktion K(n):Problemgröße -> Anzahl der zu betrachtenden Konfigurationen (Permutation + Orientierung)
ALGORITHMUS affenpuzzle(n):
erzeuge n*n Karten
erzeuge die Startpermutation der Karten
SOLANGE die letzte Permutation noch nicht erreicht und noch keine Lösung gefunden ist:
erzeuge eine Startorientierung der Karten
SOLANGE die letzte Orientierungen noch nicht erreicht ist:
erzeuge das Kartenfeld zur Permutation und zur Orientierung
überprüfe das Kartenfeld
WENN ok:
Lösung = Kartenfeld
erzeuge die nächste Orientierung
erzeuge die nächste Permutation
Rückgabe: (Karten, Lösung)
40 Kostenfunktion
Die Herleitung einer Formel für K(n) soll hier für den Fall n = 3 durchgespielt werden.
Im Fall n = 3 gibt es insgesamt 3*3 = 9 Karten.
Wenn man jetzt eine Kartenreihenfolge bildet, dann gibt es 9 Möglichkeiten für die erste Karte, 8 Möglichkeiten für die zweite Karte, 7 Möglichkeiten für die dritte Karte, ... 2 Möglichkeiten für die achte Karte und schließlich 1 Möglichkeit für die neunte Karte.
Ingesamt können bei 9 Karten also 9*8*7*6*5*4*3*2*1 verschiedene Kartenreihenfolgen (Permutationen) gebildet werden. Mathematiker schreiben auch 9! (gelesen: 9 Fakultät) für das Produkt 9*8*7*6*5*4*3*2*1.
Wenn eine bestimmte Kartenreihenfolge vorliegt, dann können alle 9 Karten in jeweils 4 verschiedenen Weisen ausgerichtet werden. Zu jeder Kartenreihenfolge gibt es also 4*4*4*4*4*4*4*4*4 verschiedene Orientierungen der Karten. Mathematiker schreiben für das Produkt 4*4*4*4*4*4*4*4*4 kurz 49.
Wenn man beide Ergebnisse zusammenfasst, dann ergeben sich im Fall n = 3 insgesamt 49*9! bzw. 4(3*3)*(3*3)! verschiedene Kartenkonfigurationen.
Wenn man die Überlegungen verallgeinert, so erhält man die Formel:K(n) = 4(n*n)*(n*n)!
41 Aufgabe
(a) Berechne (z.B. mit einem geeigneten Programm) Funktionswerte der Funktion K(n) = 4(n*n)*(n*n)! für n = 2, 3, 4, 5, 6, ... Was fällt auf?
(b) Schätze ab, wie lange ein Rechner im ungünstigsten Fall zur Überprüfung eines 4x4-Puzzles (5x5-Puzzles) benötigt. Gehe hier zunächst auch davon aus, dass ein Rechner zur Erzeugung und Überprüfung von 1 Million Konfigurationen 1 Sekunde benötigt.
(c) Die Erfahrung lehrt, dass künftige Rechnergenerationen viel schneller sind. Wie wirkt es sich aus, wenn Rechner 1000mal bzw. 1000000mal schneller sind als in der Hochrechnung oben angenommen wurde?
(d) Warum kann man sagen, dass der Algorithmus praktisch nicht anwendbar ist?
(e) Wie könnte man den Algorithmus verbessern?
42 Verbesserte Algorithmen
Der oben gezeigte "naive" Algorithmus zur Bestimmung der Lösung eines Affenpuzzles ist in der Praxis nicht anwendbar. Nur für sehr kleine Problemgrößen erhält man in akzeptabler Zeit ein Ergebnis.
Diese Eigenschaft spiegelt sich im Wachstumsverhalten der Kostenfunktion wider. Die Kostenfunktion K(n) = 4(n*n)*(n*n)! wächst schneller als jede Exponentialfunktion.
Man kann jetzt versuchen, durch Überlegungen die Anzahl der zu überprüfenden Kartenkonfigurationen zu reduzieren (vgl. auch Affenpuzzle_GeroScholz.pdf).
Verbesserte Algorithmen zeigen dann ein durchaus akzeptables Laufzeitverhalten für Problemgrößen bis n = 5. Mit wachsender Problemgröße zeigen sich aber dieselben Schwierigkeiten wie beim naiven Algorithmus: Die Kostenfunktion wächst so schnell, dass eine geringe Erhöhung der Problemgröße das Laufzeitverhalten explodieren lässt.
Algorithmen mit einer exponentiellen oder noch ungünstigeren (Zeit-) Komplexität gelten als praktisch nicht anwendbar, da nur für kleine Problemgrößen akzeptable Laufzeiten - auch bei künftigen Rechnergenerationen - zu erwarten sind.
Ob es Algorithmen zur Lösung des Affenpuzzles gibt, deren (Zeit-) Komplexität günstiger als exponentiell ist, ist nicht bekannt.
43 Teil 3
Fallstudie - PrimfaktorzerlegungPraktische Anwendbarkeit von Algorithmen
44 Primfaktorzerlegung
2 2 5* * 13*
260
Primzahlen sind natürliche Zahlen, die nur durch 1 und sich selbst ohne Rest teilbar sind.
Beispiele: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
Eine der wichtigsten Eigenschaften von Primzahlen ist, dass sie als Bausteine der natürlichen Zahlen angesehen werden können.
Satz: Jede natürliche Zahl lässt sich als Produkt von Primzahlen schreiben. Diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig.
Beispiel: 260 = 2*2*5*13 = 22*5*13
Man nennt die Primzahlen, die in einer Produktdarstellung einer gegebenen Zahl vorkommen, auch Primfaktoren der Zahl.
Das Faktorisierungsproblem besteht darin, eine vorgegebene Zahl in ein Produkt aus Primfaktoren zu zerlegen.
45 Aufgabe
(a) Bei kleineren Zahlen kann man eine Primfaktorzerlegung oft direkt angeben. Bestimme eine Primfaktorzerlegung von n = 48 und n = 100.
(b) Bei größeren Zahlen sollte man systematisch vorgehen, um die Primfaktoren zu bestimmen. Bestimme eine Primfaktorzerlegung von n = 221 und n = 585.
(c) Entwickle zunächst einen Algorithmus zur Primfaktorzerlegung. Beschreibe in einem ersten Schritt in Worten das Verfahren, das du zur Primfaktorzerlegung von Zahlen benutzt. Beschreibe das Verfahren anschließend mit einem Struktogramm. Entwickle dann ein Programm zur Primfaktordarstellung. Hinweis: In Python bietet es sich an, eine Funktion primfaktoren(n) zu erstellen, die die Liste der Primfaktoren zurückgibt.
46
Ein einfaches Faktorisierungsverfahren
Aufgabe:Bestimme mit (einer geeigneten Implementierung) der Funktion primfaktoren(n) die Primfaktorzerlegung der beiden Zahlen 484639526894037745950720 und 565765434324543216797351. Was stellst du fest? Stelle eine Vermutung auf, warum es hier zu einem unterschiedlichen Laufzeitverhalten kommt.
# Übergabe: n = 51
# Initialisierung
faktoren = [] {faktoren -> []}
z = n {z -> 51}
# Probedivisionen
z % 2 -> 1
z % 3 -> 0
# Aktualisierung
p = z {p -> 3}
faktoren = faktoren + [p] {faktoren -> [3]}
z = z // p {z -> 17}
# Probedivisionen
z % 2 -> 1
z % 3 -> 2
z % 4 -> 1
z % 5 -> 2
# Aktualisierung
p = z {p -> 17}
faktoren = faktoren + [p] {faktoren -> [3, 17]}
z = z // p {z -> 1}
# Rückgabe: [3, 17]
ALGORITHMUS primfaktoren(n):
initialisiere die Liste faktoren: faktoren = []
initialisiere die Hilfsvariable z: z = n
SOLANGE z > 1:
bestimme den kleinsten Primfaktor p von z mit Probedivisionen
füge p in die Liste faktoren ein
z = z // p
Rückgabe: faktoren
47 Laufzeitmessungen
Hinweis:Um Gesetzmäßigkeiten herauszufinden, sollte man systematisch vorgehen.
Aufgabe:Führe die Messungen durch. Kannst du anhand der Zahlen erste Zusammenhänge erkennen? Kannst du Prognosen erstellen, wie lange man wohl bis zum nächsten Ergebnis warten muss?
testzahlen = [
11,
101,
1009,
10007,
100003,
1000003,
10000019,
100000007,
1000000007,
10000000019,
100000000003,
1000000000039,
10000000000037,
100000000000031,
1000000000000037,
10000000000000061,
100000000000000003,
1000000000000000003,
10000000000000000051,
100000000000000000039,
...]
from faktorisierung import primfaktoren
from time import *
testzahlen = [...]
for z in testzahlen:
t1 = clock()
ergebnis = primfaktoren(z)
t2 = clock()
t = t2 - t1
print("Zahl: ", z)
print("Primfaktoren:", ergebnis)
print("Rechenzeit: ", t)
print()
48 Zusammenhänge und Prognosen
Gesetzmäßigkeit:Wenn man die Anzahl der Stellen der Ausgangszahl um 2 erhöht, dann erhöht sich die Laufzeit um den Faktor 10. Jede zusätzliche Stelle bei der Ausgangszahl führt also dazu, dass die Laufzeit mit dem Faktor √10 multipliziert wird.
Es handelt sich hier um ein exponentielles Wachstumsverhalten, das man mathematisch mit einer Exponentialfunktion beschreiben kann: Wenn k die Anzahl der Stellen der Ausgangszahl angibt, dann erhält man eine Laufzeit vom Typ L(k) = c*(√10)k mit einer Konstanten c.
Prognose:Wenn die Zahl 100 Stellen haben soll, also 88 Stellen mehr als eine 12-stellige Zahl, so benötigt man nach der gefundenen Gesetzmäßigkeit 1044-mal so lange wie bei der 12-stelligen Zahl - also etwa 1044 Sekunden.
...
Zahl: 1000000000039
Primfaktoren: [1000000000039]
Rechenzeit: 0.906267137304
Zahl: 10000000000037
Primfaktoren: [10000000000037]
Rechenzeit: 2.88270213114
Zahl: 100000000000031
Primfaktoren: [100000000000031]
Rechenzeit: 9.1279123464
Zahl: 1000000000000037
Primfaktoren: [1000000000000037]
Rechenzeit: 28.5701070946
Zahl: 10000000000000061
Primfaktoren: [10000000000000061]
Rechenzeit: 91.2736900919
...
49 Problemgröße / Kostenfunktion
Problemgröße i: Anzahl der Stellen der Ausgangszahl n
Kostenfunktion K(i):Problemgröße -> Anzahl der durchzuführenden Probedivisionen
# Übergabe: n = 51
# Initialisierung
faktoren = [] {faktoren -> []}
z = n {z -> 51}
# Probedivisionen
z % 2 -> 1
z % 3 -> 0
# Aktualisierung
p = z {p -> 3}
faktoren = faktoren + [p] {faktoren -> [3]}
z = z // p {z -> 17}
# Probedivisionen
z % 2 -> 1
z % 3 -> 2
z % 4 -> 1
z % 5 -> 2
# Aktualisierung
p = z {p -> 17}
faktoren = faktoren + [p] {faktoren -> [3, 17]}
z = z // p {z -> 1}
# Rückgabe: [3, 17]
ALGORITHMUS primfaktoren(n):
initialisiere die Liste faktoren: faktoren = []
initialisiere die Hilfsvariable z: z = n
SOLANGE z > 1:
bestimme den kleinsten Primfaktor p von z mit Probedivisionen
füge p in die Liste faktoren ein
z = z // p
Rückgabe: faktoren
50 Kostenanalyse
worst case: n ist eine Primzahl mit i Stellen
Beispiel: n = 983; i = 3
Beachte: 10i-1 < n < 10i
Probedivisionen:
z = n
z % 2 > 0
z % 3 > 0
z % 4 > 0
...
z % 31 > 0
-> z ist Primzahl
Beachte: √983 = 31.35...
Anzahl der Probedivisionen: 31 > √100 = (√10)2
best case: n ist eine Zweierpotenz mit i Stellen
Beispiel: n = 29 = 512; i = 3
Beachte: 10 < 24; n < 10i < 24*i
Probedivisionen:
z = n
z % 2 = 0
p = z; faktoren = faktoren + [p]; z = z//2
z % 2 = 0
p = z; faktoren = faktoren + [p]; z = z//2
...
Anzahl der Probedivisionen: 9 < 4*3
best case (bester Fall): der Fall, in dem bei der Ausführung des Algorithmus die wenigsten Kosten anfallen
worst case (schlechtester Fall): der Fall, in dem bei der Ausführung des Algorithmus die meisten Kosten anfallen
average case (durchschnittlicher Fall): eine Mittelung der Kosten über alle Fälle
K(i) >= √(10i-1) = (√10)i-1
K(i) <= 4*i
51
Asymptotisches Wachstumsverhalten
K(i) >= √(10i-1) = (√10)i-1K(i) <= 4*i
best case (bester Fall): der Fall, in dem bei der Ausführung des Algorithmus die wenigsten Kosten anfallen
worst case (schlechtester Fall): der Fall, in dem bei der Ausführung des Algorithmus die meisten Kosten anfallen
lineares Wachstum
exponentielles Wachstum
Wenn man die Problemgröße um 1 erhöht, dann wachsen die Kosten einen festen Betrag (hier maximal 4).
Wenn man die Problemgröße um 1 erhöht, dann wachsen die Kosten mit dem Faktor √10. Wenn man die Problemgröße um 2 erhöht, dann wachsen die Kosten mit dem Faktor √10*√10, also mit den Faktor 10.
52 Anwendbarkeit des Algorithmus
Angenommen, der Rechenaufwand beträgt bei 10 Stellen 1 Zeiteinheit.
Dann beträgt der Rechenaufwand bei 100 Stellen 1045 Zeiteiheiten.
Wenn sich die Rechnergeschwindigkeit um den Faktor 1000 verbessert, dann beträgt der rechenaufwand immer noch 1042 Zeiteiheiten.
Algorithmen, deren Zeitkomplexität durch eine Kostenfunktion beschrieben wird, die exponentiell oder noch schneller wächst, gelten als praktisch nicht anwendbar.
53
Komplexität d. Faktorisierungsproblems
Bis jetzt sind solche unteren Schranken für das Faktorisierungsproblem nicht gefunden worden. Es wurde auch noch kein Algorithmus entwickelt, der das Faktorisierungsproblem mit mit nicht-exponentieller Zeitkomplexität löst. Alle bisher entwickelten Algorithmen sind demnach - im Fall großer Ausgangszahlen - praktisch nicht anwendbar. Diesen Sachverhalt nutzt bei der Entwicklung kryptologische Verfahren aus (vgl. RSA-Verfahren).
Die Zeitkomplexität eines Problems wird durch eine untere Schranke für Kostenfunktionen von Algorithmen zur Lösung des Problems beschrieben.
54 Aufgabe
Überlege dir Verbesserungen des Probedivisionsalgorithmus. Versuche auch, die Auswirkungen von Verbesserungen auf den Berechnungsaufwand herauszufinden.
55 Teil 4
Fallstudie - Das RundreiseproblemSchwer lösbare Probleme
56 Rundreiseprobleme
Das Königsberger Brückenproblem: Das Ikosaeder-Problem:
Gibt es einen Rundgang durch Königsberg, der jede der sieben Brücken über den Fluss Pregel genau einmal benutzt?
Gibt es eine Rundreise längs der Kanten eines Dodekaeders, so dass alle Ecken des Dodekaeders - außer der Start- und Zielecke - genau einmal besucht werden?
57 Lösung der Rundreiseprobleme
Euler-Problem: Hamilton-Problem:
Eine Rundreise, in der jede Kante (Brücke) genau einmal vorkommt, besucht einen Knoten (Stadtteil) über eine Kante (Brücke) und verlässt ihn über eine andere Kante (Brücke). Hieraus ergibt sich, dass die Anzahl der Kanten (Brücken), die von einem Knoten (Stadtteil) der Rundreise ausgehen, gerade sein muss, damit eine Rundreise der gewünschten Art zustande kommen kann. Diese notwendige Bedingung ist beim Königsberger Brückenproblem aber nicht erfüllt.
Das Rundreiseproblem auf einem Dodekaeder hat eine Reihe von Lösungen.
58
Verallgemeinerte Rundreiseprobleme
Euler-Problem: Hamilton-Problem:
Gesucht ist eine Rundreise durch den Graphen, in der jede Kante genau einmal vorkommt. Eine solche Rundreise wird auch Eulerkreis genannt.
Gegeben ist ein Graph mit seinen Knoten und Kanten. Gesucht ist eine Rundreise durch den Graphen, in der jeder Knoten genau einmal vorkommt - nur Start- und Zielknoten kommen genau zweimal vor. Eine solche Rundreise wird auch Hamiltonkreis genannt.
59 LösungsalgorithmenALGORITHMUS eulerkreis:
Übergabe: Graph, dargestellt m. Nachbarschaftstabelle
kreisExistiert = True
FÜR alle Knoten des Graphen:
bestimme die Anzahl der Nachbarn des Knoten
WENN diese Anzahl ungerade ist:
kreisExistiert = False
Rückgabe: kreisExistiert
60 LösungsalgorithmenALGORITHMUS hamiltonkreis
Übergabe: Graph, dargestellt mit Nachbarschaftslisten
hamiltonkreisGefunden = False
lege einen Startknoten fest
erzeuge eine Ausgangsanordnung der zu besuchenden Knoten
esGibtNochWeitereAnordnungen = True
SOLANGE esGibtNochWeitereAnordnungen und nicht hamiltonkreisGefunden:
WENN die Anordnung einen zulässigen Kreis beschreibt:
hamiltonkreisGefunden = True
erzeuge systematisch eine neue Anordnung der zu besuchenden Knoten
WENN die neue Anordnung gleich der Ausgangsanordnung ist:
esGibtNochWeitereAnordnungen = False
Rückgabe: hamiltonkreisGefunden
61 KostenanalyseALGORITHMUS eulerkreis:
Übergabe: Graph, dargestellt m. Nachbarschaftstabelle
kreisExistiert = True
FÜR alle Knoten des Graphen:
bestimme die Anzahl der Nachbarn des Knoten
WENN diese Anzahl ungerade ist:
kreisExistiert = False
Rückgabe: kreisExistiert
Problemgröße n: Anzahl der Knoten des Graphen
Kostenfunktion K(n):Anzahl der Verarbeitung von Nachbarknoten
Kostenanalyse:Wenn der Graph n Knoten hat, so sind (im ungünstigsten Fall) höchstens n*n Verarbeitungen von Nachbarknoten zu erledigen. Die Kostenfunktion kann demnach durch eine quadratische Funktion abgeschätzt werden. Der Algorithmus hat also eine quadratische Komplexität.
62 LösungsalgorithmenALGORITHMUS hamiltonkreis
Übergabe: Graph, dargestellt mit Nachbarschaftslisten
hamiltonkreisGefunden = False
lege einen Startknoten fest
erzeuge eine Ausgangsanordnung der zu besuchenden Knoten
esGibtNochWeitereAnordnungen = True
SOLANGE esGibtNochWeitereAnordnungen und nicht hamiltonkreisGefunden:
WENN die Anordnung einen zulässigen Kreis beschreibt:
hamiltonkreisGefunden = True
erzeuge systematisch eine neue Anordnung der zu besuchenden Knoten
WENN die neue Anordnung gleich der Ausgangsanordnung ist:
esGibtNochWeitereAnordnungen = False
Rückgabe: hamiltonkreisGefunden
Problemgröße n: Anzahl der Knoten des Graphen
Kostenfunktion K(n):Anzahl der möglichen Knotenanordnungen zur Bildung eines Rundwegs
Kostenanalyse:Wenn der Graph n Knoten hat, so gibt es (n-1)! Knotenanordnungen. Wegen n! >= (n/2)n/2 gilt: Der Algorithmus hat eine eponentielle Komplexität.
63 LösungsalgorithmenALGORITHMUS hamiltonkreis
Übergabe: Graph, dargestellt mit Nachbarschaftslisten
kreisExistiert = False
lege einen startKnoten fest
# erzeuge eine Liste wege, mit der die Anfangsteile möglicher Rundreisewege verwaltet werden
wege = [[startKnoten]]
SOLANGE wege nicht leer ist und nicht kreisExistiert:
aktuellerWeg = erster Weg in wege
entferne akteuellerWeg aus wege
WENN aktuellerWeg alle Knoten des Graphen enthält:
WENN es eine Kante vom letzten Knoten von aktuellerWeg zum startKnoten gibt:
kreisExistiert = True
SONST:
letzterKnoten = letzter Knoten von aktuellerWeg
FÜR alle nachbarKnoten von aktuellerWeg:
WENN nachbarKnoten nicht bereits in aktuellerWeg vorkommt:
erweiterterWeg = aktuellerWeg erweitert um nachbarKnoten
nimm erweiterterWeg in der Liste wege auf
Rückgabe: kreisExistiert
Gibt es bessere Algorithmen zur Lösung des Hamilton-Problems?
64 Aufgabe
Bearbeite Aufgabe 4 auf www.inf-schule.de Seite 1.20.4.3.
65 Die Klasse P
Ergebnisse:
Das Euler-Problem gehört zur Klasse P.
Anders verhält es sich beim Hamilton-Problem. Die hier vorgestellten Lösungsalgorithmen haben eine exponentielle Zeitkomplexität. Alle weiteren Lösungsalgorithmen, die bisher entwickelt worden sind, haben ebenfalls eine exponentielle Zeitkomplexität. Ob es Lösungsalgorithmen für das Hamilton-Problem gibt, die eine polynomiale Zeitkomplexität aufweisen, ist nicht bekannt. Es ist also noch offen, ob das Hamilton-Problem zur Klasse P gehört oder nicht. Man vermutet aufgrund der vielen negativen Ergebnisse, dass es wohl nicht zu P gehört.
P bezeichnet die Klasse der Probleme, die mit einem Algorithmus mit polynomialer Zeitkomplexität gelöst werden können.
66 Nichtdeterministische AlgorithmenALGORITHMUS hamiltonkreis_nichtdeterministisch
Übergabe: Graph, dargestellt mit Nachbarschaftslisten
# erzeuge nichtdeterministisch einen Rundreisekandidaten
lege einen startKnoten fest
weg = [startknoten]
n = Anzahl der Knoten des Graphen
restKnoten = Liste mit allen Knoten außer dem startKnoten
WIEDERHOLE n-1 mal:
naechsterKnoten = restKnoten[0] | restKnoten[1] | ... | restKnoten[n-2]
weg = weg + [naechsterKnoten]
weg = weg + [startKnoten]
# überprüfe den Rundreisekandidaten
hamiltonkreisExistiert = True
FÜR i von 1 BIS n-1:
WENN weg[i] kein Nachbar von weg[i-1] ist oder
weg[i] bereits in [weg[0], ..., weg[i-1]] vorkommt:
hamiltonkreisExistiert = False
WENN weg[n] kein Nachbar von weg[n-1] ist:
hamiltonkreisExistiert = False
Rückgabe: hamiltonkreisExistiert
nichtdeterministisch
polynomiale Zeitkomplexität
67 Die Klasse NP
Ergebnisse:
Das Euler-Problem gehört auch zur Klasse NP, da P eine Teilmenge von NP ist.
Das Hamilton-Problem gehört zur Klasse NP.
NP bezeichnet die Klasse der Probleme, die mit einem nichtdeterministischen Algorithmus mit polynomialer Zeitkomplexität gelöst werden können.
68 Problemreduktion
p: Gibt es einen Hamiltonkreis?
p': Gibt es eine Rundreise mit Gewicht <= 5?
ALGORITHMUS existiertRundreiseHandlungsreisender
Übergabe: gewichteter Graph, Gewichtsschranke
# ...
Rückgabe: True / False
ALGORITHMUS existiertRundreiseHamilton
Übergabe: ungewichteter Graph G
# Umwandlung des Problems
erzeuge aus G den gewichteten Graphen G' (s.o.)
gewichtsschranke = Anzahl der Knoten von G' (bzw. G)
# Lösung des transformierten Problems
ergebnis = existiertRundreiseHandlungsreisender (G', gewichtsschranke)
# Lösung des Ausgangsproblems
Rückgabe: ergebnis
False
False
69 Polynomiale Problemreduktion
p: Gibt es einen Hamiltonkreis?
p': Gibt es eine Rundreise mit Gewicht <= 5?
ALGORITHMUS existiertRundreiseHandlungsreisender
Übergabe: gewichteter Graph, Gewichtsschranke
# ...
Rückgabe: True / False
ALGORITHMUS existiertRundreiseHamilton
Übergabe: ungewichteter Graph G
# Umwandlung des Problems
erzeuge aus G den gewichteten Graphen G' (s.o.)
gewichtsschranke = Anzahl der Knoten von G' (bzw. G)
# Lösung des transformierten Problems
ergebnis = existiertRundreiseHandlungsreisender (G', gewichtsschranke)
# Lösung des Ausgangsproblems
Rückgabe: ergebnis
False
False
Bei einer polynomialen Problemreduktion muss der Aufwand zur Umwandlung des Problems (und zur Umwandlung der Lösung) polynomial sein. Wir schreiben p ≤ p', wenn das Problem p auf das Problem p' polynomial reduzierbar ist.
Hamilton-Problem
≤
Problem des Handlungsreisenden
polynomial
70 Polynomiale Problemreduktion
Wenn p auf das Problem p' polynomial reduzierbar ist und wenn p' eine polynomiale Komplexität hat, dann hat auch das Problem p eine polynomiale Komplexität.
kurz: aus p ≤ p' und p' in P folgt p in P
p: ... p': ...
ALGORITHMUS A' Übergabe: ... ... Rückgabe ...
ALGORITHMUS A Übergabe: ... erzeuge Übergabedaten von A' wende A' auf Die Daten an Rückgabe: ...
polynomialpolynomialpolynomial
Argumentation: Aus einem Algorithmus A' mit polynomialer Komplexität zur Lösung des Problems p' lässt sich ein Algorithmus A mit polynomialer Komplexität zur Lösung des Problems p erzeugen. Man muss nur (wie im Beispiel oben) den Algorithmus A' mit den Umwandlungsalgorithmen kombinieren. Bei der Argumentation benutzt man zudem, dass das Hintereinanderausführen von Algorithmen mit polynomialer Komplexität zu einem Algorithmus mit polynomialer Komplexität führt.
71 NP-vollständige Probleme
Ein Problem p* heißt NP-vollständig genau dann, wenn es in der Komplexitätsklasse NP liegt (d.h. mit einem nichtdeterministischen Algorithmus mit polynomialer Komplexität gelöst werden kann) und wenn jedes Problem p aus NP auf p* polynomial reduzierbar ist.
NP-vollständige Probleme spielen bei der Klärung der Frage P=NP? eine zentrale Rolle. Wenn es gelingt, ein NP-vollständiges Problem p* mit einem Algorithmus mit polynomialer Komplexität zu lösen, dann ist die Aussage P=NP bewiesen. Denn, NP-Vollständigkeit bedeutet ja, dass jedes Problem p aus NP auf p* polynomial reduzierbar ist. Aus einem polynomialen Algorithmus für p* lässt sich dann ein polynomialer Algorithmus für jedes p aus NP erzeugen.
Zur Klärung der Frage P=NP? konzentriert man sich also auf das Lösen NP-vollständiger Probleme.
NPp*
p
p
p
72 P = NP?
Es gibt inzwischen eine Vielzahl von Problemen, die als NP-vollständig nachgewiesen sind. Zu diesen Problemen gehören auch das Hamilton-Problem und das Problem des Handlungsreisenden.
Alle Versuche, ein NP-vollständiges Problem mit einem polynomialen Algorithmus zu lösen, sind bisher fehlgeschlagen. Die NP-vollständigen Probleme erweisen sich also als "harte Nüsse" und gelten als schwer lösbare Probleme.
Aufgrund der vielen fehlgeschlagenen Versuche, einen polynomialen Lösungsalgorithmus für ein NP-vollständiges Problem zu finden, vermutet man, dass die Frage P=NP? negativ zu beantworten ist.
73 Teil 5
Fallstudie - Das RucksackproblemLösen schwieriger Probleme mit Näherungsverfahren
74 Rucksackproblem
Franziska ist die Gewinnerin bei der neuen Fernsehshow "Knapsack". Als Gewinn erhält sie einen Rucksack, in den sie weitere Gegenstände aus einer vorgegebenen Auswahl einpacken kann. Es gibt allerdings einen kleinen Haken. Der Rucksack wird nach dem Einpacken der Gegenstände gewogen. Überschreitet das Gesamtgewicht die maximales Traglast von 15 kg, gibt es keinen Gewinn.
Aufgabe:
Wie soll Franziska den Rucksack packen?
75 Rucksackproblem
Verallgemeinerung:
Gegeben sind n Gegenstände mit ihren Gewichten und Werten. Gegeben ist zusätzlich ein Grenzgewicht, das die maximale Traglast des Rucksacks beschreibt. Gesucht ist eine Kombination von Gegenenständen, so dass das Grenzgewicht nicht überschritten wird und der Gesamtwert der Gegenstände möglichst hoch ist.
Formalisierung:
Gegeben sind n Zahlenpaare (g0, w0), ..., (gn-1, wn-1) (die Gewicht und Wert von n Gegenständen beschreiben). Gegeben ist zusätzlich eine Grenzzahl G (die die maximale Traglast des Rucksacks beschreibt). Alle diese Zahlen sind beliebige (positive) Dezimalzahlen.
Gesucht ist eine 0-1-Folge x0, ..., xn-1 (die die Auswahl der Gegenstände beschreibt: 0 - nicht einpacken; 1 - einpacken), so dass x0*g0 + ... + xn-1*gn-1 <= G gilt und x0*g0 + ... + xn-1*gn-1 maximal ist.
76 Ein Lösungsalgorithmus
Idee:
Eine - wenig elegante - Lösung des Rucksackproblems besteht darin, alle möglichen Kombinationen von Gegenständen zu betrachten und die zugehörigen Gesamtgewichte und Gesamtwerte zu berechnen und aus all den ermittelten Zahlenwerten die gesuchte Kombination zu bestimmen.
ALGORITHMUS optimaleLoesung:
Übergabe:
erzeuge eine erste kombination, z.B. '00000000'
maxKombination = kombination
maxWert = Gesamtwert von kombination
SOLANGE noch nicht alle Kombinationen durchlaufen sind:
erzeuge eine neue kombination
WENN der Gesamtwert von kombination > maxWert und
das Gesamtgewicht von kombination <= grenzgewichtRucksack:
maxKombination = kombination
maxWert = Gesamtwert von kombination
Rückgabe: (maxKombination, maxWert, Gesamtgewicht von maxKombination)
77
Implementierung d. Lösungsalgorithmus
Aufgabe:
Ergänze die fehlenden Teile in der Implementierung.
# Rucksackproblem
gegenstaende = [(3.5, 375), (2.5, 300), (2.0, 100), (3.0, 225), (1.0, 50), (1.75, 125), (0.75, 75), (3.0, 275), (2.5, 150), (2.25, 50)]grenzgewichtRucksack = 15.0
# Funktionen zur Erzeugung einer Lösung
def gesamtGewicht(kombination): # ...
def gesamtWert(kombination): # ...
def erzeugeKombinationAusZahl(zahl): kombination = bin(zahl)[2:] while len(kombination) < len(gegenstaende): kombination = '0' + kombination return kombination
def optimaleLoesung(): # ... return (maxKombination, maxWert, gesamtGewicht(maxKombination))
# Testprint(optimaleLoesung())
78 Komplexitätsbetrachtungen
Komplexität des Algorithmus:
Problemgröße: Anzahl n der Gegenstände festgelegt.
Kostenmaß: Anzahl der zu untersuchenden Kombinationen.
Kostenfunktion: K(n) = 2n
Diese Kostenfunktion ist eine Exponentialfunktion. Der Algorithmus hat demnach eine exponentielle Komplexität und ist (für große n) praktisch nicht anwendbar.
ALGORITHMUS optimaleLoesung:
Übergabe:
erzeuge eine erste kombination, z.B. '00000000'
maxKombination = kombination
maxWert = Gesamtwert von kombination
SOLANGE noch nicht alle Kombinationen durchlaufen sind:
erzeuge eine neue kombination
WENN der Gesamtwert von kombination > maxWert und
das Gesamtgewicht von kombination <= grenzgewichtRucksack:
maxKombination = kombination
maxWert = Gesamtwert von kombination
Rückgabe: (maxKombination, maxWert, Gesamtgewicht von maxKombination)
79 Komplexitätsbetrachtungen
Komplexität des Problems
Ob das Rucksackproblem selbst eine exponentielle Komplexität hat, ist hierdurch noch nicht erwiesen. Es könnte Algorithmen geben, die das Problem viel schneller - z.B. mit polynomialer Komplexität - lösen.
Tatsächlich gibt es einen Algorithmus, der das Rucksackproblem viel effizienter als der oben gezeigte Algorithmus bearbeiten. Er beruht auf der Idee, dass man das Problem, einen Rucksack bei n Gegenständen optimal zu packen, auf das Problem, einen Rucksack bei n-1 Gegenständen optimal zu packen, reduzieren kann.Analysiert man die Komplexität dieses Algorithmen, so erweist sich die oben vorgenommene "naive" Problembeschreibung als inadäquat. Man muss die Größe und Verarbeitung der insgesamt 2n+1 zu verarbeitenden Ausgangszahlen differenzierter betrachten. Insbesondere muss man berücksichtigen, dass sinnvollerweise die Rucksackkapazität mit wachsender Anzahl von Gegenständen auch wachsen sollte. Es erweist sich dann, dass bei diesem Algorithmus trotz großer Verbesserungen dennoch eine exponentielle Komplexität vorliegt.
Alle bis heute entwickelten Algorithmen zur Lösung des Rucksackproblems haben eine exponentielle Komplexität. Es ist kein Algorithmus bekannt, der das Rucksackproblem mit polynomialem Zeitaufwand löst. Vieles spricht dafür, dass das Rucksackproblem nicht zur Klasse der Probleme mit polynomialer Komplexität gehört. Eine endgültige Klärung dieser Komplexitätsfrage ist noch nicht gelungen.
80 Evolution als Lösungsstrategie
"Evolution ist die Veränderung der vererbbaren Merkmale einer Population von Lebewesen von Generation zu Generation. Diese Merkmale sind in Form von Genen kodiert, die bei der Fortpflanzung kopiert und an den Nachwuchs weitergegeben werden. Durch Mutationen entstehen unterschiedliche Varianten (Allele) dieser Gene, die veränderte oder neue Merkmale verursachen können. Diese Varianten sowie Rekombinationen führen zu erblich bedingten Unterschieden (Genetische Variabilität) zwischen Individuen. Evolution findet statt, wenn sich die Häufigkeit dieser Allele in einer Population (die Allelfrequenz) ändert, diese Merkmale in einer Population also seltener oder häufiger werden. Dies geschieht entweder durch Natürliche Selektion (unterschiedliche Überlebens- und Reproduktionsrate aufgrund dieser Merkmale) oder zufällig durch Gendrift."Quelle: Wikipedia
Wie optimiert die Natur die Anpassung von Lebewesen an Umweltbedingungen? Evolution spielt in den Erklärungsmodellen der Biologen eine wesentliche Rolle.
In der Informatik werden Elemente der Evolution übernommen und zu einer Strategie zum näherungsweisen Lösen von Optimierungsproblemen ausgebaut. Wir werden diese Strategie im Folgenden zur Lösung des Rucksackproblems erläutern.
81 Evolution als Lösungsstrategie
Lösungskandidaten sind die Individuen der Population. Eine Population zum Rucksackproblem besteht demnach aus einer Menge von Lösungskandidaten. In der Regel gibt man die Größe der Population (d.h. die Anzahl der Individuen) fest vor.
1110000110
1111000000
1100000111
1011111100
Individuum
Gene
82 Evolution als Lösungsstrategie
Die Fitness von Lösungskandidaten beim Rucksackproblem wird so modelliert, das sie die Qualität der Lösung beschreibt. Die Qualität eines Lösungskandidaten wird durch die Summe der Werte der Gegenstände gegeben. Wenn diese Summe größer als die Kapazitätsgrenze des Rucksacks ist, dann soll die Fitness 0 betragen.
1110000110
1111000000
1100000111
1011111100
Individuum
Gene 10.25
10.75
10.75
0
Fitness
83 Evolution als Lösungsstrategie
Die Fortpflanzung von Individiuen soll durch Kreuzung von zwei Lösungskandidaten realisiert werden. Hierzu wird zunächst eine zufällige Stelle im Gencode bestimmt (z.B. die Stelle 4). Die Genabschnitte der beiden Individuen werden jetzt (über Kreuz) neu kombiniert. Der 1. Abschnitt des ersten Individuums wird mit dem 2. Abschnitt des zweiten Individuums zusammengesetzt, ebenso der 2. Abschnitt des ersten Individuums mit dem 1. Abschnitt des zweiten Individuums.
1110|000110
1111|000000
1111000110
13.25
10.7510.75
X
1110000000
8.25
84 Evolution als Lösungsstrategie
Selektion führt dazu, dass eine Bevorzugung bestimmter Individuen bei der Fortpflanzung durch die Berücksichtigung der Fitness der Individuen stattfinden.
Wir realisieren eine Fortpflanzung mit Selektion wie folgt: Aus der Population sollen zwei Eltern-Individuen ermittelt werden. Für jedes Elternteil werden zwei Kandidaten per Zufall aus der Population ausgewählt. Jetzt kommt die Fitness ins Spiel: Der fitere der beiden Kandidaten kommt zum Zug, der andere hat das Nachsehen. Aus den beiden fiteren Kandidaten werden jetzt durch Kreuzung die beiden Nachkommen erzeugt.
1110|000110
1111|000000
1111000110
13.25
10.75
10.75
1110000000
8.25
Kandidaten für den Vater
Selektion
Kandidaten für die Mutter
Selektion
X
85 Evolution als Lösungsstrategie
Mutation ist eine Veränderung des Gencodes eines Individuums. Sie kann positive, negative oder auch gar keine Auswirkungen auf die Eigenschaften des Individuum haben. Sie kommt spontan oder auch durch äußere Einflüsse zustande.
Ohne Mutation würden die Individuen durch Kreuzung immer nur ihre Anfangs- und Endabschnitte austauschen. Auf diese Weise könnte es vorkommen, dass bestimmte gute Näherungslösungen gar nicht erzeugt werden können. Mutation bringt hier Bewegung ins Spiel. Indem einzelne Gene per Zufall abgeändert werden, können völlig neue Lösungskandidaten erzeugt werden. Das kann sich positiv, aber natürlich auch negativ auf die Qualität der Lösung auswirken.
Wir realisieren Mutation, indem ein Gen per Zufall ausgewählt und abgeändert wird.
Diesen Vorgang führen wir nur ab und zu (mit einer bestimmten Mutationswahrscheinlichkeit) bei einem neu generierten Individuum aus.
Mutation
111000|0|110
10.75
111000|1|110
11.75
86 Genetischer AlgorithmusALGORITHMUS loesungMitGenetischemAlgorithmus
erzeuge eine initiale Population
SOLANGE das Abbruchkriterium nicht erfüllt ist:
lege eine neue Population an
SOLANGE die Populationsgröße nicht erreicht ist:
wähle durch Selektion 2 Individuen aus
erzeuge 2 neue Individuen durch Kreuzung der Individuen
verändere die Gensequenz der neuen Individuen durch Mutation
nimm die neuen Individuen in die neue Population auf
ersetze die alte durch die neue Population
bestimme das Individuum mit maximaler Fitness
Beachte, dass der Algorithmus keinen Bezug auf das Rucksackproblem nimmt. Er kann also auch bei anderen Optimierungsproblemen benutzt werden, sofern geeignete Realisierungen der Gen-Codierung, Selektion, Kreuzung und Mutation gefunden werden.
87 ImplementierungALGORITHMUS loesungMitGenetischemAlgorithmus
erzeuge eine initiale Population
SOLANGE das Abbruchkriterium nicht erfüllt ist:
lege eine neue Population an
SOLANGE die Populationsgröße nicht erreicht ist:
wähle durch Selektion 2 Individuen aus
erzeuge 2 neue Individuen durch Kreuzung der Individuen
verändere die Gensequenz der neuen Individuen durch Mutation
nimm die neuen Individuen in die neue Population auf
ersetze die alte durch die neue Population
bestimme das Individuum mit maximaler Fitness
Aufgabe:
Implementiere den genetischen Algorithmus zum Rucksackproblem (siehe inf-schule 1.20.5.5).