Lösungsstrategie foo #5 Bellman-Ford

[Alexj1988]

Das ist schon einmal gut zu wissen. Werden wir auch die Möglichkeit haben, mit weniger Knoten und niedrigeren Kantengewichten zu üben?
Damit man sich auf dem Niveau vom Testat vorbereiten kann?
Weil ich muss schon sagen, dass es ziemlich demotivierend ist, wenn man die Lösung als falsch hat, weil man einen kürzeren Weg übersehen hat..

Ich finde auch dass der Aufwand derzeit für Bellman-Ford viel zu hoch ist...

Bitte Veranstalter, schaut euch das nochmal an!

Das ist uns bekannt. Spätestens für die Testate werden die Graphen vereinfacht, dennoch könnt ihr solange an der Variante üben.


Kommende Änderung: niedrigere Kantengewichte, geringere Anzahl knoten.

mfg Alex

Liebe Grüße

Ich werde es weiterleiten.

mfg Alex

[Sonne34]

Vielen Dank.

Wie ich sehe wurde die Anzahl der Knoten schon etwas verkleinert (um 3 Knoten)
Allerdings ist der Wert bei den Kanten immer noch sehr hoch.
Ich gehe davon aus, dass sich der Schwierigkeitsgrad nicht weiter ändern wird oder?

Liebe Grüße

[Nullmann]

Allerdings ist der Wert bei den Kanten immer noch sehr hoch.

Wurde mittlerweile auch verbessert. Hatte noch keine Kantenlänge größere 20 bei meinen letzen Versuchen.

Vielen Dank an das Foo-Team!

[moritz31]

Zählen die weniger Knoten und Kantengewichte auch für Dijkstra?

[Nullmann]

Zählen die weniger Knoten und Kantengewichte auch für Dijkstra?

Djikstra wurde soweit ich weiß nicht verändert. Dort gibt es meiner Meinung nach aber auch keinen Bedarf einer Änderung.

[Thomi]

Wie lange braucht ihr denn so im Schnitt jetzt für Bellman-Ford? Ich brauche immer noch ca. 10 Minuten :/

Thomi

[Lithanel]

Ich brauche im Durchschnitt ca. 5min. Da ich das ein paar mal ausprobiert habe kann ich die richtigen Pfade jetzt einigermaßen gut rauslesen, weshalb ich viel weniger Zeit brauche, als bei meinen ersten Versuchen.

[d110]

Meine Lösungsstrategie (falls vom Veranstalter in der Form unerwünscht bitte wieder löschen):

- i nachsehen --> maximal i+1 Kanten
- Diagonalelemente der Matrix mit 0 ausfüllen
- Graph anschauen, wo sind Kanten mit geringem Gewicht?
- Für alle restlichen Kontenpaare : Länge des kürzesten Weges mit max. i+1 Kanten bestimmen und an den beiden Stellen in der Matrix eintragen (dabei besonders auf "billige" Kanten achten / Symmetrie beachten L(u, v) = L(v, u)).
- Zum Abschluss: Für alle Knotenpaare mit großer Entfernung (meistens L > 10, ggf, weniger) prüfen:
1. Ist die Distanz korrekt berechnet (gegen Verrechnen)
2. Sieht man einen kürzeren Weg (fällt einem manchmal erst auf nachdem man alle Knotenpaare schon mal durchgemacht hat.)


Finde die Aufgabe nicht so gut, ist eigentlich nur anstrengend und das bei der Hitze .
Vielleicht könnte man zu Bellman-Ford eher eine Iteration Repeated Squaring als Aufgabe machen.

[headhumper]

Gibt es jemanden, der eine "sichere" Methode zum Lösen dieser Aufgabe gefunden hat?

Die Wahrscheinlichkeit, diese Aufgabe fehlerfrei zu lösen, ist schon einigermaßen gering. Dementsprechend niedrig finde ich auch den Lernwert bei dieser Aufgabe. Es gibt wirklich tolle Aufgaben, so wie die B-tree: remove, bei der kann man tatsächlich viel lernen. Aber Bellman-Ford ist so eine Aufgabe, bei der man den Algorithmus vorwärts und rückwärts aufsagen kann und trotzdem macht man Fehler, weil man sich bei so vielen Kopfrechenoperationen einfach verrechnen "muss".

Ist so ähnlich wie beim Double-Hashing, die Aufgabe bzw. der Algo ist extrem einfach, man darf eben nur keine Rechenfehler machen. Wobei man sich Double-Hashing sehr stark vereinfachen konnte, sodass man Rechenfehler weitestgehend minimieren konnte (Platz ist nicht frei? Dann immer das Doppelte des Platzes addieren, bis freier Platz gefunden, immer Modulo rechnen, Zahlen x nahe N durch x-N ersetzen). Wenn man natürlich bei jedem Versuch/jeder Iteration die Funktionen komplett ausgewertet hat, hat man sich auch hier ziemlich sicher irgendwann verrechnet.

Bei Bellman-Ford sieht das irgendwie deutlich schlechter aus, zumindest habe ich noch keinen Weg gefunden.

[SenZe]

Dementsprechend niedrig finde ich auch den Lernwert bei dieser Aufgabe.

Um deutlich zu werden: Die Aufgabe, wie sie derzeit gestellt ist, vermittelt genau einen Punkt des BF-Algorithmus: Die Invariante, die wirklich sehr simpel ist. Alles weitere ist ein Spielchen, das sich vom Niveau her dem altbekannten Malen mit Zahlen gar nicht so unähnlich ist. Entsprechend deprimierend ist es, wenn man diese Grundschul-Aufgabe mit erschreckender Regelmäßigkeit verhaut, weil man irgendwo doch immer einen etwas kürzeren Pfad übersieht.

[Alby407]

Bei mir ist es irgendwie anders rum: Bei Bellmann-Ford hab ich weniger Probleme. Dijkstra macht mir eher zu schaffen. Für i > 7 (oder sogar i > 6) kann man fast wie bei Bellmann-Ford rangehen und den kürzesten Pfad suchen. Aber für i < 5 geht das nicht mehr im Kopf (zumindest kann ich das nicht, da muss ich mir aufschreiben, welche Knoten ich eingesammelt habe).
Bei Bellmann-Ford liegt die Schwierigkeit wirklich nur im "kürzesten Pfad" suchen.

Die Strategie von d110 ist schon sehr gut.

Habt ihr Strategien für Dijkstra?

[headhumper]

Bei Dijkstra kann man m.E. stur nach einem Schema vorgehen ohne sich zu sehr darauf verlassen zu müssen, dass die Mustererkennung des Gehirns zuverlässig funktioniert - der Knackpunkt ist sich die Priority Queue aufzuschreiben.

Siehe die ersten Minuten in dem Video auf der Wiki-Seite:
http://wiki.algo.informatik.tu-darmstadt.de/Dijkstra

Das lässt sich 1:1 auf die Foo-Aufgabe übertragen, die Queue kann man leicht aufschreiben. Ohne das verliert man den Überblick nach der dritten oder vierten Iteration, das stimmt...

Bei Bellman-Ford gibt es so eine Hilfs-Datenstruktur leider nicht (?)...

Ich habe noch ein bisschen mit B-F rumgespielt, und es nervt ehrlich gesagt einfach nur Eine Aufgabe ohne erkennbaren Sinn.

[CryNickSystems]

Sehe ich auch so, aber im Testat soll es wohl scheinbar noch eine Kante weniger geben und der Graph wohl recht eindeutig sein (Verlasst euch aber nicht auf meine Aussage ;D)

Mal sehen, was das noch wird.

[headhumper]

Problematisch wird es häufig dann, wenn statt der direkten Kante ein "Umweg" über zwei oder sogar drei Kanten kürzer ist.
Das muss man zuverlässig erkennen und sich merken.
Klar kann man die größten Zahlen nochmal kontrollieren, vielleicht auch noch zwei Mal, aber das kostet auch Zeit...

Die Anzahl Iterationen ist im Übungsmodus auch irgendwie witzlos, denn es sind immer mehr Kanten erlaubt als nötig - ich hatte bisher noch nie den Fall, dass ich die (finale) kürzeste Kante nicht nehmen durfte, weil das i nicht groß genug war. Wenn es im Testatmodus anders ist, sollte das im Übungsmodus auch irgendwie abgebildet werden (durch eine größere Variation von i, vielleicht auch mal i=2..3).

Da die Aufgabe ja auch schon testiert wird, wird sich jetzt wohl definitiv nichts mehr ändern...

[SenZe]

ich hatte bisher noch nie den Fall, dass ich die (finale) kürzeste Kante nicht nehmen durfte, weil das i nicht groß genug war.

Bei mir trat das einmal auf. Hab ich natürlich auch übersehen, weil man sich schön antrainiert hatte, dass das i ja groß genug ist...