Effiziente Algorithmen
Hartmut KlauckUniversität FrankfurtSS 06
Organisatorisches Vorlesungen: Mo. 14-16 c.t., Do 12-14 c.t. Magnus Übung: Mi. 14-16 SR307 Schein: Übung
50% der Übungspunkte Aktive Teilnahme
Zuordnung: T3, ThBI Voraussetzung: Vordiplom
(Informatik, Mathematik) Website:
www.thi.informatik.uni-frankfurt.de/~klauck/EA06.html
Literatur
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest:Introduction to Algorithms(MIT Press)
Deutsch als Algorithmen - Eine Einführung
Bei Oldenbourg
Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms (Cambridge)
Literator
Jon Kleinberg, Eva Tardos: Algorithm Design(Pearson)
Übersicht
Inhalt der Vorlesung: Entwurf effizienter Algorithmen für
interessante Probleme Effizienz:
• Theoretische Effizienz: Polynomialzeit• Praktische Effizienz• Andere Modelle, z.B. Algorithmen mit
konstanter Laufzeit (?) Probleme:
• Aus verschiedenen Bereichen
Übersicht
Probleme: Graphproblem Optimierungsprobleme Geometrische Probleme Online-Probleme
Techniken: Randomisierung Approximation Greedy Algorithmen Divide and Conquer Lineares Programmieren ...
Übersicht
Anordnung der Vorlesung weitgehend nach Problemfeldern
Beginnen mit Graphalgorithmen Durchsuchen von Graphen Kürzeste Wege Spannbäume Matchings Flussalgorithmen
Übersicht
Dabei betrachten wir Entwurftechniken: Greedy Algorithmen Dynamisches Programmieren Randomisierung
Und sondern Datenstrukturprobleme aus, die wir getrennt betrachten Amortisierte Analyse
Übersicht
Später: Andere Problemfelder, z.B.
• Matrixalgorithmen (schnelle Matrixmultiplikation, FFT)
• Lineares Programmieren• Zahlentheoretische Algorithmen (Primzahltests)
Ansätze zur Lösung NP-schwieriger Probleme:• Approximation, lokale Optimierung
Online Algorithmen• Wenn die Eingabe erst im Laufe des Algorithmus
bekannt wird
Graphalgorithmen
Graphen
Ein Graph ist gegeben durch G=(V,E) wobei V die Menge der Knoten ist (|V|=n) Eµ V£V die Menge der Kanten (|E|=m) Es gibt gerichtete und ungerichtete Graphen!
Wie wird ein Graph repräsentiert? Adjazenzmatrix (dichte Graphen) Adjazenzliste (sonst)
Adjazenzmatrix: A[i,j]=1 gdw (i,j)2 E Adjazenzliste: Array der Länge n von Listen, jede
Liste enthält alle Nachbarn des entsprechenden Knoten
Durchsuchen von Graphen Gegeben sei ein gerichteter Graph G Weiterhin ein Startknoten s Ziel ist es, den Graphen zu durchsuchen,
z.B. um einen Zielknoten t zu finden (bzw. zu entscheiden, ob t von s erreichbar)
Zwei Varianten: Breitensuche Tiefensuche
Breitensuche
Idee: besuche zuerst alle Nachbarn, dann iteriere von einem der Nachbarn aus
Tiefensuche
Idee: Besuche einen Nachbarn, iteriere von diesem Nachbarn aus, komme später zurück
Graphsuche
Algemeines Gerüst: Verwende eine Datenstruktur, die
folgende Operationen unterstützt:• Einfügen von Knoten• Entfernen von Knoten
S sei der aktive Knoten Iteriere:
• vom aktiven Knoten besuche alle bisher unbesuchten Nachbarn und füge sie ein
• Entferne einen Knoten und und mache ihn aktiv
Zusätzlich Array: besucht/nicht besucht
Die Datenstruktur
Alternative 1: queue Liste, FIFO (first in first out)
Alternative 2: stack LIFO (last in first out)
Ergebnis
Alternative 1: FIFO Breitensuche Nachbarn werden eingefügt, und
nacheinander abgearbeitet
Alternative 2: LIFO Tiefensuche Nachbarn werden eingefügt, der letzte
Nachbar wird neuer start
Durchsuchen von Graphen Offensichtlich werden mit beiden Methoden
alle erreichbaren Knoten irgendwann besucht
Verschiedene Anwendungen: Breitensuche findet kürzeste Wege in
ungewichteten Graphen Tiefensuche erzeugt eine topologische
Sortierung auf dags (directed acyclic graphs), d.h. eine Nummerierung der Knoten, so dass Kanten nur von niedrigen zu höheren Nummern verlaufen
Topologische Sortierung
Breitensuche und kürzeste Wege Gegeben sei G, sowie ein Startknoten s
und ein Zielknoten t Finde den kürzesten Weg von s nach t (so
einer existiert)! d(u,v) sei Länge des kürzesten Weges von
u nach v
Verwende Breitensuche von s, stoppe wenn t gefunden.
Erzeuge Breitensuchbaum
Breitensuchbaum
Speichere alle Kanten, auf denen neue Knoten besucht werden
Beobachtung: Dies ergibt einen Baum Zu Beginn ist keine Kante gespeichert Wenn eine Kante gespeichert wird, verläuft sie
von einem besuchten zu einem unbesuchten Knoten
Jeder Knoten wird nur einmal besucht, hat also nur einen Vorgänger
Zusätzlich verwalte ein Distanzarray Jeder Knoten erhält eine Distanz d(v) d(s)=0 wenn v von u aus eingefügt wird, setze d(v)=d(u)
+1
Korrektheit der Distanz
Klar: d(s)=0 ist korrekter Distanzwert Angenommen, v wird irgendwann von u aus
besucht, und per Induktion ist d(u) korrekt Zu zeigen: d(v)=d(u)+1 ist korrekt
d(v)=d(u)+1 = korrekte Distanz (s u) +1¸ korrekte Distanz (s v), denn es gibt einen Weg s u v
Noch zu zeigen: d(v) · korrekte Distanz (s v)
Korrektheit
Behauptung: der Breitensuchbaum enthält kürzeste Pfade von s v für alle v
d(v) ist Tiefe von v im Breitensuchbaum, daher korrekte Distanz
Beweis: für s korrekt Sei v ein Knoten auch einer Schicht d des Baumes Per Induktion seien alle Knoten auf Schichten des Baumes,
die näher an s liegen, durch kürzeste Pfade mit s verbunden
Angenommen, es gebe einen kürzeren Weg s v als d(u)+1 für den Vorgänger u von v
Folge diesem Pfad rückwärts, bis ein Knoten w erreicht wird, der im Breitensuchbaum in einer Schicht d‘<d-1 liegt
w ist im Baum korrekt mit s verbunden wu Der Nachfolger von w liegt in Schicht ¸ d, hat aber Distanz ·
d-1, wurde also im Algorithmus NICHT beim Besuch von w eingefügt. Dies ist ein Widerspruch zum Algorithmus.
Laufzeit
Queue und Stackoperationen laufen in konstanter Zeit (uniformes Kostenmass)
Im Algorithmus wird jeder Knoten genau einmal eingefügt und einmal entfernt
Gesamtkosten: O(n+m) Adjazenzliste Bei Adjazenzmatrix: O(n2)
Kürzeste Wege in gewichteten Graphen Gegeben sei ein Graph G als Adjazenzliste mit
Gewichten, d.h. für jede Kante (u,v) sei zusätzlich ein Gewicht W(u,v)¸ 0 gespeichert.
Wir suchen die kürzesten Wege von einem Startknoten s zu allen anderen Knoten
Das Gewicht eines Weges von u nach v sei die Summe der Kantengewichte
Die Distanz von u und v sei das minimale Gewicht eines Weges von u nach v
Minimale Wege müssen nicht die wenigsten Kanten haben!
Beobachtung
Betrachte einen minimalen Weg von s nach v
Alle Teilwege beginnend ab s sind ebenfalls minimal
Idee: Bestimme Wege mit weniger Kanten zuerst Wir benutzen Schätzungen d(v), zu
Anfang d(s)=0 und d(v)=1 sonst Erzeugen im Laufe des Algorithmus
bessere Schätzungen
Speicherung der Wege
Für jeden Knoten v speichern wir einen Vorgänger (v), zu Beginn ist dieser auf NIL gesetzt
Die Vorgänger sollen am Ende einen zur Wurzel s gerichteten Baum minimaler Wege bilden
Relaxierung einer Kante
Grundlegende Operation Relax(u,v,W)
• if d(v)>d(u)+W(u,v)• then d(v):=d(u)+W(u,v); \pi(v):=u
D.h. wenn es einen besseren Weg nach v gibt als bisher erneuere Schätzung für v
Dijkstras Algorithmus
Löst das single-source shortest-path problem
Idee: speichere Knoten so, dass Knoten mit minimaler Distanzschätzung effizient ausgewählt werden können
Wähle einen solchen Knoten, relaxiere alle Kanten zu seinen Nachbarn
Bis alle Knoten ausgewählt Korrektheitsidee: Knoten mit minimaler
Distanzschätzung ist bereits korrekt verbunden
Datenstruktur
Wir brauchen folgende Operationen: ExtractMin: Finde einen Knoten mit
minimalem d(v), entferne ihn DecreaseKey(v,x): Ersetze die
Distanzschätzung von Knoten v durch x (x ist kleiner als bisherige Schätzung
Initialisierung Dieser Operationen reichen aus, um
Dijkstras Algorithmus zu implementieren
Dijkstras Algorithmus
Initialisiere (v)=NIL für alle v undd(s)=0, d(v)=1 sonst
INIT der Datenstruktur S=; Menge der abgearbeiteten Knoten Q=V While Q ;
u=ExtractMin S=S [ u Für alle Nachbarn v von u:
Relax(u,v,W) • Relax benutzt DecreaseKey
Dijkstras Algorithmus
Arbeitsprogramm:
1. Beweise Korrektheit2. Implementiere die Datenstruktur3. Analysiere Laufzeit
Laufzeit
Die Laufzeit wird dominiert durch höchstens n ExtractMin Operationen und höchstens m DecreaseKey Operationen
Zu 2.
Werden später eine Datenstruktur kennenlernen, die folgende Laufzeiten erlaubt: Amortisierte Zeit von ExtractMin ist
O(log n), d.h. Gesamtzeit für n Operationen O(n log n)
Amortisierte Zeit von DecreaseKey ist O(1), d.h. Gesamtzeit für m Operationen O(m)
Dies erlaubt Laufzeit von O(m+n log n)
Simple Implementierung
Speichere d(v) in einem Array DecreaseKey in O(1) ExtractMin in O(n)
Gesamtlaufzeit: O(n2) für ExtractMin und O(m) für DecreaseKey
Praktikabel für Adjazenzmatrizen
Recommended