Seite 1 von 3

Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 26. Jun 2015 18:54
von schreibt...
Hey allerseits,
hat vielleicht schon jemand eine Lösungsstrategie entwickelt mit der man in annehmbarer Zeit die Foo-Aufgabe Bellman-Ford lösen kann?
Derzeit benötige ich zum Lösen einer Aufgabe mind. 15 Minuten und mir fällt keine schnellere Herangehensweise ein.

Danke schon mal für Antworten :-)

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 26. Jun 2015 20:43
von Alexj1988
Invariante verstehen und man muss nicht mehr viel rechnen ;)

mfg Alex

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 27. Jun 2015 11:43
von Nullmann
Ich habe das gleiceh Problem mit der Aufgabe. Meine letzten 15 Versuchen habe ich falsch gemacht, teilweise nur wegen "einer" falschen Eingabe. Müsste den Algorithmus also verstanden haben.
Die Invariante sagt doch eigentlich nur aus, dass man bei i = 5 darf man maximal 5 Kanten benutzen, um von einem zum anderen Knoten zu kommen. Aber auch das sind 28 Zahlen, die man eintragen muss. Manche davon enthalten viele Rechnungen, manche sind offensichtlich.

Die beiden Vereinfachungen, die ich bisher gefunden habe, die aber nicht all zu schwer herauszufinden sind, wenn man sich das Ergebnis anschaut:
Die Diagonale enthält immer Nullen (von a nach a, von b nach b...) und man muss nur die Hälfte der Matrix eintragen, weil sie spiegelverkehrt ist.

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 27. Jun 2015 16:37
von Alexj1988
Nullmann hat geschrieben:Ich habe das gleiceh Problem mit der Aufgabe. Meine letzten 15 Versuchen habe ich falsch gemacht, teilweise nur wegen "einer" falschen Eingabe. Müsste den Algorithmus also verstanden haben.
Die Invariante sagt doch eigentlich nur aus, dass man bei i = 5 darf man maximal 5 Kanten benutzen, um von einem zum anderen Knoten zu kommen. Aber auch das sind 28 Zahlen, die man eintragen muss. Manche davon enthalten viele Rechnungen, manche sind offensichtlich.

Die beiden Vereinfachungen, die ich bisher gefunden habe, die aber nicht all zu schwer herauszufinden sind, wenn man sich das Ergebnis anschaut:
Die Diagonale enthält immer Nullen (von a nach a, von b nach b...) und man muss nur die Hälfte der Matrix eintragen, weil sie spiegelverkehrt ist.
Die matritzen sind immer symetrisch, da der graph ungerichtet ist.

mfg alex

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 30. Jun 2015 16:02
von Lithanel
Finde auch, dass diese Aufgabe bis jetzt die mit Anstand schwerste foo-Aufgabe ist. :|

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 30. Jun 2015 17:03
von headhumper
Alexj1988 hat geschrieben:Invariante verstehen und man muss nicht mehr viel rechnen ;)
Ich denke dir ist niemand böse, wenn du etwas expliziter wirst ;)

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 30. Jun 2015 17:08
von Lithanel
Er meint wahrscheinlich, dass man z.B. bei i=4 wegen der Invariante weiß, dass man 5 Kanten für den minimalen Pfad verwenden darf. Nun kannst du eigentlich jeden einzelnen Fall durchgehen und schauen, was der minimale Pfad ist, wenn du dabei auch diese Kantenregel einhälst. Das Problem bei diesem Vorgehen wäre halt, dass wenn du nicht genau genug schaust, es ziemlich schnell vorkommen kann, dass du einen längeren Pfad für den kürzesten hälst. Aber denke mal, da kann man nur üben üben und nochmals üben, um das etwas reflexartig sehen zu können. 8)

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 30. Jun 2015 19:32
von Nullmann
Lithanel hat geschrieben:Aber denke mal, da kann man nur üben üben und nochmals üben, um das etwas reflexartig sehen zu können. 8)
Hat sonst niemand eine bessere Vorgehensweise? Darauf war ich auch schon von alleine gekommen :D

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 30. Jun 2015 20:04
von schreibt...
Also danke schonmal für die Antworten. Ich sehe allerdings auch das Problem des leichten Übersehens eines kürzesten Pfades beim "einfach Ablesen". Im Durchschnitt benötige ich nun 8 Minuten zum lösen und die Fehler-quote ist ziemlich hoch. :/
Außerdem sehe ich den Sinn hinter der Aufgabe beim Ablesen nicht, da man dafür den Bellman-Ford Algorithmus in keiner Weise anwenden oder verstehen muss.
Fände es echt hilfreich wenn diesbezüglich jemand Licht ins Dunkel bringen könnte. ^^

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 1. Jul 2015 16:14
von AnMa
Hallo zusammen,

nach mehrmaligem Lösen von Aufgaben des Typs Bellman-Ford, benötige ich immer noch durchschnittlich 10 Minuten zum Lösen einer Aufgabe.
Da man ja im Testat 3 Versuche hat und zusätzlich noch einen anderen Algorithmus lösen muss, für den man ebenfalls 3 Versuche hat, finde ich steigt der Zeitdruck enorm, um all dies innerhalb von 30 Minuten zu schaffen. Klar, wenn man beide Algorithmen das erste Mal richtig hat, braucht man die 30 Minuten nicht ganz und die restlichen Versuche sind hinfällig. Jedoch setzt es einen enorm unter Druck, zu wissen, dass die Zeit nicht reicht, wenn man den ersten Versuch verhaut.
Daher hätte ich ein paar Alternativen, um diesen Druck zu mindern:

- Die Matrix des Bellman-Ford kleiner machen
- Die eine Hälfte der Matrix, die sowieso die gleichen Werte enthält einfach ausblenden
- Das Zeitlimit rauslassen, so dass das Testat einfach nach 3 Versuchen pro Algorithmus beendet ist und nicht nach 30 Minuten

Ich finde bei diesem Testat rückt der Zeitdruck in den Vordergrund und nicht, wie es eigentlich sein sollte, das Lösen und Verstehen der Algorithmen. Daher fände ich es sehr gut, wenn wie im vierten Testat, auf diesen Aspekt eingegangen werden würde (B-Tree verkleinern => Matrix verkleinern).

Liebe Grüße
AnMa

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 2. Jul 2015 21:00
von MikMik
Ich fände es auch gut, wenn die Aufgabenstellung angepasst werden würde, denn verstanden wie der Algorithmus funktioniert, das hat man auch bei einer 4*4 Matrix.
Eine 8*8 Matrix fehlerfrei zu lösen (auch wenn man dabei effektiv nur eine 4*8 - 8 Matrix lösen muss) finde ich etwas übertrieben, und ich bin mir sicher, wenn man sich die durchschnittliche zum Erarbeiten der Lösung verwendete Zeit anschaut, sollten die Organisatoren selber merken, dass der Arbeitsaufwand nicht ganz mit der zur Verfügung gestellten Zeit und der hohen Fehleranfälligkeit im Verhältnis steht.

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 3. Jul 2015 01:14
von CryNickSystems
Ich finde auch dass der Aufwand derzeit für Bellman-Ford viel zu hoch ist...

Bitte Veranstalter, schaut euch das nochmal an! :cry:

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 3. Jul 2015 11:01
von Anonym
Hallo zusammen,

ich habe auch sehr große Probleme mit dem Lösen der Aufgabe.

Im Video gibt es ja diese Vorgehensweise mit dem Repeated Squaring.
Hat es jemand von euch mal damit versucht und wie waren dann eure Erfahrungen damit?

Lieben Gruß

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 3. Jul 2015 11:17
von Alexj1988
CryNickSystems hat geschrieben:Ich finde auch dass der Aufwand derzeit für Bellman-Ford viel zu hoch ist...

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

Re: Lösungsstrategie foo #5 Bellman-Ford

Verfasst: 3. Jul 2015 11:23
von Sonne34
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