H4.6b: Bellman-Ford-Durchlauf darstellen

Benutzeravatar
Tapion
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 14. Okt 2006 19:16
Wohnort: Darmstadt

H4.6b: Bellman-Ford-Durchlauf darstellen

Beitrag von Tapion »

Ich finde nirgendwo (weder in den Folien, noch im Skript) Beispiele, wie man den Bellman-Ford-Algorithmus auf Paier darstellen kann. Für z.B. Kruskal hatten wir da so eine schöne Tabelle, mit der der Algorithmus sehr anschaulich dargestellt ist. Gibt's da auch was für Bellman?
WS 2010/11 - Tutor GDI 1
SS 2010 - Tutor FGI 1+2

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

*same problem* ...der algorithmus ist ja simpel... problematisch ist nur das ganze mit Zettel und stift in eine "gültige" form zu bringen...

Sollen wir wirklich alle "v * k" Schritte einzeln aufmalen?

Benutzeravatar
mcreichelt
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 2. Mai 2007 19:23
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von mcreichelt »

In der Aufgabe steht:
Bestimmen Sie mit Hilfe des Algorithmus von Bellman und Ford den günstigsten Weg zum Transport der Waren nach Berlin. [...] Geben Sie die Knoten des kostengünstigsten Weges und dessen Länge an.
Ich glaube also nicht, dass wir den Algorithmus Schritt für Schritt darstellen sollen - es reichen wohl die Endergebnisse (also die Darstellung der Endergebnisse des Graphen und der letztendlich kürzeste Pfad).

Grüße
Marc
Den Benutzern anderer Betriebssysteme wie Linux oder OS/2 unterstellen
wir die nötigen Grundkenntnisse [...]
-- "T-DSL Montage- und Betriebsanleitung", Kapitel 6

Benutzeravatar
Tapion
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 14. Okt 2006 19:16
Wohnort: Darmstadt

Beitrag von Tapion »

"mit Hilfe des Algorithmus von Bellman und Ford"

das Ergebnis wäre ja mit jedem Algorithmus gleich. Ich denke schon, dass wir den Algorithmus anwenden sollen.
WS 2010/11 - Tutor GDI 1
SS 2010 - Tutor FGI 1+2

Benutzeravatar
Maradatscha
Computerversteher
Computerversteher
Beiträge: 353
Registriert: 2. Okt 2006 18:53

Beitrag von Maradatscha »

mein tutor wollte von mir auch irgendwie wissen, dass ich den verstanden habe und es nicht irgendwie anders gelöst habe, nur wie ich es aufschreiben soll hat er mir nicht mitgeteilt, oder ihc kann mich nicht dran erinnern

Benutzeravatar
Tapion
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 14. Okt 2006 19:16
Wohnort: Darmstadt

Beitrag von Tapion »

Ich hab das jetzt so gemacht:

Zunächst habe habe ich für jeden Knoten eine Spalte genommen, in die dann die Entfernung zum Startknoten steht. Der Kostenaufwand zum Startknoten ist 0, zu allen anderen unendlich.

Um etwas Platz zu sparen, habe ich in jeder Zeile alle ausgehenden Kanten eines Knotens betrachtet (die Knoten können ja zufällig in dieser Reihenfolge abgearbeitet werden ;)) und die jeweiligen Kosten addiert.

links steht dann immer der Vorgänger und oben sozusagen der Nachfolger und am Kreuzungspunkt wie lange man mindestens braucht, wenn man von Startknoten zum "Nachfolger" die aktuelle Kante mitnehmen will.

"rückwärts" kann man dann hinterher den Pfad auslesen.

Da der Bellman-Ford Algorithmus mit Überschreiben arbeitet, lässt sich der Pfad nicht so wirklich nebenbei "aufzählen". Mal schauen, was mein Tutor morgen oder nächste Woche dazu sagt.
WS 2010/11 - Tutor GDI 1
SS 2010 - Tutor FGI 1+2

TimN
Mausschubser
Mausschubser
Beiträge: 46
Registriert: 19. Feb 2005 12:30

Beitrag von TimN »

Soweit so richtig:

Erste Spalte gibt an, in der wievielten Iteration man ist, ansonsten für jeden Knoten eine Spalte. In den Feldern dann jeweils den aktuellen Kostenaufwand und den entsprechenden Vorgängerknoten. Den weg bekommt man tatsächlich durch ein "Re-Tracen" in der Tabelle.

Gruß Tim

baerchen
Computerversteher
Computerversteher
Beiträge: 382
Registriert: 24. Okt 2006 15:42

Beitrag von baerchen »

sollen wir den graphen als ungerichteten graphen betrachten, also jeweils hin und rückrichtung betrachten??

[edit] wer lesen kann ist klar im vorteil. tut mir leid... [/edit]
We can do this the hard way or my way ...which is basically the same thing!

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Beitrag von marlic »

Hm .. also ich hab jedes mal nach dem alle kanten betrachtet wurden einen einschnitt gemacht und den aufgeschrieben.
"Copy & Passed"

Wahlspruch der Plagiatoren

Antworten

Zurück zu „Archiv“