Foren » 35. BwInf

Veröffentlichung von Einsendungen nach Einsendeschluss

    • 230 Beiträge
    23. April 2017 20:08:13 CEST
    Hallo zusammen,

    wer es noch nicht mitbekommen haben sollte: Morgen ist Einsendeschluss. Nach dem Einsendeschluss kann auch gerne über die konkreten Lösungsideen und deren Umsetzungen diskutiert werden. Dann können die Einsendungen gerne auch online für andere zur Verfügung gestellt werden. Das PMS wird voraussichtlich "in den frühen Morgenstunden" am Dienstag, 25.04. geschlossen. Für den Fall, dass es technische Probleme gibt (und nicht alle Probleme sind von außen sichtbar), sollen Einsendungen nicht vor Mittwoch, 26.04. veröffentlicht werden (auch wenn das PMS schon geschlossen ist).

    Ein entsprechender Link zu der Einsendung hier wäre dann auch ganz gut, dann gibt es auch die Möglichkeit, über verschiedenen Lösungen zu diskutieren. Und Teilnehmer in den kommenden Jahren können sich auch alte Einsendungen anschauen.

    Viele Grüße
    Thomas
    • 26 Beiträge
    26. April 2017 11:16:47 CEST
    Dann fange ich hier doch mal an.
    Ich habe die Aufgaben 1 und 2 bearbeitet.
    https://1drv.ms/u/s!AmoEVYq8BVEZs3ACrTstoeuw-J7v

    Bei Aufgabe 2 habe ich Kreuzungen mit mehr als 4 kreuzenden Straßen als Verteilerkreis definiert. Hat das sonst noch jemand außer mir gemacht? xD

    Bin auf die anderen Veröffentlichungen gespannt.

    Gruß

    Fabian Märkert
    • 16 Beiträge
    26. April 2017 12:44:09 CEST
    Hallo Fabian, ich hab größere Kreuzungen nicht als Verteilerkreis definiert, aber darauf kommt es ja auch nicht an. Es ist ja immerhin immer noch eine Kreuzung, bei der 4 oder mehr Straßen kreuzen und dort die Regel "Erst Rechts oder Geradeaus statt Links" gilt. Meine gelösten Aufgaben folgen.
    • 26 Beiträge
    26. April 2017 12:52:25 CEST
    Naja ich kam halt zu den Schluss, dass der Straßenverlauf bei mehr als 4 Straßen nicht eindeutig sein kann und man dadurch nicht genau bestimmen kann, welche Straßen zum gerade ausfahren und welche zum rechts beziehungsweise links abbiegen sind. Außerdem habe mich dabei an der Realität orientiert, da es eine einfache Kreuzung (ohne spezielle Verkehrsführung) mit mehr als 4 Straßen nicht hier in Deutschland gibt.
    • 16 Beiträge
    26. April 2017 13:04:21 CEST
    Ja das mag schon stimmen, aber für dieses Problem habe ich widerum die Definition genutzt, dass ich davon ausgehe, dass sowie man im Koordinatensystem auch nur von der y-Koordinate abweicht, man links abbiegt.

    Also wir fahren nach rechts. Die nächste Kreuzung hat 5 abgehende Straßen. 3 nach oben und 2 nach unten. also darf ich die drei oberen Straßen nicht befahren, da diese nach Links von der Straße abgehen.

    Alles was links liegt bleibt ein linksabbiegen
    • 16 Beiträge
    26. April 2017 15:02:18 CEST
    Zudem steht unter Wikipedia folgende Definition zum Verteilerkreis:

    "Unter Verteilerkreis versteht man einen größeren Kreisverkehr, an dem sich mehrere wichtige Straßen kreuzen."

    Dementsprechend wäre es ein Fehler eine größer Kreuzung als Verteilerkreis anzusehen, da beim Verlassen eines Kreisverkehrs ein Abbiegevorgang nach rechts stattfindet. Auch Bilder die ich dazu gefunden habe, deuten eher auf einen Kreisverkehr als auf eine Kreuzung.
    Vielleicht, hast du aber auch den Verteilerkreis neu definiert und Wikipedia hat sich dem noch nicht angepasst :D

    PS: wie habt ihr das mit den Sackgassen gemacht (befährt euer Programm diese oder nicht?).

    Dieser Beitrag wurde am 26. April 2017 15:03:47 CEST von Christian Dechant bearbeitet
    • 26 Beiträge
    26. April 2017 15:23:41 CEST
    Dann sind es halt Kreisverkehre... haben ja beide die gleiche Funktion.
    Und ja mein Programm befährt Sackgassen, da man schließlich in Sackgassen Wenden kann.
    • 16 Beiträge
    26. April 2017 16:02:55 CEST
    Interressant. Mein Programm befährt es nicht, da ich mir denke, dass ein Navigationsgerät einen ja auch nicht in die Sackgasse lenkt. Somit sind dadurch dann auch mehr Straßen nicht bei nur Linksabbiegen zu erreichen.

    • 7 Beiträge
    • 17 Beiträge
    26. April 2017 16:31:06 CEST
    [blockquote]Christian Dechant said:
    Interressant. Mein Programm befährt es nicht, da ich mir denke, dass ein Navigationsgerät einen ja auch nicht in die Sackgasse lenkt. Somit sind dadurch dann auch mehr Straßen nicht bei nur Linksabbiegen zu erreichen.

    [/blockquote]
    Wird in der Aufgabenstellung nicht sogar gefordert, dass das Wenden in Sackgassen erlaubt sein soll?
    Zitat: ,,Im obigen Beispiel sollten beispielsweise die Routen DADEF [...] erlaubt sein" - A ist eine Sackgasse.
    Ein Navigationsgerät kann dich soweit ich weiß auch zum Wenden in eine Sackgasse lotsen, wenn du dich verfahren hast.
  • 26. April 2017 16:34:22 CEST
    @Christian Dechant
    Ist das Befahren von Sackgassen durch den Pfad DADEF im Beispiel-Rechthausen nicht explizit gefordert?

    EDIT: Da war jemand schneller als ich ;)

    @Manuel Klockow
    An einen Simplex-Algorithmus hatte ich anfänglich auch gedacht (oder einen SMT Solver)

    Btw. hier meine Lösungen zu den Aufgaben 1 und 2:

    https://link.tim-hollmann.de/a69c98c835

    Aufgabe 1 wurde auf das Project Selection Problem reduziert.
    Dieser Beitrag wurde am 26. April 2017 16:34:59 CEST von nicht mehr angemeldetes Mitglied bearbeitet
    • 45 Beiträge
    26. April 2017 16:35:58 CEST
    Ich habe drei einfache Regeln aufgestellt:

    1. Die erste Kante rechts von der Startkante ist immer frei befahrbar. Welche Kante das ist, wird mithilfe des mathematischen Winkels zwischen der Startkante und der Endkante bestimmt.

    2. Jede Endkante, welche einen mathematischen Winkel von > 180° zur Startkante hat, gilt als Linksabbiegen. Außer die Regel Nr. 1. tritt in Kraft.

    3. Jeder Nullwinkel wird automatisch zu einem Vollwinkel umgeformt.

    Dies erlaubt Sachgassen, als auch alle Kreuzungen wo d = 2 und man nicht wendet

    EDIT: Startkante ist die Kante auf, welche man sich befindet, wenn man auf die Kreuzung zufährt. Endkanten sind die Kanten, welche man im originalen Straßensystem, von der Kreuzung, befahren kann.
    Dieser Beitrag wurde am 26. April 2017 16:38:27 CEST von Simon Döring bearbeitet
    • 7 Beiträge
    26. April 2017 16:41:50 CEST
    [blockquote]Tim Hollmann said:
    @Christian Dechant
    Ist das Befahren von Sackgassen durch den Pfad DADEF im Beispiel-Rechthausen nicht explizit gefordert?

    EDIT: Da war jemand schneller als ich ;)

    @Manuel Klockow
    An einen Simplex-Algorithmus hatte ich anfänglich auch gedacht (oder einen SMT Solver)

    Btw. hier meine Lösungen zu den Aufgaben 1 und 2:

    https://link.tim-hollmann.de/a69c98c835

    Aufgabe 1 wurde auf das Project Selection Problem reduziert.[/blockquote]

    Warum hast du dich dagegen entschieden?
    • 2 Beiträge
    26. April 2017 16:44:20 CEST
    [blockquote]Simon Döring said:
    Ich habe drei einfache Regeln aufgestellt:

    1. Die erste Kante rechts von der Startkante ist immer frei befahrbar. Welche Kante das ist, wird mithilfe des mathematischen Winkels zwischen der Startkante und der Endkante bestimmt.

    2. Jede Endkante, welche einen mathematischen Winkel von > 180° zur Startkante hat, gilt als Linksabbiegen. Außer die Regel Nr. 1. tritt in Kraft.

    3. Jeder Nullwinkel wird automatisch zu einem Vollwinkel umgeformt.

    Dies erlaubt Sachgassen, als auch alle Kreuzungen wo d = 2 und man nicht wendet

    EDIT: Startkante ist die Kante auf, welche man sich befindet, wenn man auf die Kreuzung zufährt. Endkanten sind die Kanten, welche man im originalen Straßensystem, von der Kreuzung, befahren kann.[/blockquote]

    Hab ich auch so gemacht
    • 7 Beiträge
    26. April 2017 16:46:49 CEST
    Hat hier noch jemand Aufgabe 3 gelöst und will sie hochladen?
    • 31 Beiträge
    26. April 2017 17:03:09 CEST
    Ja, dann beteilige ich mich mit der Aufgabe 1 und 3 auch einmal. https://1drv.ms/f/s!AnkfQ2-GMfyUj1dDBoREx-BSZ26h (damit der Onedrive-Account auch mal irgendeinen Nutzen hat)
    Dieser Beitrag wurde am 5. Juni 2017 09:39:28 CEST von Gabriel Dengler bearbeitet
    • 16 Beiträge
    26. April 2017 17:26:12 CEST
    Jetzt wo ich so darüber nachdenke, ja stimmt ein Navi kann mich zum wenden in einer Sackgasse bringen. Allerdings Frage ich mich, warum man das Beispiel DADEF nicht auch einfacher zu DEF hätte machen können. Von daher... Zweiter Grund, der mich zu dieser Entscheidung veranlasst hat, ist, dass das Drehen in einer Sackgasse nicht immer zu einem der kürzesten Wege führt und der Fahrer des Autos, der von dem Navi angeleitet wird, hat sich ja nicht verfahren, daher sollte das Navigationsgerät ihn nicht in eine Sackgasse fahren lassen, um dort zu wenden!

    • 6 Beiträge
    26. April 2017 18:06:19 CEST
    Hallo, hier ist auch meine Einsendung.
    http://www.mediafire.com/file/dpnezrtnzafmes1/RobinSchm%C3%B6cker.zip
    Ich habe Aufgabe 1 und 2 bearbeitet.
    • 16 Beiträge
    26. April 2017 18:45:42 CEST
    @Robin Schmöcker: ich muss schon sagen, du hast die GUI ganz schön aufwendig gestaltet. Da muss man ja erst nen Lehrgang machen, um zu verstehen wie das ganze funktioniert und läuft. Hätte ich deine Dokumentation nicht gehabt, hätte ich nicht gewusst wie was funktioniert. Wo wir gerade dabei sind: Ein Anwender wäre damit wahrscheinlich überfordert.
    • 17 Beiträge
    26. April 2017 19:37:08 CEST
    [blockquote]Christian Dechant said:
    Allerdings Frage ich mich, warum man das Beispiel DADEF nicht auch einfacher zu DEF hätte machen können. Von daher...
    [/blockquote]
    Weil es ja darum geht, Beispiele dafür zu zeigen, was mit dem Verbot möglich ist und was nicht.
    [blockquote]Christian Dechant said:
    Zweiter Grund, der mich zu dieser Entscheidung veranlasst hat, ist, dass das Drehen in einer Sackgasse nicht immer zu einem der kürzesten Wege führt und der Fahrer des Autos, der von dem Navi angeleitet wird, hat sich ja nicht verfahren, daher sollte das Navigationsgerät ihn nicht in eine Sackgasse fahren lassen, um dort zu wenden!
    [/blockquote]
    Verstehe ich nicht. Du wirst ja nicht gezwungen, in deinen Routen Sackgassen zu nutzen, es geht lediglich darum, dass es erlaubt ist, sie zum Wenden zu nutzen. Und selbst wenn der Autofahrer sich nicht verfahren hat, müssen dank dem Verbot trotzdem manchmal Sackgassen verwendet werden, um zum Ziel zu kommen.
    Ein Beispiel:
    http://imgur.com/a/pUJAj
    Wie kommst du hier von E nach C, ohne in einer Sackgasse zu wenden?
    • 16 Beiträge
    26. April 2017 20:03:51 CEST
    Mein Programm würde ausgeben, dass dies nicht möglich wäre...
    • 3 Beiträge
    26. April 2017 20:56:19 CEST
    Ich finde die Antworten interessant:
    Mein Programm hat z.B. bei Aufgabe 1 Quadrat-6 nur 13 Knoten gewählt und eine Teilsumme von 311 berechnet. Ihr alle habt 25 Knoten und 333 als Summe.
    • 2 Beiträge
    26. April 2017 21:11:43 CEST
    [blockquote]Bjoern Buschkaemper said:
    Ich finde die Antworten interessant:
    Mein Programm hat z.B. bei Aufgabe 1 Quadrat-6 nur 13 Knoten gewählt und eine Teilsumme von 311 berechnet. Ihr alle habt 25 Knoten und 333 als Summe.[/blockquote]
    Meins hat auch 13 Knoten gefunden, ebenfalls 311 als Wert... Wahrscheinlich irgendeinen Sonderfall nicht abgefangen
    • 31 Beiträge
    26. April 2017 22:00:41 CEST
    Mit 25 ausgewählten Knoten kann man aber diese Summe erreichen, versuche einfach mal, die Knoten auf der Angabe zu markieren.
    • 26 Beiträge
    27. April 2017 10:45:21 CEST
    Ich finde es ziemlich interessant, dass die meisten Leute hier bereits existierende Algorithmen benutzen und dafür dann die Eingabedaten konvertieren.
    Gibt es einen Grund dafür, dass ihr keine eigenen Algorithmen geschrieben habt oder zumindest existierende Algorithmen für die gegebenen Aufgaben modifiziert habt?