Algorithmen Flashcards Preview

Operations Research > Algorithmen > Flashcards

Flashcards in Algorithmen Deck (17):
1

Vorgehen Topologische Sortierung

0. Stelle eine Tabelle auf mit allen Knoten und der Anzahl der Vorgänger
1. Wähle einen Knoten mit 0 Vorgängern aus
2. setze diesen knoten auf -1
3. ziehe von allen Nachfolgern 1 ab
4. -> Schritt 1

Reihnfolge in der die -1 erreicht wird ist topologische Sortierung

2

Ziel: Algorithmus von Ford und Fulkerson

maximalen Fluss im Netzwerk

3

Ziel: Cycle-Cancelling Algorithmus

maximalen Fluss mit minimalen Kosten

4

Ziel: Dijkstra - Algorithmus

kürzesten Weg zwischen zwei Punkten, wenn es keine negativen Kantengewichte gibt

5

Ziel: Generischer Label Correcting Algorithmus

kürzesten Weg zwischen zwei Punkten, auch(!) wenn es negative Kantengewichte gibt. Aber anfällig für negative Zykel

6

Kürzeste Wege Problem

- Dijkstra, Cycle-Cancelling (falls negative Kantengewichte)
- Knoten haben generell kein Gewicht, außer als Ausschlusskriterium (Bsw. Kumulierte Kosten -> Budgeteinhaltung)

7

Wahrscheinlichkeiten

Logarithmus im Graph für Additivität

8

Wieso kann der Dijkstra Algorithmus keine negativen Kantengewichte verarbeiten?

permanent markierte Knoten können nicht mehr verändert werden

9

Vorgehen Dijkstra

- Tabelle erstellen mit allen Knoten (zeilen) pred und init (0 für Start unendlich für Rest)
- Knoten vom Start aus "entdecken"
- vom Knoten mit der geringsten Gewichtung weitererkunden
- bereits entdeckte Knoten evtl. korrigieren

10

Vorgehen Label Correcting

- Start auswählen
- alle anderen Knoten auf unendlich setzen
- in einer Phase alle(!) Kanten überprüfen, ob ein Knotenwert nach unten korrigiert werden kann.
- ein Graph mit n Knoten wird in n+1 Phasen abgearbeitet

11

Vorgehen Ford Fulkerson

- Setzte Start- und Zielknoten
- Setzte den Fluss an jeder Kante = 0
- Suche einen augumentierten Pfad und erhöhe bis zum Maximum
- bis kein augumentierter Pfad mehr da ist

12

Vorgehen Cylcle-Canceling- Algorithmus

Voraussetzung: Residualgraph b-Fluss (mit Kosten)
1. Finde negativen Zirkel (Kosten)
2. erhöhe den Zirkel um die engpasskapaziät
3. solange bis man keinen negativen zirkel mehr findet

-> zirkel kann auch mehr als 3 Knoten enthalten

13

Minimalkostenfluss

- Wert des Flusses ist durch Bedarfe und Angebote (b-Werte) vorgegeben. Dieser Fluss soll durch den Cycle Canceling Algorithmus maximiert werden.
- Fluss kann an mehreren Knoten entspringen
- Kosten und Kapazitäten an den Kanten
- b-Werte an den Knoten

14

Maximalfluss

- Fluss nicht vorgegeben, maximaler Fluss wird gesucht
- Fluss entspringt an einer Quelle und geht in eine Senke
- Nur Kapazitäten an den Kanten

15

Maximalflussprobleme

Zuordnungsprobleme, Transportprobleme

16

Kürzeste-Wege-Probleme

Zeitexpansion, Raumprobleme, Überdeckungsprobleme

17

Minimaler-Schnitt-Probleme

(Kosten, Kapazitäten) an den Kanten
an den Knoten b-Werte