Foren » 39. Bundeswettbewerb Informatik

[39.2 A3 Eisbudendilemma] Brute Force Zeit

    • 4 Beiträge
    5. Januar 2021 22:11:03 CET

    Meine Brute-Force-Rust Implementierung der Aufgabe kann schon nach 80 Sekunden (eisbuden4.txt) eine valide Lösung generieren. Generell lässt sich potentiell auch in 1h eine Lösung, mit dummer Optimierung, selbst für die schwierigeren Beispiele finden. Wird eine Lösung der Aufgabe oder ein Algorithmus gefordert der auch auf einem 30 Jahre alten Heimcomputer eine Lösung finden würde?

    Wahrscheinlich letzteres, wollte dennoch nochmal sicher gehen :)


    Dieser Beitrag wurde am 5. Januar 2021 22:22:06 CET von Hannes Furmans bearbeitet
    • 66 Beiträge
    5. Januar 2021 22:39:07 CET

    Es kommt bei Algorithmen im allgemeinen Fall nicht darauf an, ob sie für bestimmte Testfälle auf bestimmten Computern schnell genug sind. Häufig ist das Laufzeitverhalten ein wesentliches Kriterium für die Qualität vom Algorithmus, d. h. wie viel länger er braucht, wenn (in diesem Fall) die Anzahl der Häuser allgemein um einen bestimmten Faktor wächst.

    Brute-Force-Lösungen haben oft exponentielle Laufzeit, sind also nicht mehr zu gebrauchen, wenn es schon nur vielleicht 100 Häuser gibt. Außerdem ist es keine Schwierigkeit, eine Brute-Force-Lösung (mit dummer Optimierung) zu implementieren; in den Lösungshinweisen vergangener Wettbewerbe findet sich ein Bewertungskriterium „Laufzeitverhalten“. Das ist aber natürlich von der Aufgabe abhängig. Bei manchen Problemen ist es auch nicht möglich, sie schneller (mit besserem Laufzeitverhalten) zu lösen; dann kommt es auf Optimierungen an.

    Als Antwort auf deine Frage: Man kann das Problem (die Beispieltestfälle) sicher auch mit Brute-Force lösen, aber das ist wahrscheinlich nicht die beste Möglichkeit. Die Aufgaben werden schließlich nicht nur mit „richtig“ oder „falsch“ bewertet: schnellere Algorithmen sind (fast?) immer besser.