Algorithmen im Überblick (Uni Köln)

Lineare Optimierung

Fourier-Motzkin

Löst Ungleichungssysteme der Form , bzw. oder stellt fest, dass es keine Lösung gibt

Algorithmus

• wir betrachten das allgemeine Ungleichungssystem
• wir fassen wie vorher je 2 Ungleichungen zusammen, in denen unterschiedliche Vorzeichen hat
• durch Elimination erhalten wir ein Ungleichungssystem
• wobei die erste Spalte von A' nur Nullen enthält
• wir wissen lösbar lösbar
• damit haben wir die Lösung von auf die Lösung von reduziert

Fourier-Motzkin-Elimination

1. berechne rekursiv eine Lösung () für das System
2. wenn keine Lösung existiert: stop
3. berechne mittels Rückwärtssubstitution

Dabei sind nur zwei Operationen zulässig:

1. Multiplikation einer Ungleichung mit einer positiven Zahl
2. Addition von zwei Ungleichungen

Bäume und Wege

Blau-Rot-Algorithmus

Bestimmt einen minimal aufspannenden Baum. Es werden zwei Färbungsregeln in beliebiger Reihenfolge auf die Kanten des Graphen angewandt. Die zum Schluss mit Blau markierten Kanten bilden den minimal aufspannenden Baum.

Merke: Blau = Schnitt + günstigste Kante, Rot = Kreis + teuerste Kante, Blau bildet MST

Vorgehen

B - Regel blau - Schnitt:

• wähle einen Schnitt, der keine blaue Kante enthält
• bestimme darin eine kürzeste ungefärbte Kante und färbe sie blau

R - Regel rot - Kreis:

• wähle einen Kreis im Graphen, der keine rote Kante enthält
• bestimme darin eine längste ungefärbte Kante und färbe sie rot

Prim

Greedy-Verfahren; Bestimmt einen MST mit Laufzeit:

Vorgehen:

1. Setze , und wähle einen beliebigen Startknoten s
2. Füge die günstigste, zu s inzidente Kante zu T hinzu
3. Füge die günstigste, zu T adjazente Kante zu T hinzu ohne einen Kreis zu erzeugen
4. Ist kein weiteres Hinzufügen möglich, stellt T einen Baum dar

Hat der Graph mehr als nur eine Zusammenhangskomponente, so muss der Algorithmus für jede Zusammenhangskomponente ausgeführt werden. Die daraus gewonnenen T's bilden einen Wald.

Kruskal

Greedy-Verfahren; Bestimmt einen MST mit Laufzeit:

Ähnlich Prim, jedoch werden die Kantengewichte vorher sortiert und dann den Gewichten aufsteigend zu T hinzugefügt.

Vorgehen:

1. Setze , und sortiere die Kantengewichte
2. Füge die nächstgünstigste Kante zu T hinzu ohne einen Kreis zu erzeugen
3. Ist kein weiteres Hinzufügen möglich, stellt T einen Baum dar

Ford

Bestimmt kürzesten Weg mit Laufzeit ???. Kommt mit negativen Kreisen nicht zurecht.

Alle Kanten so lange optimieren, bis zulässiges Potential erreicht.

Per Hand: Tabelle aufstellen mit dist und pred für jeden Knoten.

Verfahren

Für jeden Knoten werden zwei Werte gespeichert:

• dist: Die Entfernung, bzw. Kosten vom Startknoten
• pred: Der Vorgängerknoten, durch den die Entfernung dist zustandekommt.

Initialisierung: Für alle v: dist(v) = , pred(v) = nil; dist(s) = 0, pred(s) = s
Iteration: Immer wieder alle Kanten durchgehen und dist und pred aktualisieren, falls: dist(v)>dist(u)+c(u,v), also man über den Knoten u günstiger zu v kommt.

Algorithmus

dist (s) = 0, pred (s) = s
for all do
  dist (v) =
  pred (v) = nil
end do
while exists with dist(v) > dist(u) + c(u,v) do
  dist (v) = dist (u) + c(u,v)
  pred (v) = u
end while

Bellman / Ford

Berechnet kürzeste Wege mit Laufzeit O(mn).

Beginnt mit Kantenlänge 1, erhöht diese in jedem Schritt und prüft auf zulässiges Potential. Entdeckt auch negative Kreise. Maximal n=|V| Schritte. Im letzten Schritt wird nur noch geprüft, ob es negative Kreise gibt.

Algorithmus

speichert den bisher kürzesten gefunden Weg der Länge k

for do

end do

Dijkstra

Greedy Algorithmus zur Berechnung eines kürzesten Pfades. Laufzeit: O(n²)

Die Grundidee des Algorithmus ist, ab einem Startknoten die kürzest möglichen Wege weiter zu verfolgen und längere Wege beim Updaten auszuschließen. Er besteht aus diesen Schritten:

1. Weise allen Knoten die beiden Eigenschaften "Distanz" und "Vorgänger" zu. Initialisiere die Distanz im Startknoten mit 0 und in allen anderen Knoten mit ?.
2. Solange es noch unbesuchte Knoten gibt, wähle darunter denjenigen mit minimaler Distanz aus und
   1. Speichere, dass dieser Knoten schon besucht wurde
   2. Berechne für alle noch unbesuchten Nachbarknoten die Summe des jeweiligen Kantengewichtes und der Distanz im aktuellen Knoten
   3. Ist dieser Wert für einen Knoten kleiner als die dort gespeicherte Distanz, aktualisiere sie und setze den aktuellen Knoten als Vorgänger.
      Dieser Schritt wird auch als Update bezeichnet und ist die zentrale Idee von Dijkstra.

In dieser Form berechnet der Algorithmus ausgehend von einem Startknoten die kürzesten Wege zu allen anderen Knoten. Ist man dagegen nur an dem Weg zu einem ganz bestimmten Knoten interessiert, so kann man in Schritt (2) schon abbrechen, wenn der gesuchte Knoten der aktive ist.

Matroide

Eine Menge E und eine eine Familie von Teilmengen bilden ein Matroid (E, F), wenn:

1. 
2. 
3. zu mit |X| < |Y| existiert ein sodass (Augmentierungseingeschaft)

Branchings

Ein Branching ist eine Kantenmenge mit den folgenden Eigenschaften:

• B (ungerichtet aufgefasst) ist ein Wald
• für alle

Eine Arboreszenz ist ein aufspannendes Branching.

Branching Algorithmus

1. kritischen Graphen H mittels Greedy bestimmen
2. ist H azyklisch, stop, denn H ist ein maximales Branching
3. schrumpfe die Kreise von H zum Graphen (G', c')
4. berechne rekursiv ein maximales Branching B' in (G', c')
5. expandiere B' zu einem maximalen Branching B

Laufzeit: O(m*log(n)) oder O(n²) je nach Implementierung

sei umgekehrt B0 ein Branching in G0 mit Gewichten c0
• sei B die Kantenmenge von G, die durch Expandieren entsteht:
• falls B0 eine Kante e0 = (u,w) enthält:
• sei e(e0) = (u, v ) mit v 2 V(C)
• sei (x, v ) 2 V(C) die Kreiskante mit Endknoten v
• sei B = B0 r (u,w) [ (u, v ) [
`

C r (x, v )
´
• andernfalls:
• sei B = B0 [ (C r a)
• dann ist B ein C-optimales Branching in G

Folie 26

Flüsse

Ford / Fulkerson

Gehe alle möglichen Wege von s nach t durch und erhöhe die Kapazität. Wiederhole, bis Kapazität nicht mehr erhöht werden kann.

1. setze f(u,v) := 0 für alle (u,v) A
2. konstruiere
3. falls in kein augmentierender Weg existiert, stop
4. andernfalls sei P ein augmentierender Weg mit Restkapazität
5. für jede Kante (u,v) P:
6. ist (u,v) Vorwärtskante, so setzte f(u,v) := f(u,v) +
7. ist (u,v) Rückwärtskante, so setzte f (v,u) := f (v,u) ?
8. gehe zu (2)

Edmonds / Karp

Genauso wie Ford / Fulkerson, jedoch mit

4. andernfalls sei P ein kürzester (in Anzahl der Kanten) augmentierender Weg

D.h. die einzelnen Wege nicht zufällig ausprobieren, sondern die kürzesten zuerst.

Preflow-Push

Preflow-Push berechnet den maximalen Fluss von s nach t mittels einem Preflow, der während der Berechnung die Flusserhaltung nicht garantiert. Jeder Knoten v bekommt ein Reservoir e(v), welches unbegrenzt ist und die aktuelle Flussbilanz speichert. h(v) hält dagegen die aktuelle Höhe des Knotens fest.

In jedem Schritt ein gültiger Schnitt (Folie 28) vorhanden. Starke Dualitätsbeziehung.

1. Initialisierung
   1. 
   2. 
   3. f(s,v) := c(s,v), e(v) = c(s,v) für alle (s,v) A
2. führe push oder lift aus, solange noch eine Prozedur anwendbar ist.

Beispiel (Sei |V| = 7):

Die push-Operation heißt saturierend, falls anschließend . Dem Algorithmus ist egal, ob es sich um Vorwärts- oder Rückwärtskanten handelt. Wenn freie Kapazität vorhanden, dann wird gepusht. Pushen kann man nur von einem höheren auf einen niedrigeren Knoten.

lift

ein Knoten wird auf die Höhe des Nachbarn zu dem eine Kante mit freier Kapazität existiert h(u) + 1 angehoben.

push

Flusswert aus dem Reservoir wird zu einem Nachbarn gepusht. Vorwärtskante: Fluss+, Rückwärtskante: Fluss-.

Matchings

Tutte-Berge Formel

Die Formel hilft zu überprüfen, ob ein gefundenes Matching ein Maximalmatching darstellt.

Wobei X eine trennende Knotenmenge ist und die Anzahl der Zusammenhangskomponenten von , die eine ungerade Anzahl von Knoten haben.