Fehler beim Bellman-Ford Algorithmus

ChristophM
Neuling
Neuling
Beiträge: 2
Registriert: 17. Sep 2013 11:52

Fehler beim Bellman-Ford Algorithmus

Beitrag von ChristophM »

Hi,
ich habe glaube ich einen Fehler beim Bellman-Ford Algorithmus im Wiki gefunden. Abgesehen davon das der beschriebene Algorithmus nicht das Single-source shortest-paths Problem löst wie beispielsweise in "Introduction to Algorithms" scheint der Verfasser des Artikels ein wenig mit den exponenten durcheinander gekommen zu sein. So wird in der Auxilary Data ein mal L als M^1 initialisiert, in der Induction basis allerdings als M^0. Außerdem steht das Theorem im Paths Artikel zur Potenzrechnung im Widerspruch zur Bellman Ford Invariante. Deshalb wäre ich froh, wenn dies entweder geändert wird, oder aber mir jemand erklären kann wo mein Denkfehler liegt und warum das doch richtig sein soll.

sbechtel
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 17. Apr 2013 19:13

Re: Fehler beim Bellman-Ford Algorithmus

Beitrag von sbechtel »

Ist mir auch gerade aufgefallen. Im Video wird auch bei M^1 = L gestartet und nach i Iterationen existiert die Matrix M^(i+1) mit i+1 Kanten. Im Wiki steht, dass M^i nach i Iterationen i+1 Kanten enthält, also vollkommen durcheinander. Ich empfinde es persönlich als etwas schwer und kritisch, wenn solche Ungenauigkeiten sich häufen. Was soll ich denn nun in der Klausur hinschreiben? Ich fände es schade, Punktabzüge zu bekommen, weil ich mich für eine Notation aus der offiziellen Quelle entscheide, die am Ende falsch ist. Abgesehen davon erschwert es natürlich die Korrektur.

edit: Mir ist gerade aufgefallen, dass die Änderung mit M^0 von R Egert hinzugefügt wurde. Da das Video von Prof. Weihe M^(i+1) enthält, werde ich mich an diese Notation halten, sofern nicht noch etwas anderes kommt.

RalfKundel
Erstie
Erstie
Beiträge: 11
Registriert: 17. Apr 2013 15:16
Wohnort: Darmstadt

Re: Fehler beim Bellman-Ford Algorithmus

Beitrag von RalfKundel »

Hi,
ich bin eben auch über das Problem gefallen.

problem ist:
wenn wir sagen M^0 = L, also nach i>=0 iterationen haben wir M^i
ist die Abbruchbedingung wieder falsch, die lautet: i = n-1
z.B. wenn wir zwei knoten haben wären wir demnach nach der ersten Iteration fertig, wir sind allerdings schon zuvor fertig. dann müsste break: i = n-2 sein.

Alternativ könnte man sagen: nach i Iterationen enthält M^(i+1) den kürzesten Pfad mit maximal i+1 Kanten.

Die Frage bleibt: was sollen wir in der Klausur machen???

vg
Ralf

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Fehler beim Bellman-Ford Algorithmus

Beitrag von Assax »

Mit dem Problem schlage ich und paar andere hier auch schon seit gestern herum.
Was aber auch nicht zur Lösung beiträgt ist, dass vor der Änderung im Wiki von R Egert "M" gar keine Potenz hatte (abgesehen von der Auxiliary Data).
In der Vorlesung 2012 war die Invariante auf Papier noch "... Matrix M enthält kürzesten Pfad über I+1 Kanten", da war auch von keinen Potenzen die Rede. Damit gibt es jetzt drei Möglichkeiten, M^i, M und M^i+1.
Ein Statement wäre von großer Hilfe :roll:

ChristophM
Neuling
Neuling
Beiträge: 2
Registriert: 17. Sep 2013 11:52

Re: Fehler beim Bellman-Ford Algorithmus

Beitrag von ChristophM »

Ich persönlich denke ja, dass im Sinne der Matrikmultiplikation M^1 = L sein sollte und M^0 auf der diagonalen 0 und an allen anderen Stellen + unendlich sein sollte. Demnach wäre dann die Invariante, dass nach i>= 0 Iterationen M(i+1)(v,w) den kürzesten (v,w) Pfad mit i+1 Kanten enthält. Wenn man an der Stelle Variante und Abbruchbedingung beibehält müsste der Algorithmus stimmen.
Allerdings bin ich doch ein wenig enttäuscht, dass obwohl genügend Zeit zum verbessern des Artikels war dies nicht geschehen ist und auch nicht auf dieses Thema von offizieller Seite geantwortet wurde obwohl in den Informationen zur Klausur steht: "Sollte in dieser Version noch ein Fehler oder eine Unklarheit zutage treten, wird diese Version durch eine neue ersetzt."

Antworten

Zurück zu „Archiv“