- left
- right
- up
- down
> Ist Lisa punktförmig?
Ja, der Einfachheit halber.
> Im BWInf-Forum gab es den offiziellen Hinweis, dass an einem
> Berührpunkt zweier Polygone
> für Lisa kein Durchkommen ist. In den bereitgestellten Beispielen tritt
> dieser Fall aber - wie auch der Fall, dass zwei verschiedene Polygone
> eine gemeinsame Strecke haben, die lt. Forum ebenfalls kein Durchkommen
> ermöglichen soll - nicht auf.
> Muss die einzureichende Lösung diese Fälle nun berücksichtigen, um
> keinen Punktabzug zu riskieren, oder nicht?
>
Wenn man auf diese besonderen Fälle in der Dokumentation
eingeht, werden auch sinnvolle Antworten darauf erwartet.
Es dürfen zusätzlich auch eigene Beispiele verwendet werden.
Im Übrigen kann eine schwierige Erweiterung der Aufgabenstellung
und ihre Lösung in der 2. Runde wertvolle Pluspunkte bringen.
Inwieweit die besonderen Fälle dazu gehören, wird davon
abhängen, wie schwierig sie sind und wie sie gelöst werden.
> In Beispieldatei 5 gibt es einige Merkwürdigkeiten:
> - drei Punkte des Polygons 3 liegen auf einer Strecke
> - drei Punkte des Polygons 10 liegen auf einer Strecke
> - zwei Punkte des Polygons 11 liegen dicht beieinander: (380,340)
> und (381,340)
> - zwei Punkte des Polygons 12 liegen dicht beieinander: ( 80,300)
> und ( 81,300)
>
> Diese Merkwürdigkeiten irritieren mich.
> Wird erwartet, dass das Programm überflüssige Punkte explizit wegoptimiert?
>
Nein, das wird nicht erwartet, die Merkwürdigkeiten sollen nicht verunsichern;
eventuell testen sie nur die Eingabe des Programms ohne Auswirkungen auf Lisas Weg.
Mario Albrecht said:
Ja, der Bus trifft erst auf Lisa, nachdem er von der Haltestelle abgefahren ist.
Ich habe es noch nicht überprüft, aber könnte der optimale Treffpunkt nicht auch an der Haltestelle liegen?
Wie wichtig ist ein schneller Algorithmus bei der Aufgabe?
Bei den Dokumentationsinfos steht ja nicht mal, dass die Laufzeit angegeben werden muss
(neben Daten wie Länge des Weges, Zeit des Treffpunktes usw.)
Sollte man sich also überhaupt darauf konzentrieren, dass die Laufzeit gering bleibt oder eher auf andere Sachen?
Wichtige Eigenschaften der eingesetzten Algorithmen wie z.B. Laufzeit sind natürlich stets ebenfalls interessante Angaben. Die Laufzeit sollte sich immer im vernünftigen Rahmen bezüglich der Problemgröße halten, daher sind konkrete Angaben hierzu vorab nicht weiter möglich.
Leider ist mir der Inhalt der Frage nicht ganz klar, aber ich versuche mal eine Antwort:
Beweise wie in der Mathematik kommen beim BwInf eher selten vor, dagegen sind Hinweise und Nachweise anhand von Beispieldaten, Zufallsdaten und Ergebnisvergleiche etc. über die Qualität eines Verfahrens relativ häufig. Die Lösungsidee sollte stets klar beschrieben und begründet werden, ggf. auch im Vergleich zu anderen Lösungsideen.
Bei dieser Aufgabe könnte man sich tatsächlich auch einen kleinen mathematischen Beweis vorstellen, z.B. warum Lisas Weg stets einen bestimmten Verlauf haben sollte, um ein kurzer Weg zu sein. Diese Möglichkeit hängt jedoch u.a. vom konkreten Verfahren zur Wegberechnung ab, so dass ich hier nur recht allgemeine Aussagen machen kann und werde.
Matej Svaral said:
Sollte in der Doku die Lösungsidee nur sehr ausführlich beschrieben werden, oder auch bewiesen werden, dass es die optimale Lösungsidee ist
Ich glaube nicht, dass es tatsächlich eine optimale Lösungsidee gibt, sondern eher viele gleichwertige Wege um ans Ziel zu kommen.
Meinst du vielleicht ob gezeigt werden soll, dass mit der Lösungsidee der optimale Weg gefunden wird? Ich denke, das müsste in der Dokumentation schon klar werden, da es ja nur eine Lösung der Aufgabe ist, wenn tatsächlich der kürzest mögliche Weg gefunden wird. Man sollte also vermutlich schon zeigen, dass ein kürzerer Weg nicht möglich ist.
Ich hätte noch eine Frage zu dem Dateiformat. Sind die Punkte der Polygone nach einem bestimmten Schema angegeben (d.h. die Eckpunkte im Uhrzeigersinn oder entgegengesetzt) oder kann das von Polygon zu Polygon variieren?
Die Reihenfolge bzw. mit/entgegen dem Uhrzeigersinn kann variieren, siehe hierzu auch beispielhaft SVG.
Hallo,
ich habe eine Frage bezüglich der Bearbeitung der fünf Beispiele.
Darf man die Vorgehensweise (Code) pro Beispiel ändern, da man unterschiedliche Komplexititäten in den Beispielen hat, oder muss man sozusagen denselben Code auf alle Bsp. anwenden können ?