13. April 2016 17:11:32 CEST
Hallo,
ich habe die Aufgaben 2 und 3 (mehr oder weniger erfolgreich) bearbeitet.
Aufgabe 3 funktioniert soweit sehr gut, das Problem ist hingegen die quadratische Laufzeit, wo ich nicht wusste, wie man die denn wegbekommen soll. Bis 100 mal 100 Felder keine Probleme (dauert unter Python 30 Sekunden; man muss aber auch sagen, dass die Rechenzeiten von Python enorm lang sind) auf, größere Flächen werden dann allerdings doch schwierig.
Für die Aufgabe 2 habe ich im Prinzip nicht mehr genügend Zeit gehabt, diese vernünftig zu bearbeiten, weshalb auch die Algorithmen weniger erfolgreich sind; der erste Algorithmus funktioniert zwar, braucht aber viel zu viele Züge und ewig zum berechnen. Die Idee, Kanten zu bewerten und dann zu verschieden wäre auf jeden Fall sinnvoller gewesen als stets auf die am weitesten entfernten Pakete zu konzentrieren und dann den Rest verschieben. So wie ich das umgesetzt habe, ist das zumindest wenig zielführend.
(Eventuell bringen vielleicht sogar wenige Veränderungen ein deutlich besseres Ergebnis.) Ich habe dabei auch an den Trajan-Algorithmus gedacht, (
https://de.wikipedia.org/wiki/Algorithmus_von_Tarjan_zur_Bestimmung_starker_Zusammenhangskomponenten), welche einem aber eher bei der 3. Aufgabe als bei der 2. Aufgabe hilft.
Wer sich es trotzdem mal anschauen will:
https://onedrive.live.com/redir?resid=94FC31866F431F79!1798&authkey=!AMnUDiA1R_nYguA&ithint=folder%2cpdf
Mfg
Gabriel Dengler
