Edmond's Algorithm

Moderator: Effiziente Graphenalgorithmen

murphy
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 9. Nov 2005 13:58

Edmond's Algorithm

Beitrag von murphy »

Hallo zusammen,

ich hätte eine kurze Frage zu o.g. Algorithmus. Zwar weiß ich (zumindest denke ich das :wink: ) wie das Schrumpfen funktioniert, bin mir aber beim "expand" unsicher. Wie werden denn die passenden Kanten ausgewählt?

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Edmond's Algorithm

Beitrag von MisterD123 »

naja du hast eine kante in die blüte rein die gematcht ist. Der Knoten auf den diese Kante nach dem expandieren zeigt ist der Basisknoten der blüte. von dem aus läufst du den kreis einfach ab und matchst die kanten alternierend, beginnend mit einer nicht gematchten weil der knoten ja schon an einer anderen hängt. innerhalb der Blüte hast du ja ein nahezu perfektes matching, eben mit ausnahme des basisknotens. Und der basisknoten ist eben der, der aus der blüte raus die matchingkante hat.

murphy
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 9. Nov 2005 13:58

Re: Edmond's Algorithm

Beitrag von murphy »

Hey ho,

danke für deine Antwort.

Meine Frage bezog sich auf Kapitel 3, die maximalen branchings (sorry, ich hatte das nicht erwähnt). Deine Antwort bezog sich eher auf die Matchings, oder?

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Edmond's Algorithm

Beitrag von MisterD123 »

ups, hatten wir noch ein anderes schrumpfen als blüten? :D dann hab ich da was vergessen

als würd ich mir algorithmen-namen merken hoho

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

Re: Edmond's Algorithm

Beitrag von Stille »

Hallo,

ja, da schrumpft man allerdings kritische Kreise.

Das Prinzip beim Expandieren ist ähnlich einfach: man wählt im azyklischen Zustand (nach Schrumpfen aller krit. Kreise) die Kante(n) größtmöglichen Gewichts. Dann expandiert man auf den nächsten Level, die gewählte(n) Kante(n) bleiben in jedem Fall erhalten. Dann expandiert man weiter und wählt aus den geschrumpften krit. Kreisen jeweils die Kanten größtmöglichen Gewichts, so dass die Branching-EIgenschaft nicht verletzt wird (bzw. lässt man die Kante kleinsten Gewichts im Zyklus einfach weg). Die Kantengewichte passt man jeweils durch Rücktransformation entsprechend an.

Wichtig ist, dass Entscheidungen bzgl. der Kantenwahl, die auf einem "geschrumpfteren" Level zustande kamen, niemals verworfen werden.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

murphy
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 9. Nov 2005 13:58

Re: Edmond's Algorithm

Beitrag von murphy »

Hallo,

danke für die Erklärung! Hab es nachvollziehen können.

Gruß

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

Re: Edmond's Algorithm

Beitrag von DreamFlasher »

Was zum Verständnis noch wichtig ist (wollte keinen neuen Thread aufmachen, aber ist für meine Begriffe wichtig) und auf den Folien leider nicht erklärt/definiert ist:

Code: Alles auswählen

c(ai) = min_{j}(c(x(j),j) | j el V
Also wir addieren immer die minimalen Kosten innerhalb eines Kreises drauf.
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

Romeo
Erstie
Erstie
Beiträge: 12
Registriert: 16. Nov 2011 10:03

Re: Edmond's Algorithm

Beitrag von Romeo »

Hey,

Die \(a_i\) werden auf Folie III.51 genauso definiert, wie du es beschreibst.

Viele Grüße
Roland

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

Re: Edmond's Algorithm

Beitrag von DreamFlasher »

Hi,

Tatsache, das ist gut, dann deckt sich das ja :)

VG 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

Antworten

Zurück zu „Effiziente Graphenalgorithmen“