Foren » 37. BwInf

Fragen zur 2. Runde – Aufgabe 1: Lisa rennt

    • 93 Beiträge
    20. Dezember 2018 11:29:58 CET

    Hier könnt ihr Fragen zur Aufgabe 1 (Lisa rennt) der 2. Runde stellen.


    Dieser Beitrag wurde am 20. Dezember 2018 11:30:09 CET von Mario Albrecht bearbeitet
    • 3 Beiträge
    29. Dezember 2018 00:42:56 CET

    Zählen bekannte Algorithmen wie etwa Dijkstra's, auch wenn sie der zentrale letzte Schritt zur Lösung sind, als "nützliche Hilfestellung", wie es im FAQ genannt wird, für die man eine Library benutzen kann? Oder sollte man diese selbst implementieren, auch wenn die so oder so für den Graphen genutzte Library eine solche Funktion besitzt?

    • 93 Beiträge
    29. Dezember 2018 03:26:26 CET

    Wenn die verwendete Library einen geeigneten Algorithmus (z.B. von Dijkstra) bereits zur Verfügung stellt, muss man ihn nicht selber programmieren, aber man sollte den Algorithmus verstanden haben, um alles klar dokumentieren zu können.

  • 29. Dezember 2018 18:36:49 CET

    Ist eine graphische Ausgabe nötig?

    • 93 Beiträge
    30. Dezember 2018 01:26:46 CET

    Die Ergebnisse sollen klar und nachvollziehbar dokumentiert werden, hierfür ist eine graphische Darstellung sicherlich hilfreich.

  • 30. Dezember 2018 09:45:14 CET

    Danke

  • 30. Dezember 2018 10:18:56 CET

    In welcher Größenordnung würden sich die Eingaben ungefähr bewegen (d.h. wie sollte der Maßstab der graphischen Darstellung sein)?

    Oder ist der Maßstab der jeweiligen Eingabe anzupassen?

  • 30. Dezember 2018 10:37:47 CET

    Wodurch sind die einzelnen Punkte und wodurch deren zwei Koordinaten getrennt?

    • 5 Beiträge
    30. Dezember 2018 16:42:17 CET

    Du kannst den Maßstab doch relativ zur Eingabe anpassen oder in der Grafik auf eine feste Größe strecken.


    Das Material zu Runde2 ist erst ab Mitte Januar 2019 verfügbar - du wirst dir also vorerst eigene Daten
    generieren müssen in denen du das Format frei wählen kannst

    • 2 Beiträge
    2. Januar 2019 11:28:30 CET

    Hallo, ich habe mehrere Fragen zu den Polygonen:

    1. Im Beispiel sind alle Polygone konvex, ich vermute dass dies allgemein nicht unbedingt der Fall ist?
    2. Können sich zwei oder mehrere Polygone berühren bzw. überlappen oder kann man das ausschließen?
    3. Sind bei den Polygonen alle Punkte entgegengesetzt des Uhrzeigersinns ablaufbar oder sind Polygone wie ([ 1,0], [0,1], [0,-1],[-1,0])  auch zu berücksichtigen? Und wäre dann der Punkt [0,0] passierbar oder nicht?

     

  • 2. Januar 2019 13:20:55 CET

     Zu Frage 3. : Praktisch würde es kaum Sinn ergeben, wenn der Punkt 0,0 in einem Hindernis läge, da dort die Haltestelle ist. Diese muss ja für Bus und Passagiere zugänglich sein. Ebenso kann denke ich auch ausgeschlossen werden, dass ein Hindernis auf der Straße ist, da der Bus dort nicht durchfahren könnte.

    Ich hätte selbst noch eine Frage (eigentlich ein Spezialfall von Frage 1): Sind überschlagene Polygone möglich?

    Außerdem: Kann man davon ausgehen, dass ein Weg vom Haus zur Straße möglich ist, das Haus also nicht vollständig von Hindernissen umgeben ist sich irgendwo eine Blockade befindet?

    Das meint: Wenn man den Maßstab so wählt, dass alle Hindernisse draufpassen, kann man davon ausgehen, dass innerhalb dieses Ausschnitts der gesuchte Weg gefunden werden kann (dieser den Ausschnitt also nicht verlässt)?


    Dieser Beitrag wurde am 4. Januar 2019 09:25:13 CET von nicht mehr angemeldetes Mitglied bearbeitet
    • 2 Beiträge
    2. Januar 2019 13:55:35 CET
    Merlin Mendel said:

     Zu Frage 3. : Praktisch würde es kaum Sinn ergeben, wenn der Punkt 0,0 in einem Hindernis läge, da dort die Haltestelle ist. Diese muss ja für Bus und Passagiere zugänglich sein. Ebenso kann denke ich auch ausgeschlossen werden, dass ein Hindernis auf der Straße ist, da der Bus dort nicht durchfahren könnte.

     

    Das war nur als ein Beispiel für ein irgendwo liegendes sich "überschlagendes Polygon" gedacht, ich kannte diesen Fachbegriff nicht smile.

     

     

  • 2. Januar 2019 17:38:26 CET

    achso

  • 2. Januar 2019 18:02:42 CET
    Martin Boehlau-Godau said:
    Merlin Mendel said:

     Zu Frage 3. : Praktisch würde es kaum Sinn ergeben, wenn der Punkt 0,0 in einem Hindernis läge, da dort die Haltestelle ist. Diese muss ja für Bus und Passagiere zugänglich sein. Ebenso kann denke ich auch ausgeschlossen werden, dass ein Hindernis auf der Straße ist, da der Bus dort nicht durchfahren könnte.

     

    Das war nur als ein Beispiel für ein irgendwo liegendes sich "überschlagendes Polygon" gedacht, ich kannte diesen Fachbegriff nicht smile.

     

     

    Ich denke, der Punkt 0,0 wäre trotzdem nicht passierbar, da dort ja die Kanten des Polygons sind.

    Wenn du die Figur z.B. aus Seilen formen würdest, könntest du ja am Kreuzungspunkt deine Hand trotzdem nicht durch bewegen


    Dieser Beitrag wurde am 2. Januar 2019 18:03:19 CET von nicht mehr angemeldetes Mitglied bearbeitet
    • 93 Beiträge
    10. Januar 2019 12:09:53 CET

    Weder an der Haltestelle noch entlang der Landstraße befinden sich Hindernisse.
    Die Hindernisse berühren auch nicht die Haltestelle oder die Landstraße.

    Man kann annehmen, dass es stets einen Weg von Lisas Haus zur Landstraße gibt.

    > Wenn man den Maßstab so wählt, dass alle Hindernisse draufpassen,
    > kann man davon ausgehen, dass innerhalb dieses Ausschnitts der
    > gesuchte Weg gefunden werden kann (dieser den Ausschnitt also nicht verlässt)?

    Nein, davon kann man nicht ausgehen.

    Antworten zu den Polygon-Fragen:

    1. Die Polygone können konkav und/oder konvex sein und umschließen stets eine tatsächliche Fläche (Flächeninhalt größer Null).
    2. Mehrere Polygone können sich berühren, aber überlagern/überlappen sich nie.
    3. Die einzelnen Eckpunkte eines Polygons sind entweder im oder gegen den Uhrzeigersinn angegeben.
    • 1 Beiträge
    10. Januar 2019 12:39:09 CET

    Gibt es eine maximale länge der Straße oder ist die Straße Theoretisch unendlich lang?

    Und: wenn zwei Polygone den gleichen Punkt von beiden seiten berühren kann Lisa dann trotzdem vorbei?

     

     


    Dieser Beitrag wurde am 10. Januar 2019 12:40:37 CET von Jonas Rubeck bearbeitet
    • 93 Beiträge
    10. Januar 2019 13:26:10 CET

    Die Landstraße ist theoretisch unendlich lang. 

    An Stellen, an denen sich mehrere Polygone berühren, ist kein Durchkommen für Lisa,
    weder an gemeinsamen Punkten noch entlang gemeinsamer Randstrecken von Polygonen.

     

    • 5 Beiträge
    12. Januar 2019 22:32:43 CET

    Gibt es Abzüge für Lösungswege, welche auf Bruteforce basieren?

    • 14 Beiträge
    13. Januar 2019 21:33:34 CET
    Merthan Erdem said:

    Gibt es Abzüge für Lösungswege, welche auf Bruteforce basieren?

    Ich vermute sehr stark, dass das der Fall ist. In der zweiten Runde soll ein möglichst effizienter Algorithmus entwickelt werden. Brute Force zählt aber im Allgemeinen nicht zu den effizienten Algorithmen, zumindest wenn es offensichtlich schnellere und effizientere Algorithmen gibt, was bei dieser Aufgabe so zu sein scheint. Nach meinen Erfahrungen gibt es für ineffiziente Algorithmen wie auch schon in der ersten Runde Punktabzug.

    Edit: Wenn man Brute force durch Backtracking optimiert, können tatsächlich oft genügend effiziente Algorithmen entstehen (beispielsweise bei Aufgabe 1 der 2. Runde letztes Jahr). Insbesondere, wenn sich kein anderer Lösungsweg finden lässt, ist das einen Versuch wert. Ob das bei dieser Aufgabe sinnvoll ist oder eher nicht, ist eine andere Frage.


    Dieser Beitrag wurde am 14. Januar 2019 13:21:47 CET von Lukas Rost bearbeitet
    • 5 Beiträge
    13. Januar 2019 21:43:41 CET

    Dem kann ich nicht ganz zustimmen, da BruteForce häufig guter Ansatz ist, den es dann noch weiter zu optimieren gilt. Auch dadurch können durchaus passable Laufzeiten entstehen.

    Ob es bei diesem speziellen Problem günstig ist ist die andere Frage.

    • 260 Beiträge
    15. Januar 2019 10:52:26 CET
    Alex F. said:

    Dem kann ich nicht ganz zustimmen, da BruteForce häufig guter Ansatz ist, den es dann noch weiter zu optimieren gilt. Auch dadurch können durchaus passable Laufzeiten entstehen.

    Ob es bei diesem speziellen Problem günstig ist ist die andere Frage.

    Wenn ein Brute-Force-Ansatz (d.h. Aufzählen aller Möglichkeiten, zu einer Lösung zu kommen) nicht nur oberflächlich "optimiert", sondern substanziell von der Laufzeit her verbessert wird, ist es kein Brute-Force-Ansatz mehr. Von "Backtracking" war ja schon die Rede, "Branch-and-Bound" ist ein weiteres Stichwort in dieser Richtung. Dazu findet man im Netz bestimmt Informationen, und ansonsten auch in Büchern wie "Fit fürs Studium - Informatik" von Fischbeck, Boockmeyer und Neubert (die beiden letzten sind ehemalige BwInf-Teilnehmer) oder "Ideen der Informatik" von Uwe Schöning.

    • 93 Beiträge
    19. Januar 2019 00:30:40 CET

    WICHTIG:

    Die zu bearbeitenden Beispieldaten und weitere wichtige Informationen sind nun publiziert:

    https://bwinf.de/bundeswettbewerb/37/2-runde/material-372/


    Dieser Beitrag wurde am 19. Januar 2019 00:32:07 CET von Mario Albrecht bearbeitet
    • 5 Beiträge
    19. Januar 2019 22:46:57 CET

    Ich gehe davon aus, dass eine Längeneinheit / ein Pixel einem Meter entspricht.

    Sollte vielleicht mit in die Dokumentation der Beispieldaten...


    Dieser Beitrag wurde am 19. Januar 2019 22:54:30 CET von Alex F. bearbeitet
    • 93 Beiträge
    21. Januar 2019 01:51:35 CET

    Die Pixelzahl ist eigentlich von der Darstellung auf dem Monitor abhängig, aber in der Aufgabenstellung steht bereits ein entsprechender Hinweis: "... und alle Längen in Metern angegeben werden."

  • 22. Januar 2019 11:10:25 CET

    Sind negative y-Werte möglich (können also Punkte unterhalb der Haltestelle liegen)?