Lösungsstrategie foo #5 Bellman-Ford

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von Alexj1988 »

Sonne34 hat geschrieben: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..
Alexj1988 hat geschrieben:
CryNickSystems hat geschrieben:Ich finde auch dass der Aufwand derzeit für Bellman-Ford viel zu hoch ist... :shock: :|

Bitte Veranstalter, schaut euch das nochmal an! :cry:
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
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 3. Mai 2015 18:10

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von 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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von Nullmann »

Sonne34 hat geschrieben: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
Erstie
Erstie
Beiträge: 13
Registriert: 27. Okt 2014 12:34

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von moritz31 »

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

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von Nullmann »

moritz31 hat geschrieben: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
Neuling
Neuling
Beiträge: 7
Registriert: 21. Apr 2015 14:48

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von Thomi »

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

Thomi

Lithanel
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 21. Apr 2015 12:13

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von 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. 8)

d110
Erstie
Erstie
Beiträge: 13
Registriert: 13. Apr 2015 19:28

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von 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 :cry: :wink: .
Vielleicht könnte man zu Bellman-Ford eher eine Iteration Repeated Squaring als Aufgabe machen.

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von 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
Erstie
Erstie
Beiträge: 20
Registriert: 13. Dez 2011 21:03

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von SenZe »

headhumper hat geschrieben: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
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 19. Jul 2014 15:40

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von 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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von 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 :evil: Eine Aufgabe ohne erkennbaren Sinn.

CryNickSystems
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 30. Apr 2015 18:27

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von 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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von 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
Erstie
Erstie
Beiträge: 20
Registriert: 13. Dez 2011 21:03

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von SenZe »

headhumper hat geschrieben: 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...

Antworten

Zurück zu „Archiv“