Unabhängige Nullen -> Überdeckung

Moderator: Effiziente Graphenalgorithmen

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Unabhängige Nullen -> Überdeckung

Beitrag von Stille »

Hallo,

habe gerade nochmal über die Frage aus der Vorlesung nachgedacht, ob man bei mehreren Möglichkeiten für eine minimale Überdeckung eine beliebige wählen könne: ja, kann man prinzipiell machen. Im Beispiel aus der Vorlesung würde das sogar eine Iteration sparen (statt zwei Updates mit einmal delta=2 und einmal delta=1 hätte man nur ein Update mit delta=3). Evtl. könnte man dies sogar heuristisch nutzen, indem man sagt: wähle immer die Überdeckung, welche ein grösseres delta impliziert.

Falls man das Markierungsverfahren zur Erhöhung der Anzahl unabhängiger Nullen verwendet hat, kann man eine Überdeckung leicht bestimmen, indem man einfach alle bei Terminierung des Verfahrens nicht markierten Zeilen und alle markierten Spalten nimmt.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

DreamFlasher
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 102
Registriert: 12. Okt 2010 12:44

Re: Unabhängige Nullen -> Überdeckung

Beitrag von DreamFlasher »

Hallo,

ich habe das Verfahren auf den Folien leider überhaupt nicht verstanden. Was da jetzt markiert, entfernt, gestrichen, gekreuzt wird bleibt unklar.
Ich hab das jetzt so gemacht wie wir das mal früher gelernt haben, ich komm auf die korrekte Lösung, ich hoffe das ist auch für die Klausur okay, wenn wir nicht unbedingt die Methoden aus den Folien nehmen?

Ansonsten bitte ich darum, dass derjenige der das vorstellt Schritt für Schritt dazu erklärt weshalb der Schritt korrekt ist.

Ist in der "Dokumentation für den Chef" zu erläutern was genau gemacht wird oder auch warum jeder Schritt gültig ist?

Viele Grüße
Marcel
Marcel Ackermann
http://www.dreamflasher.de
Machine Learning, Natural Language Processing, Algorithms

Interesse an Machine Learning, Artificial Intelligence, Natural Language Processing? Du möchtest deine Skills und Wissen verbessern, an Wettbewerben mit anderen Begeisterten teilnehmen? Mach mit bei unserer Study Group: http://groups.google.com/group/ml-ai

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Unabhängige Nullen -> Überdeckung

Beitrag von Stille »

Hallo,

ich hatte ja versprochen, das zu überarbeiten, leider aber vergessen, es hochzuladen. Daher danke für die Erinnerung! Das Wörtchen "independent" in (3.1) war zu viel. Die Null darf natürlich nicht independent sein (denn die gibt es ja per Auswahl der Zeilen in (2) nicht). Ich habe die korrigierte und etwas kompaktere Version nun hochgeladen. Alternativ können Sie sich das Original von Kuhn hier herunterladen: http://dss.ucsd.edu/~vcrawfor/hungar.pdf

Es gibt einige Varianten dieses Markierungsalgorithmus, sowie es auch verschiedene Möglichkeiten für das Update der Dualvariablen gibt. Sofern Sie eine korrekte Variante verwenden und aus Ihrer Lösung hervorgeht, was Sie da tun, ist mir egal, was Sie verwenden.

Schönen Sonntag!
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Unabhängige Nullen -> Überdeckung

Beitrag von Stille »

DreamFlasher hat geschrieben: Ich hab das jetzt so gemacht wie wir das mal früher gelernt haben, [...]
P.S. Wo war das denn, wenn ich fragen darf?
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Unabhängige Nullen -> Überdeckung

Beitrag von Stille »

DreamFlasher hat geschrieben: Ist in der "Dokumentation für den Chef" zu erläutern was genau gemacht wird oder auch warum jeder Schritt gültig ist?
Kommt auf den Chef an. Ersteres reicht im Normalfall :D.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

DreamFlasher
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 102
Registriert: 12. Okt 2010 12:44

Re: Unabhängige Nullen -> Überdeckung

Beitrag von DreamFlasher »

Okay :) Hochschule Mannheim, Operations Research.
Hihi, das ist gut zu wissen, für später dann mal ;)

Dir auch noch einen schönen Sonntag!
Marcel Ackermann
http://www.dreamflasher.de
Machine Learning, Natural Language Processing, Algorithms

Interesse an Machine Learning, Artificial Intelligence, Natural Language Processing? Du möchtest deine Skills und Wissen verbessern, an Wettbewerben mit anderen Begeisterten teilnehmen? Mach mit bei unserer Study Group: http://groups.google.com/group/ml-ai

Antworten

Zurück zu „Effiziente Graphenalgorithmen“