Beispiel ungarische Methode

Moderator: Effiziente Graphenalgorithmen

David
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 23. Jun 2005 15:28

Beispiel ungarische Methode

Beitrag von David »

Hallo zusammen,

ich verstehe eine Berechnung im Beispiel zur ungarischen Methode nicht. Auf Folie 308 werden u und v aktualisiert. Warum ist v = (-1,0,0,0)? Nach der Formel auf Folie 306 müssten doch alle Werte reduziert werden, außer den gecoverten Werten. Also v = (0,-1,-1,-1)!

Denkfehler? Formel falsch? Beispiel falsch?

Kmiecik
Neuling
Neuling
Beiträge: 4
Registriert: 12. Feb 2010 20:22

Re: Beispiel ungarische Methode

Beitrag von Kmiecik »

Ich tipp ma drauf, dass die Formel falsch ist.
u und v geben ja nur an wie gross die Optimallösung ist. Welche Kanten man nimmt, ist unabhängig von v und u, wenn du dir jetzt die Kosten der Kanten der Optimallösung im Beispiel aufsummierst, dann kommst du auf 5.

Also denk ma soll in der Formel bei
vj = vj - delta für (j element J)
heissen und nicht
vj = vj - delta für (j nicht-element J)

David
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 23. Jun 2005 15:28

Re: Beispiel ungarische Methode

Beitrag von David »

Ok, hört sich sinnvoll an.

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

Re: Beispiel ungarische Methode

Beitrag von Stille »

Ja, so ist es. Copy&Paste hat nicht nur Vorteile. Ist inzwischen korrigiert.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“