Upload
ruehmkorf
View
420
Download
0
Embed Size (px)
DESCRIPTION
Ein Feedback-Vertex-Set (FVS) eines (gerichteten) Graphen G ist eine Knotenmenge F, durch deren Entfernen G azyklisch wird. Das Feedback-Vertex-Set-Problem besteht aus der Berechnung eines FVSs minimaler Kardinalität. Es modelliert Kernprobleme aus vielen praktischen Bereichen wie z.B. VLSI-Design oder Programmverifikation. Andererseits ist das Problem NP-schwer [Karp72], d.h. im Allgemeinen kann es nicht effizient gelöst werden. Eine Möglichkeit mit diesem Dilemma umzugehen, ist sich mit einer Approximation der Optimallösung zufrieden zu geben. In diesem Vortrag werden auf Markovketten basierende Heuristiken vorgestellt, um solche Approximationen zu bestimmen. Die Pionierarbeit dazu wurde in [Speckenmeyer89] geleistet. Im Mittelpunkt des Vortrags steht eine Verbesserung des ursprünglichen Algorithmus von Speckenmeyer, sowie eine darauf basierende lokale Suchfunktion. Diese beiden Verfahren werden mit bereits bekannten Ansätzen verglichen. Dabei lieferten diese Ansätze signifikant bessere Lösungen als das beste aus der Literatur bekannte Verfahren von Resende. Beispielsweise benötigten sie nur einen Bruchteil der Rechenzeit des Resende-Verfahreens - 733 Sekunden statt 41626 Sekunden auf einem modernen PC - zur Lösung eines Satzes von Benchmark-Graphen. Eine Schlüsselrolle hatten dabei schnelle Methoden zur Lösung dünnbesetzter linearer Gleichungssysteme.
Citation preview
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Auf Markovketten basierende Heuristiken für dasFeedback-Vertex-Set-Problem
Mile Lemaić
Institut für InformatikUniversität zu Köln
20.01.2010
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Gliederung
1 Das FVS-Problem
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Gliederung
1 Das FVS-Problem
2 Markovsche FVS-Algorithmen
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Gliederung
1 Das FVS-Problem
2 Markovsche FVS-Algorithmen
3 Ergebnisse
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Gliederung
1 Das FVS-Problem
2 Markovsche FVS-Algorithmen
3 Ergebnisse
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
NotationInverser Digraph
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
NotationInverser Digraph
G
• Sei G = (V ,A) ein Digraph
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
NotationInverser Digraph
G G−1
• Sei G = (V ,A) ein Digraph• Dann bezeichnet G−1 den inversen Digraph von G
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
DefinitionenFeedback-Vertex-Set
Definition
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
DefinitionenFeedback-Vertex-Set
DefinitionSei G = (V ,A) ein Digraph.
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
DefinitionenFeedback-Vertex-Set
DefinitionSei G = (V ,A) ein Digraph.
• G heißt azyklisch, falls er keine Kreise enthält
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
DefinitionenFeedback-Vertex-Set
DefinitionSei G = (V ,A) ein Digraph.
• G heißt azyklisch, falls er keine Kreise enthält• F ⊂ V ist ein Feedback-Vertex-Set (FVS) von G ,
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
DefinitionenFeedback-Vertex-Set
DefinitionSei G = (V ,A) ein Digraph.
• G heißt azyklisch, falls er keine Kreise enthält• F ⊂ V ist ein Feedback-Vertex-Set (FVS) von G ,
falls G − F ayklisch ist
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
DefinitionenFeedback-Vertex-Set
DefinitionSei G = (V ,A) ein Digraph.
• G heißt azyklisch, falls er keine Kreise enthält• F ⊂ V ist ein Feedback-Vertex-Set (FVS) von G ,
falls G − F ayklisch ist• Ein FVS minimaler Kardinalität heißt optimal
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Das FVS-ProblemÜberblick
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Das FVS-ProblemÜberblick
FVS-Problem
Eingabe: Digraph G = (V ,A)Ausgabe: Optimales FVS F
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Das FVS-ProblemÜberblick
FVS-Problem
Eingabe: Digraph G = (V ,A)Ausgabe: Optimales FVS F
• FVS-Problem ist NP hart [Karp, 1972]
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Das FVS-ProblemÜberblick
FVS-Problem
Eingabe: Digraph G = (V ,A)Ausgabe: Optimales FVS F
• FVS-Problem ist NP hart [Karp, 1972]• Es gibt polynomiell lösbare Klassen
• completely contractible graphs [Levy/Low, 1988]• Smith-Walford reducible graphs [Wang et al, 1985]• . . .
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Das FVS-ProblemÜberblick
FVS-Problem
Eingabe: Digraph G = (V ,A)Ausgabe: Optimales FVS F
• FVS-Problem ist NP hart [Karp, 1972]• Es gibt polynomiell lösbare Klassen
• completely contractible graphs [Levy/Low, 1988]• Smith-Walford reducible graphs [Wang et al, 1985]• . . .
• Bester Approximationsalgorithmus hat Güte vonO(log |V | log log |V |) [Even et al, 1998]
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Eingabe: a, b
Ausgabe: q, r
y := 1q := 0r := a
b := 2by := 2y
r := r-bq := q+y
b := b/2y := y/2
Ja
r > bNein
Ja
r ≥ bNein
Ja
y = 1Nein
• Stelle Programm alsFlowchart dar
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Eingabe: a, b
Ausgabe: q, r
y := 1q := 0r := a
b := 2by := 2y
r := r-bq := q+y
b := b/2y := y/2
Ja
r > bNein
Ja
r ≥ bNein
Ja
y = 1Nein
• Stelle Programm alsFlowchart dar
• Wähle Cutpoints
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Eingabe: a, b
Ausgabe: q, r
y := 1q := 0r := a
b := 2by := 2y
r := r-bq := q+y
b := b/2y := y/2
Ja
r > bNein
Ja
r ≥ bNein
Ja
y = 1Nein
• Stelle Programm alsFlowchart dar
• Wähle Cutpoints
• zerlegen Programmin azyklischeTeilstrukturen
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Eingabe: a, b
Ausgabe: q, r
y := 1q := 0r := a
b := 2by := 2y
r := r-bq := q+y
b := b/2y := y/2
Ja
r > bNein
Ja
r ≥ bNein
Ja
y = 1Nein
• Stelle Programm alsFlowchart dar
• Wähle Cutpoints
• zerlegen Programmin azyklischeTeilstrukturen
• representieren Pro-grammspezifikationen
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Eingabe: a, b
Ausgabe: q, r
y := 1q := 0r := a
b := 2by := 2y
r := r-bq := q+y
b := b/2y := y/2
Ja
r > bNein
Ja
r ≥ bNein
Ja
y = 1Nein
• Stelle Programm alsFlowchart dar
• Wähle Cutpoints
• zerlegen Programmin azyklischeTeilstrukturen
• representieren Pro-grammspezifikationen
• Zeige Kosistenz derSpezifikationen aufTeilstrukturen
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Eingabe: a, b
Ausgabe: q, r
y := 1q := 0r := a
b := 2by := 2y
r := r-bq := q+y
b := b/2y := y/2
Ja
r > bNein
Ja
r ≥ bNein
Ja
y = 1Nein
• Stelle Programm alsFlowchart dar
• Wähle Cutpoints
• zerlegen Programmin azyklischeTeilstrukturen
• representieren Pro-grammspezifikationen
• Zeige Kosistenz derSpezifikationen aufTeilstrukturen
• Zeige Korrektheit desgesamten Programmsmittels induktiverArgumente
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Eingabe: a, b
Ausgabe: q, r
y := 1q := 0r := a
b := 2by := 2y
r := r-bq := q+y
b := b/2y := y/2
Ja
r > bNein
Ja
r ≥ bNein
Ja
y = 1Nein
Dann gilt: Falls das Programmtertminiert, so arbeitet esformal korrekt.
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Eingabe: a, b
Ausgabe: q, r
y := 1q := 0r := a
b := 2by := 2y
r := r-bq := q+y
b := b/2y := y/2
Ja
r > bNein
Ja
r ≥ bNein
Ja
y = 1Nein
Dann gilt: Falls das Programmtertminiert, so arbeitet esformal korrekt.
Spezifikationen:
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Eingabe: a, b
Ausgabe: q, r
y := 1q := 0r := a
b := 2by := 2y
r := r-bq := q+y
b := b/2y := y/2
Ja
r > bNein
Ja
r ≥ bNein
Ja
y = 1Nein
Dann gilt: Falls das Programmtertminiert, so arbeitet esformal korrekt.
Spezifikationen:◦ a ≥ 0 ∧ b > 0
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Eingabe: a, b
Ausgabe: q, r
y := 1q := 0r := a
b := 2by := 2y
r := r-bq := q+y
b := b/2y := y/2
Ja
r > bNein
Ja
r ≥ bNein
Ja
y = 1Nein
Dann gilt: Falls das Programmtertminiert, so arbeitet esformal korrekt.
Spezifikationen:◦ a ≥ 0 ∧ b > 0
◦ a = bq + r ∧ q ≥ 0 ∧ 0 ≤ r < b
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Eingabe: a, b
Ausgabe: q, r
y := 1q := 0r := a
b := 2by := 2y
r := r-bq := q+y
b := b/2y := y/2
Ja
r > bNein
Ja
r ≥ bNein
Ja
y = 1Nein
Dann gilt: Falls das Programmtertminiert, so arbeitet esformal korrekt.
Spezifikationen:◦ a ≥ 0 ∧ b > 0
◦ a = bq + r ∧ q ≥ 0 ∧ 0 ≤ r < b
◦ ay = bq + ry
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Anwendung: Programmverifikation nach FloydBeispiel: Ganzzahlige Division mit Rest
Eingabe: a, b
Ausgabe: q, r
y := 1q := 0r := a
b := 2by := 2y
r := r-bq := q+y
b := b/2y := y/2
Ja
r > bNein
Ja
r ≥ bNein
Ja
y = 1Nein
Dann gilt: Falls das Programmtertminiert, so arbeitet esformal korrekt.
Spezifikationen:◦ a ≥ 0 ∧ b > 0
◦ a = bq + r ∧ q ≥ 0 ∧ 0 ≤ r < b
◦ ay = bq + ry
◦ · · ·
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Das FVS-ProblemHeuristiken für die Knotenwahl
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Das FVS-ProblemHeuristiken für die Knotenwahl
Heuristiken:
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Das FVS-ProblemHeuristiken für die Knotenwahl
Heuristiken:1 [Lee/Reddy, 1990]: Wähle Knoten mit maximalem Produkt
(bzw. Summe) von Eingangs- und Ausgangsgrad
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Das FVS-ProblemHeuristiken für die Knotenwahl
Heuristiken:1 [Lee/Reddy, 1990]: Wähle Knoten mit maximalem Produkt
(bzw. Summe) von Eingangs- und Ausgangsgrad2 [Lin/Jou, 1999]: Wähle Knoten mit maximaler Summe von
Eingangs- und Ausgangsgrad sowie Anzahl von Länge-2-Wegen
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Das FVS-ProblemHeuristiken für die Knotenwahl
Heuristiken:1 [Lee/Reddy, 1990]: Wähle Knoten mit maximalem Produkt
(bzw. Summe) von Eingangs- und Ausgangsgrad2 [Lin/Jou, 1999]: Wähle Knoten mit maximaler Summe von
Eingangs- und Ausgangsgrad sowie Anzahl von Länge-2-Wegen
Problem bei 1 und 2 : Auswahlkriterien sind lokal,aber Kreise sind global
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Gliederung
1 Das FVS-Problem
2 Markovsche FVS-Algorithmen
3 Ergebnisse
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenDefinitionen
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenDefinitionen
• Eine Markovkette
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenDefinitionen
• Eine Markovkette• ist ein Digraph M = (V , A) mit V = {v1, . . . , vn}
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenDefinitionen
35
25
12 7
1 7
47
1
1 P =
⎛⎜⎜⎜⎜⎝
0 35 0 2
5 00 0 1 0 027 0 0 1
747
0 0 0 0 10 1 0 0 0
⎞⎟⎟⎟⎟⎠
• Eine Markovkette• ist ein Digraph M = (V , A) mit V = {v1, . . . , vn}• versehen mit stochastischer Matrix P = (pij ), so dass
pij �= 0 ⇐⇒ (vi , vj ) ∈ A
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenDefinitionen
35
25
12 7
1 7
47
1
1 P =
⎛⎜⎜⎜⎜⎝
0 35 0 2
5 00 0 1 0 027 0 0 1
747
0 0 0 0 10 1 0 0 0
⎞⎟⎟⎟⎟⎠
• Eine Markovkette• ist ein Digraph M = (V , A) mit V = {v1, . . . , vn}• versehen mit stochastischer Matrix P = (pij ), so dass
pij �= 0 ⇐⇒ (vi , vj ) ∈ A• P heißt Übergangsmatrix von M
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenDefinitionen
35
25
12 7
1 7
47
1
1 P =
⎛⎜⎜⎜⎜⎝
0 35 0 2
5 00 0 1 0 027 0 0 1
747
0 0 0 0 10 1 0 0 0
⎞⎟⎟⎟⎟⎠
• Eine Markovkette• ist ein Digraph M = (V , A) mit V = {v1, . . . , vn}• versehen mit stochastischer Matrix P = (pij ), so dass
pij �= 0 ⇐⇒ (vi , vj ) ∈ A• P heißt Übergangsmatrix von M
• Eine Markovkette heißt Random Walk,
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenDefinitionen
12
12
11 3
1 3
13
1
1 P =
⎛⎜⎜⎜⎜⎝
0 12 0 1
2 00 0 1 0 013 0 0 1
313
0 0 0 0 10 1 0 0 0
⎞⎟⎟⎟⎟⎠
• Eine Markovkette• ist ein Digraph M = (V , A) mit V = {v1, . . . , vn}• versehen mit stochastischer Matrix P = (pij ), so dass
pij �= 0 ⇐⇒ (vi , vj ) ∈ A• P heißt Übergangsmatrix von M
• Eine Markovkette heißt Random Walk,falls je zwei positive Zeilenelemente pij , pik von P gleich sind
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenDefinitionen
12
12
11 3
1 3
13
1
1 P =
⎛⎜⎜⎜⎜⎝
0 12 0 1
2 00 0 1 0 013 0 0 1
313
0 0 0 0 10 1 0 0 0
⎞⎟⎟⎟⎟⎠
• Eine Markovkette• ist ein Digraph M = (V , A) mit V = {v1, . . . , vn}• versehen mit stochastischer Matrix P = (pij ), so dass
pij �= 0 ⇐⇒ (vi , vj ) ∈ A• P heißt Übergangsmatrix von M
• Eine Markovkette heißt Random Walk,falls je zwei positive Zeilenelemente pij , pik von P gleich sind
• Jeder Digraph G = (V , A) induziert eindeut. Random Walk MG
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenStationäre Verteilung
M = (V ,A) Markovkette mit V = {v1, . . . , vn} undÜbergangsmatrix P
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenStationäre Verteilung
M = (V ,A) Markovkette mit V = {v1, . . . , vn} undÜbergangsmatrix P
Ist M stark zusammenhängend, so
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenStationäre Verteilung
M = (V ,A) Markovkette mit V = {v1, . . . , vn} undÜbergangsmatrix P
Ist M stark zusammenhängend, so• existiert eindeutiger Spaltenvektor π = (πi ), so dass
tπ · P = tπ undn∑
i=1πi = 1
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenStationäre Verteilung
M = (V ,A) Markovkette mit V = {v1, . . . , vn} undÜbergangsmatrix P
Ist M stark zusammenhängend, so• existiert eindeutiger Spaltenvektor π = (πi ), so dass
tπ · P = tπ undn∑
i=1πi = 1
• π heißt stationäre Verteilung von M
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovkettenStationäre Verteilung
M = (V ,A) Markovkette mit V = {v1, . . . , vn} undÜbergangsmatrix P
Ist M stark zusammenhängend, so• existiert eindeutiger Spaltenvektor π = (πi ), so dass
tπ · P = tπ undn∑
i=1πi = 1
• π heißt stationäre Verteilung von M• 1
πiist mittlere Rückkehrzeit zum Knoten vi
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Speckenmeyers ursprünglicher Algorithmus (MFVS)
Bestimme kleines FVS F von G = (V ,A) mit V = {v1, . . . , vn}
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Speckenmeyers ursprünglicher Algorithmus (MFVS)
Bestimme kleines FVS F von G = (V ,A) mit V = {v1, . . . , vn}
MFVS Algorithmus [Speckenmeyer, 1989]
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Speckenmeyers ursprünglicher Algorithmus (MFVS)
Bestimme kleines FVS F von G = (V ,A) mit V = {v1, . . . , vn}
MFVS Algorithmus [Speckenmeyer, 1989]
• Konstruiere Random Walk MG
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Speckenmeyers ursprünglicher Algorithmus (MFVS)
Bestimme kleines FVS F von G = (V ,A) mit V = {v1, . . . , vn}
MFVS Algorithmus [Speckenmeyer, 1989]
• Konstruiere Random Walk MG• Berechne stationäre Verteilung π = (πi ) von MG
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Speckenmeyers ursprünglicher Algorithmus (MFVS)
Bestimme kleines FVS F von G = (V ,A) mit V = {v1, . . . , vn}
MFVS Algorithmus [Speckenmeyer, 1989]
• Konstruiere Random Walk MG• Berechne stationäre Verteilung π = (πi ) von MG• Wähle Knoten vi mit kleinster mittlerer Rückkehrzeit 1
πi
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Speckenmeyers ursprünglicher Algorithmus (MFVS)
Bestimme kleines FVS F von G = (V ,A) mit V = {v1, . . . , vn}
MFVS Algorithmus [Speckenmeyer, 1989]
• Konstruiere Random Walk MG• Berechne stationäre Verteilung π = (πi ) von MG• Wähle Knoten vi mit kleinster mittlerer Rückkehrzeit 1
πi
Beispiel zu MFVS
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Speckenmeyers ursprünglicher Algorithmus (MFVS)
Bestimme kleines FVS F von G = (V ,A) mit V = {v1, . . . , vn}
MFVS Algorithmus [Speckenmeyer, 1989]
• Konstruiere Random Walk MG• Berechne stationäre Verteilung π = (πi ) von MG• Wähle Knoten vi mit kleinster mittlerer Rückkehrzeit 1
πi
Beispiel zu MFVS
• Berechne stationäre Verteilung
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Speckenmeyers ursprünglicher Algorithmus (MFVS)
Bestimme kleines FVS F von G = (V ,A) mit V = {v1, . . . , vn}
MFVS Algorithmus [Speckenmeyer, 1989]
• Konstruiere Random Walk MG• Berechne stationäre Verteilung π = (πi ) von MG• Wähle Knoten vi mit kleinster mittlerer Rückkehrzeit 1
πi
Beispiel zu MFVS
• Berechne stationäre Verteilung• Wähle Knoten mit
kleinster mittlerer Rückkehrzeit
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Speckenmeyers ursprünglicher Algorithmus (MFVS)
Bestimme kleines FVS F von G = (V ,A) mit V = {v1, . . . , vn}
MFVS Algorithmus [Speckenmeyer, 1989]
• Konstruiere Random Walk MG• Berechne stationäre Verteilung π = (πi ) von MG• Wähle Knoten vi mit kleinster mittlerer Rückkehrzeit 1
πi
Beispiel zu MFVS
• Berechne stationäre Verteilung• Wähle Knoten mit
kleinster mittlerer Rückkehrzeit
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Speckenmeyers ursprünglicher Algorithmus (MFVS)
Bestimme kleines FVS F von G = (V ,A) mit V = {v1, . . . , vn}
MFVS Algorithmus [Speckenmeyer, 1989]
• Konstruiere Random Walk MG• Berechne stationäre Verteilung π = (πi ) von MG• Wähle Knoten vi mit kleinster mittlerer Rückkehrzeit 1
πi
Beispiel zu MFVS
• Berechne stationäre Verteilung• Wähle Knoten mit
kleinster mittlerer Rückkehrzeit• Restgraph vollständig reduzierbar
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Kernidee
Versuche suboptimale Entscheidungen von MFVS zu vermeiden
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Kernidee
Versuche suboptimale Entscheidungen von MFVS zu vermeiden
• Konzipiere alternative unabhängige Heuristik gleicher Güte
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Kernidee
Versuche suboptimale Entscheidungen von MFVS zu vermeiden
• Konzipiere alternative unabhängige Heuristik gleicher Güte• Schlagen beide Heuristiken gleichen Knoten vor, so wähle ihn
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Kernidee
Versuche suboptimale Entscheidungen von MFVS zu vermeiden
• Konzipiere alternative unabhängige Heuristik gleicher Güte• Schlagen beide Heuristiken gleichen Knoten vor, so wähle ihn• Falls nicht, dann . . .
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Kernidee
Versuche suboptimale Entscheidungen von MFVS zu vermeiden
• Konzipiere alternative unabhängige Heuristik gleicher Güte• Schlagen beide Heuristiken gleichen Knoten vor, so wähle ihn• Falls nicht, dann . . .
Beobachtung: F FVS von G ⇐⇒ F FVS von G−1
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Kernidee
Versuche suboptimale Entscheidungen von MFVS zu vermeiden
• Konzipiere alternative unabhängige Heuristik gleicher Güte• Schlagen beide Heuristiken gleichen Knoten vor, so wähle ihn• Falls nicht, dann . . .
Beobachtung: F FVS von G ⇐⇒ F FVS von G−1
Alternative Heuristik: Wende Heuristik von MFVS auf G−1 an
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Tie-Break
Welchen Knoten wählen,wenn beide Heuristiken verschiedene Knoten vorschlagen?
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Tie-Break
Welchen Knoten wählen,wenn beide Heuristiken verschiedene Knoten vorschlagen?
• Berechne stationäre Verteilungen π und π′
der Random Walks MG und MG−1
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Tie-Break
Welchen Knoten wählen,wenn beide Heuristiken verschiedene Knoten vorschlagen?
• Berechne stationäre Verteilungen π und π′
der Random Walks MG und MG−1
• Definiere π̃ = (π̃i) durchπ̃i := h(πi , π
′i ) mit Heuristik h : R
2 → R
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Tie-Break
Welchen Knoten wählen,wenn beide Heuristiken verschiedene Knoten vorschlagen?
• Berechne stationäre Verteilungen π und π′
der Random Walks MG und MG−1
• Definiere π̃ = (π̃i) durchπ̃i := h(πi , π
′i ) mit Heuristik h : R
2 → R
• Wähle Knoten vi mit kleinstem 1eπi
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Tie-Break
Welchen Knoten wählen,wenn beide Heuristiken verschiedene Knoten vorschlagen?
• Berechne stationäre Verteilungen π und π′
der Random Walks MG und MG−1
• Definiere π̃ = (π̃i) durchπ̃i := h(πi , π
′i ) mit Heuristik h : R
2 → R
• Wähle Knoten vi mit kleinstem 1eπi
Wahl v h:
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Tie-Break
Welchen Knoten wählen,wenn beide Heuristiken verschiedene Knoten vorschlagen?
• Berechne stationäre Verteilungen π und π′
der Random Walks MG und MG−1
• Definiere π̃ = (π̃i) durchπ̃i := h(πi , π
′i ) mit Heuristik h : R
2 → R
• Wähle Knoten vi mit kleinstem 1eπi
Wahl v h:• muss symmetrisch sein
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Tie-Break
Welchen Knoten wählen,wenn beide Heuristiken verschiedene Knoten vorschlagen?
• Berechne stationäre Verteilungen π und π′
der Random Walks MG und MG−1
• Definiere π̃ = (π̃i) durchπ̃i := h(πi , π
′i ) mit Heuristik h : R
2 → R
• Wähle Knoten vi mit kleinstem 1eπi
Wahl v h:• muss symmetrisch sein• Kandidaten: arithm. Mittel, geom. Mittel, Maximum, . . .
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Tie-Break
Welchen Knoten wählen,wenn beide Heuristiken verschiedene Knoten vorschlagen?
• Berechne stationäre Verteilungen π und π′
der Random Walks MG und MG−1
• Definiere π̃ = (π̃i) durchπ̃i := h(πi , π
′i ) mit Heuristik h : R
2 → R
• Wähle Knoten vi mit kleinstem 1eπi
Wahl v h:• muss symmetrisch sein• Kandidaten: arithm. Mittel, geom. Mittel, Maximum, . . .• Bestes: arithmetrisches Mittel, d.h. h(x , y) = 1
2(x + y)
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Tie-Break
Welchen Knoten wählen,wenn beide Heuristiken verschiedene Knoten vorschlagen?
• Berechne stationäre Verteilungen π und π′
der Random Walks MG und MG−1
• Definiere π̃ = (π̃i) durchπ̃i := h(πi , π
′i ) mit Heuristik h : R
2 → R
• Wähle Knoten vi mit kleinstem 1eπi
Wahl v h:• muss symmetrisch sein• Kandidaten: arithm. Mittel, geom. Mittel, Maximum, . . .• Bestes: arithmetrisches Mittel, d.h. h(x , y) = 1
2(x + y)
Resultierender Algorithmus: MFVSMean
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Beispiel
Beispiel zu MFVSMean
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Beispiel
Beispiel zu MFVSMean
G
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Beispiel
Beispiel zu MFVSMean
G
• Berechne stat. Verteilung von MG
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Beispiel
Beispiel zu MFVSMean
G
G−1• Berechne stat. Verteilung von MG
• Konstruiere inversen Digraphen G−1
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Beispiel
Beispiel zu MFVSMean
G
G−1• Berechne stat. Verteilung von MG
• Konstruiere inversen Digraphen G−1
• Berechne stat. Verteilung von MG−1
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Beispiel
Beispiel zu MFVSMean
G G
G−1• Berechne stat. Verteilung von MG
• Konstruiere inversen Digraphen G−1
• Berechne stat. Verteilung von MG−1
• Mittele stat. Verteilungen
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Der gemittelte MFVS (MFVSMean)Beispiel
Beispiel zu MFVSMean
G
G−1• Berechne stat. Verteilung von MG
• Konstruiere inversen Digraphen G−1
• Berechne stat. Verteilung von MG−1
• Mittele stat. Verteilungen• Wähle Knoten
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchKernidee
Bestimme kleines FVS F des Digraphen G = (V ,A)
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchKernidee
Bestimme kleines FVS F des Digraphen G = (V ,A)
• Generiere Nachfolger-FVS F ′ eines gegebenen FVSs F
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchKernidee
Bestimme kleines FVS F des Digraphen G = (V ,A)
• Generiere Nachfolger-FVS F ′ eines gegebenen FVSs F• Steuere Generierung durch Schrittweite d
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchKernidee
Bestimme kleines FVS F des Digraphen G = (V ,A)
• Generiere Nachfolger-FVS F ′ eines gegebenen FVSs F• Steuere Generierung durch Schrittweite d• Schrittweite von F nach F ′: |F \ F ′|
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchKernidee
Bestimme kleines FVS F des Digraphen G = (V ,A)
• Generiere Nachfolger-FVS F ′ eines gegebenen FVSs F• Steuere Generierung durch Schrittweite d• Schrittweite von F nach F ′: |F \ F ′|
Konstruktion eines Nachfolger-FVSs F ′ von F
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchKernidee
Bestimme kleines FVS F des Digraphen G = (V ,A)
• Generiere Nachfolger-FVS F ′ eines gegebenen FVSs F• Steuere Generierung durch Schrittweite d• Schrittweite von F nach F ′: |F \ F ′|
Konstruktion eines Nachfolger-FVSs F ′ von F• Eingabe: FVS F von Digraph G
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchKernidee
Bestimme kleines FVS F des Digraphen G = (V ,A)
• Generiere Nachfolger-FVS F ′ eines gegebenen FVSs F• Steuere Generierung durch Schrittweite d• Schrittweite von F nach F ′: |F \ F ′|
Konstruktion eines Nachfolger-FVSs F ′ von F• Eingabe: FVS F von Digraph G• Wähle zufällige d -elementige Menge X ⊂ F
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchKernidee
Bestimme kleines FVS F des Digraphen G = (V ,A)
• Generiere Nachfolger-FVS F ′ eines gegebenen FVSs F• Steuere Generierung durch Schrittweite d• Schrittweite von F nach F ′: |F \ F ′|
Konstruktion eines Nachfolger-FVSs F ′ von F• Eingabe: FVS F von Digraph G• Wähle zufällige d -elementige Menge X ⊂ F• Setze F1 := F \ X
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchKernidee
Bestimme kleines FVS F des Digraphen G = (V ,A)
• Generiere Nachfolger-FVS F ′ eines gegebenen FVSs F• Steuere Generierung durch Schrittweite d• Schrittweite von F nach F ′: |F \ F ′|
Konstruktion eines Nachfolger-FVSs F ′ von F• Eingabe: FVS F von Digraph G• Wähle zufällige d -elementige Menge X ⊂ F• Setze F1 := F \ X• Digraph G ′ := G − F1 ist zyklisch
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchKernidee
Bestimme kleines FVS F des Digraphen G = (V ,A)
• Generiere Nachfolger-FVS F ′ eines gegebenen FVSs F• Steuere Generierung durch Schrittweite d• Schrittweite von F nach F ′: |F \ F ′|
Konstruktion eines Nachfolger-FVSs F ′ von F• Eingabe: FVS F von Digraph G• Wähle zufällige d -elementige Menge X ⊂ F• Setze F1 := F \ X• Digraph G ′ := G − F1 ist zyklisch• Bestimme FVS F2 von G ′ mittels MFVSMean
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchKernidee
Bestimme kleines FVS F des Digraphen G = (V ,A)
• Generiere Nachfolger-FVS F ′ eines gegebenen FVSs F• Steuere Generierung durch Schrittweite d• Schrittweite von F nach F ′: |F \ F ′|
Konstruktion eines Nachfolger-FVSs F ′ von F• Eingabe: FVS F von Digraph G• Wähle zufällige d -elementige Menge X ⊂ F• Setze F1 := F \ X• Digraph G ′ := G − F1 ist zyklisch• Bestimme FVS F2 von G ′ mittels MFVSMean• Ausgabe: F ′ := F1 ∪ F2
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchAlgorithmus
MarkovSearch Algorithmus
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchAlgorithmus
MarkovSearch Algorithmus• Eingabe: Digraph G
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchAlgorithmus
MarkovSearch Algorithmus• Eingabe: Digraph G• Bestimme FVS F0 von G mittels MFVSMean
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchAlgorithmus
MarkovSearch Algorithmus• Eingabe: Digraph G• Bestimme FVS F0 von G mittels MFVSMean
• Füge F0 zu Prioritätswarteschlange Q hinzu
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchAlgorithmus
MarkovSearch Algorithmus• Eingabe: Digraph G• Bestimme FVS F0 von G mittels MFVSMean
• Füge F0 zu Prioritätswarteschlange Q hinzu• Iteriere t mal:
• Extrahiere FVS F kleinster Kardinalität aus Q• Generiere Nachfolger-FVSs F1, . . . , Fk von F (Schrittweite d)• Füge F1, . . . , Fk zu Q hinzu
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchAlgorithmus
MarkovSearch Algorithmus• Eingabe: Digraph G• Bestimme FVS F0 von G mittels MFVSMean
• Füge F0 zu Prioritätswarteschlange Q hinzu• Iteriere t mal:
• Extrahiere FVS F kleinster Kardinalität aus Q• Generiere Nachfolger-FVSs F1, . . . , Fk von F (Schrittweite d)• Füge F1, . . . , Fk zu Q hinzu
• Ausgabe: kleinstes generiertes FVS
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchAlgorithmus
MarkovSearch Algorithmus• Eingabe: Digraph G• Bestimme FVS F0 von G mittels MFVSMean
• Füge F0 zu Prioritätswarteschlange Q hinzu• Iteriere t mal:
• Extrahiere FVS F kleinster Kardinalität aus Q• Generiere Nachfolger-FVSs F1, . . . , Fk von F (Schrittweite d)• Füge F1, . . . , Fk zu Q hinzu
• Ausgabe: kleinstes generiertes FVS
Parameter von MarkovSearch:
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchAlgorithmus
MarkovSearch Algorithmus• Eingabe: Digraph G• Bestimme FVS F0 von G mittels MFVSMean
• Füge F0 zu Prioritätswarteschlange Q hinzu• Iteriere t mal:
• Extrahiere FVS F kleinster Kardinalität aus Q• Generiere Nachfolger-FVSs F1, . . . , Fk von F (Schrittweite d)• Füge F1, . . . , Fk zu Q hinzu
• Ausgabe: kleinstes generiertes FVS
Parameter von MarkovSearch:• Anzahl der Iterationen t
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchAlgorithmus
MarkovSearch Algorithmus• Eingabe: Digraph G• Bestimme FVS F0 von G mittels MFVSMean
• Füge F0 zu Prioritätswarteschlange Q hinzu• Iteriere t mal:
• Extrahiere FVS F kleinster Kardinalität aus Q• Generiere Nachfolger-FVSs F1, . . . , Fk von F (Schrittweite d)• Füge F1, . . . , Fk zu Q hinzu
• Ausgabe: kleinstes generiertes FVS
Parameter von MarkovSearch:• Anzahl der Iterationen t• Anzahl der Nachfolger-FVSs k
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchAlgorithmus
MarkovSearch Algorithmus• Eingabe: Digraph G• Bestimme FVS F0 von G mittels MFVSMean
• Füge F0 zu Prioritätswarteschlange Q hinzu• Iteriere t mal:
• Extrahiere FVS F kleinster Kardinalität aus Q• Generiere Nachfolger-FVSs F1, . . . , Fk von F (Schrittweite d)• Füge F1, . . . , Fk zu Q hinzu
• Ausgabe: kleinstes generiertes FVS
Parameter von MarkovSearch:• Anzahl der Iterationen t• Anzahl der Nachfolger-FVSs k• Schrittweite d
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchOptimale Schrittweite
Was ist die optimale Schrittweite d?
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchOptimale Schrittweite
Was ist die optimale Schrittweite d?
• Eindeutiger optimaler Wert existiert
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchOptimale Schrittweite
Was ist die optimale Schrittweite d?
• Eindeutiger optimaler Wert existiert• Schwer zu quantifizieren
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchOptimale Schrittweite
Was ist die optimale Schrittweite d?
• Eindeutiger optimaler Wert existiert• Schwer zu quantifizieren• Hängt von der Eingabe-Instanz ab
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MarkovSearchVariierende Schrittweite
0 30 60 90 120 150180
181
182
183
184
185
FVS-
Grö
ße
Schrittweite
100 Iterationen500 Iterationen
FVS-Größe in Abhängigkeit vonSchrittweite d für 100 Zufallsdigraphen(p = 0.05) mit 300 Knoten.
0 50 100 150 200 250457
458
459
460
461
462
FVS-
Grö
ßeSchrittweite
100 Iterationen500 Iterationen
FVS-Größe in Abhängigkeit vonSchrittweite d für 100 Zufallsdigraphen(p = 0.2) mit 500 Knoten.
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Markovsche FVS-AlgorithmenImplementierung und Laufzeit
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Markovsche FVS-AlgorithmenImplementierung und Laufzeit
• Jeder Knoten vom FVS F wird von Markov-Heuristik gewählt
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Markovsche FVS-AlgorithmenImplementierung und Laufzeit
• Jeder Knoten vom FVS F wird von Markov-Heuristik gewählt• Dazu muss Eigenvektor π = (πi ) der Übergangsmatrix P
berechnet werden:tπ · P = tπ mit
n∑i=1
πi = 1
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Markovsche FVS-AlgorithmenImplementierung und Laufzeit
• Jeder Knoten vom FVS F wird von Markov-Heuristik gewählt• Dazu muss Eigenvektor π = (πi ) der Übergangsmatrix P
berechnet werden:tπ · P = tπ mit
n∑i=1
πi = 1
Laufzeit mit direkter Methode: O(|V |2.376|F |)
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Markovsche FVS-AlgorithmenImplementierung und Laufzeit
• Jeder Knoten vom FVS F wird von Markov-Heuristik gewählt• Dazu muss Eigenvektor π = (πi ) der Übergangsmatrix P
berechnet werden:tπ · P = tπ mit
n∑i=1
πi = 1
Laufzeit mit direkter Methode: O(|V |2.376|F |)Iterative Methode:
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Markovsche FVS-AlgorithmenImplementierung und Laufzeit
• Jeder Knoten vom FVS F wird von Markov-Heuristik gewählt• Dazu muss Eigenvektor π = (πi ) der Übergangsmatrix P
berechnet werden:tπ · P = tπ mit
n∑i=1
πi = 1
Laufzeit mit direkter Methode: O(|V |2.376|F |)Iterative Methode:
• Ist P irreduzibel und aperiodisch, so gilt:limn→∞ Pn = e tπ, wobei e = t (
1 · · · 1)
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Markovsche FVS-AlgorithmenImplementierung und Laufzeit
• Jeder Knoten vom FVS F wird von Markov-Heuristik gewählt• Dazu muss Eigenvektor π = (πi ) der Übergangsmatrix P
berechnet werden:tπ · P = tπ mit
n∑i=1
πi = 1
Laufzeit mit direkter Methode: O(|V |2.376|F |)Iterative Methode:
• Ist P irreduzibel und aperiodisch, so gilt:limn→∞ Pn = e tπ, wobei e = t (
1 · · · 1)
=⇒ limn→∞ txPn = tπ, für jeden Vektor x mit txe = 1
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Markovsche FVS-AlgorithmenImplementierung und Laufzeit
• Jeder Knoten vom FVS F wird von Markov-Heuristik gewählt• Dazu muss Eigenvektor π = (πi ) der Übergangsmatrix P
berechnet werden:tπ · P = tπ mit
n∑i=1
πi = 1
Laufzeit mit direkter Methode: O(|V |2.376|F |)Iterative Methode:
• Ist P irreduzibel und aperiodisch, so gilt:limn→∞ Pn = e tπ, wobei e = t (
1 · · · 1)
=⇒ limn→∞ txPn = tπ, für jeden Vektor x mit txe = 1• Bekannt: Für n > d
− log |λ| stimmen txPn und tπ auf ersten dStellen überein (λ subdominanter Eigenwert von P)
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Markovsche FVS-AlgorithmenImplementierung und Laufzeit
• Jeder Knoten vom FVS F wird von Markov-Heuristik gewählt• Dazu muss Eigenvektor π = (πi ) der Übergangsmatrix P
berechnet werden:tπ · P = tπ mit
n∑i=1
πi = 1
Laufzeit mit direkter Methode: O(|V |2.376|F |)Iterative Methode:
• Ist P irreduzibel und aperiodisch, so gilt:limn→∞ Pn = e tπ, wobei e = t (
1 · · · 1)
=⇒ limn→∞ txPn = tπ, für jeden Vektor x mit txe = 1• Bekannt: Für n > d
− log |λ| stimmen txPn und tπ auf ersten dStellen überein (λ subdominanter Eigenwert von P)
Laufzeit mit iterativer Methode: O(|A||F | d− ln |λ|)
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Markovsche FVS-AlgorithmenImplementierung und Laufzeit
• Jeder Knoten vom FVS F wird von Markov-Heuristik gewählt• Dazu muss Eigenvektor π = (πi ) der Übergangsmatrix P
berechnet werden:tπ · P = tπ mit
n∑i=1
πi = 1
Laufzeit mit direkter Methode: O(|V |2.376|F |)Iterative Methode:
• Rechengenauigkeit üblicherweise beschränkt
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Markovsche FVS-AlgorithmenImplementierung und Laufzeit
• Jeder Knoten vom FVS F wird von Markov-Heuristik gewählt• Dazu muss Eigenvektor π = (πi ) der Übergangsmatrix P
berechnet werden:tπ · P = tπ mit
n∑i=1
πi = 1
Laufzeit mit direkter Methode: O(|V |2.376|F |)Iterative Methode:
• Rechengenauigkeit üblicherweise beschränkt• Stellenzahl d kann als konstant angenommen werden
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Markovsche FVS-AlgorithmenImplementierung und Laufzeit
• Jeder Knoten vom FVS F wird von Markov-Heuristik gewählt• Dazu muss Eigenvektor π = (πi ) der Übergangsmatrix P
berechnet werden:tπ · P = tπ mit
n∑i=1
πi = 1
Laufzeit mit direkter Methode: O(|V |2.376|F |)Iterative Methode:
• Rechengenauigkeit üblicherweise beschränkt• Stellenzahl d kann als konstant angenommen werden
Laufzeit mit iterativer Methode: O(|A||F | 1− ln |λ|)
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Gliederung
1 Das FVS-Problem
2 Markovsche FVS-Algorithmen
3 Ergebnisse
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Betrachtete Algorithmen
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Betrachtete Algorithmen
MFVS: Speckenmeyers ursprünglicher Algorithmus
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Betrachtete Algorithmen
MFVS: Speckenmeyers ursprünglicher AlgorithmusMFVSMean: Gemittelte Version von MFVS
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Betrachtete Algorithmen
MFVS: Speckenmeyers ursprünglicher AlgorithmusMFVSMean: Gemittelte Version von MFVS
MarkovSearch: Markovsche lokale Suchfunktion• führt 100 Iterationen aus• generiert jeweils 2 Nachfolger-FVSs
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Betrachtete Algorithmen
MFVS: Speckenmeyers ursprünglicher AlgorithmusMFVSMean: Gemittelte Version von MFVS
MarkovSearch: Markovsche lokale Suchfunktion• führt 100 Iterationen aus• generiert jeweils 2 Nachfolger-FVSs
Simple: Wählt Knoten v ∈ V des Graphen G = (V ,A) mitmaximalem Produkt∑
v∈N−(v)
d−(v) · ∑v∈N+(v)
d+(v)
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Betrachtete Algorithmen
MFVS: Speckenmeyers ursprünglicher AlgorithmusMFVSMean: Gemittelte Version von MFVS
MarkovSearch: Markovsche lokale Suchfunktion• führt 100 Iterationen aus• generiert jeweils 2 Nachfolger-FVSs
Simple: Wählt Knoten v ∈ V des Graphen G = (V ,A) mitmaximalem Produkt∑
v∈N−(v)
d−(v) · ∑v∈N+(v)
d+(v)
GRASP: Multistart-Algorithmus von Resende et al• generiert 2048 FVSs• wird derzeit als bester Algorithmus angesehen
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Deterministische Algorithmen
360
370
380
390
400
410
420
430
440
450
460
470
0.05 0.10 0.15 0.20
XXX MFVSMean
XXX MFVSXXX Simple
FVS-Größe für 100 Zufallsdigraphenmit 500 Knoten in Abhängigkeit vonDichte p.
120
140
160
180
200
220
240
260
280
3 5 7 9
XXX MFVSMean
XXX MFVSXXX Simple
FVS-Größe für 100 reguläre Digraphenmit 500 Knoten in Abhängigkeit vomRang k .
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Randomisierte Algorithmem I
170
180
190
200
210
220
230
240
250
260
270
0.05 0.10 0.15 0.20
XXX MarkovSearchXXX GRASP
FVS-Größe für 100 Zufallsdigraphenmit 300 Knoten in Abhängigkeit vonDichte p.
0
50000
100000
150000
200000
250000
300000
0.05 0.10 0.15 0.20
XXX MarkovSearchXXX GRASP
Laufzeit in Sekunden.
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Randomisierte Algorithmem II
120130140150160170180190200210220230240
4 6 8 10
XXX MarkovSearchXXX GRASP
FVS-Größe für 100 reguläre Digraphenmit 400 Knoten in Abhängigkeit vomRang k .
0
5000
10000
15000
20000
25000
4 6 8 10
XXX MarkovSearchXXX GRASP
Laufzeit in Sekunden.
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MFVSMean vs. GRASP vs. MarkovSearch
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MFVSMean vs. GRASP vs. MarkovSearch
Resende Digraphen:
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MFVSMean vs. GRASP vs. MarkovSearch
Resende Digraphen:
• 40 Digraphen
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MFVSMean vs. GRASP vs. MarkovSearch
Resende Digraphen:
• 40 Digraphen• verschiedene Größen (50—1000 Knoten)
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MFVSMean vs. GRASP vs. MarkovSearch
Resende Digraphen:
• 40 Digraphen• verschiedene Größen (50—1000 Knoten)• verschiedene Dichten
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MFVSMean vs. GRASP vs. MarkovSearch
Resende Digraphen:
• 40 Digraphen• verschiedene Größen (50—1000 Knoten)• verschiedene Dichten
Optimum MFVSMean GRASP MarkovSearchFVS-Größe ≤ 6576 6964 6941 6749Laufzeit (Sek.) 193 41626 733
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
MFVSMean vs. GRASP vs. MarkovSearch
Resende Digraphen:
• 40 Digraphen• verschiedene Größen (50—1000 Knoten)• verschiedene Dichten
Optimum MFVSMean GRASP MarkovSearchFVS-Größe ≤ 6576 6964 6941 6749Laufzeit (Sek.) 193 41626 733
Weitere Informationen: M. Lemaić, E. Speckenmeyer.Markov-Chain-Based Heuristics for the Minimum FeedbackVertex Set Problem,zaik2010-596, http://www.zaik.uni-koeln.de, 2010
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Zusammenfassung
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Zusammenfassung
• Neue Markovsche Algorithmen: MFVSMean, MarkovSearch
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Zusammenfassung
• Neue Markovsche Algorithmen: MFVSMean, MarkovSearch• erzielen gute Resultate
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Zusammenfassung
• Neue Markovsche Algorithmen: MFVSMean, MarkovSearch• erzielen gute Resultate
• MFVSMean
• ist eine signifikante Verbesserung gegenüber MFVS
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Zusammenfassung
• Neue Markovsche Algorithmen: MFVSMean, MarkovSearch• erzielen gute Resultate
• MFVSMean
• ist eine signifikante Verbesserung gegenüber MFVS• übertrifft bekannte deterministische Algorithmen
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Zusammenfassung
• Neue Markovsche Algorithmen: MFVSMean, MarkovSearch• erzielen gute Resultate
• MFVSMean
• ist eine signifikante Verbesserung gegenüber MFVS• übertrifft bekannte deterministische Algorithmen• nur marginal schlechter als GRASP
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Zusammenfassung
• Neue Markovsche Algorithmen: MFVSMean, MarkovSearch• erzielen gute Resultate
• MFVSMean
• ist eine signifikante Verbesserung gegenüber MFVS• übertrifft bekannte deterministische Algorithmen• nur marginal schlechter als GRASP
• MarkovSearch• übertrifft GRASP in puncto FVS-Größe als auch Laufzeit
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Zusammenfassung
• Neue Markovsche Algorithmen: MFVSMean, MarkovSearch• erzielen gute Resultate
• MFVSMean
• ist eine signifikante Verbesserung gegenüber MFVS• übertrifft bekannte deterministische Algorithmen• nur marginal schlechter als GRASP
• MarkovSearch• übertrifft GRASP in puncto FVS-Größe als auch Laufzeit• derzeit bester Algorithmus für FVS-Problem
• Markovketten sehr gut geeignet für FVS-Problem
Das FVS-Problem Markovsche FVS-Algorithmen Ergebnisse
Vielen Dank!