Lösungsstrategie foo #5 Bellman-Ford

schreibt...
Neuling
Neuling
Beiträge: 2
Registriert: 26. Jun 2015 18:47

Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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 :-)

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

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von Alexj1988 »

Invariante verstehen und man muss nicht mehr viel rechnen ;)

mfg Alex

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

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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.

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

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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

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

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von Lithanel »

Finde auch, dass diese Aufgabe bis jetzt die mit Anstand schwerste foo-Aufgabe ist. :|

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

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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 ;)

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

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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)

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

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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

schreibt...
Neuling
Neuling
Beiträge: 2
Registriert: 26. Jun 2015 18:47

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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. ^^

AnMa
Neuling
Neuling
Beiträge: 2
Registriert: 20. Jun 2015 11:27

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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

MikMik
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 24. Apr 2015 18:56

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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.

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

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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:

Anonym
Neuling
Neuling
Beiträge: 2
Registriert: 23. Apr 2015 10:07

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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ß

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

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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

Sonne34
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 3. Mai 2015 18:10

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag 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

Antworten

Zurück zu „Archiv“