- left
- right
- up
- down
Hier sind meine Lösungen: https://github.com/ChuangSheep/bwinf2020
Für Aufgabe 1 habe ich nur die Straßenlänge berücksichtigt. Ich konnte keine Gegenbeispiele finden, wo die Prämisse ({\sum_{i = 0}^{n - 1} c_{i,j} x_i } \leq 1000 \forall j \in \{0,1,...,9\}) erfüllt ist und es aber unmöglich ist, dem Anbieter einem festen Platz zuzuordnen. Das zu bewiesen habe ich nicht geschafft, vielleicht weil es doch Gegenbeispiele gibt?
Aufgabe 2 kann man einfach mit einem linearen Gleichungssystem lösen.
Hier ist meine Einreichung:
Benedikt Kuder said:
Hier meine Dokumentationen:
Wäre an Lösungen/Ausgaben für Aufgabe 1 interessiert da ich da nur optimiert habe und wissen will wie nah ich an anderen Ergebnissen bin.
Als NP-schweres Problem könnte selbst das Bruteforcen viel Zeit benötigen. Insbesondere wenn man Eingaben wie Flohmarkt7.txt denkt. Mich würde aber auch interessieren, wenn jemand eine vollständige Lösung hat (und wie die Person da hingekommen ist).
Dann geselle Ich mich doch auch mal mit meiner Einreichung dazu. Ich habe Aufgabe 2 und 3 bearbeietet.
Ich habe die Aufgaben 2 und 3 bearbeitet:
In A2 stelle ich jede Beobachtung als Matrix mit Aussagen (kann sich Obst X in Schüssel Y befinden?) dar, die Lösung erhält man, indem man die komponentenweise logische Konjunktion bildet. Laufzeit (b: Anzahl Beobachtungen, n: Anzahl Obstsorten) O(b * n^2)
A3 habe ich mit Brute-Force gelöst. Für jede mögliche Konstellation K lässt sich dabei in O(1) (nach Vorberechnung in O(U^3)) die andere Konstellation L' errechnen, die die meisten Stimmen erhalten würde - genau dann, wenn das mehr als die Hälfte der Anzahl der Häuser ist, ist K instabil. Gesamte Laufzeit: O(U^3)
Und hier die Einsendung: https://github.com/LinuxUserJTB/Einsendung_BwInf_39_2
Gerade auch nochmal Zeit gefunden ein paar Worte dazu zu schreiben, was ich gemacht habe.
Bei Aufagbe 2 habe ich jeder Obstsorte auf Basis der Beobachtungen in denen sie vorkommen einen Wert zu gewiesen. Folgend sind also alle äquivalenten Obstsorten nicht voneinander zu unterscheiden. Dann kann man einfach alle Obstsorten raussuchen die die Werte der gesuchten Obstsorten besitzen. Worstcase ist der Ansatz O(k*n^2). Im Avargecase ist der Ansatz O(k*n).
Bei Aufgabe 3 habe ich zunächst Untersucht, wie sich ein einzelnes Zentrum auf dem Zahlenstrahl verhält. Unter der gegebenen Bedingung ist jeder Punkt zwischen unterem und oberen Median ein stabiles Zentrum. Das dies auch für alle 3 Zentren auf dem Kreis gilt (jeweils für die Menge an Punkten, zu denen sie die nächsten sind) habe ich einfach mal angenommen. Vielleicht ließe sich das auch beweisen, aber ich fand, dass das als Heuristik durchgehen kann. Durch diese und ein paar weitere Beobachtungen kann ich die Menge an Kandidaten reduzieren und dann einfach mit einander vergleichen. Laufzeit dürfte O(n^6) sein, aber da bin ich mir gerade wirklich nicht sicher.
Bei Aufgabe 1 konnte ich Subset-Sum auf das Problem reduzieren und darüber die NP-Vollständigkeit zeigen. Ansonsten hat meine Heuristik denselben Ansatz wie die von den meisten hier, zuerst Reihenweise das Feld zu füllen.
Aufgabe 2 habe ich wie Jonathan auch per Matrix mit Einträgen a_f,s gelöst, die angeben, ob Frucht f in Schüssel s liegen kann. Zusätzlich habe ich die Aufgabe dahingehend erweitert, dass das Programm ausgibt, welche Informationen noch benötigt sind, um eine eineindeutige Zuordnung feststellen zu können (dabei soll die Anzahl der Informationen/Beobachtungen minimiert werden).
Ich habe Aufgabe zwei und drei in C++ gelöst: https://github.com/christopher-besch/bwinf_39_round2
Für Aufgabe drei habe ich ein Visualisierungsprogramm für's Web geschrieben. Man kann es hier benutzen. Der Source Code ist hier: https://github.com/christopher-besch/lake_visualizer
Dann stelle ich mal auch Lösungen vor.
Aufgabe 2 habe ich ähnlich zu einigen, die bisher vorgestellt haben, gelöst. (Ich habe nicht alles durchgelesen.) Der vollständigkeit halber hier meine Dokumentation.
Bei Aufgabe 3 habe ich eine Lösung mit O(N^3/K^2) im Averagecase. Man kann nämlich zeigen, dass sich bei einer stabilen Konfiguration die Anzahlen der Häuser zwischen Eisdiele 1 und 2, zwischen Eisdiele 2 und 3 sowie zwischen Eisdiele 3 und 1 jeweils höchstens um 3 unterscheiden, was den Suchraum deutlich verkleinert: Dokumentation
Weiß jemand aus den Vorjahren, wo die "Cutoffs" normalerweise liegen?
Ich teile meine Lösung auch mal: https://gitlab.com/vypxl/bwinf39_2
Doku ist auch enthalten.
Aufgabe 2 ist in Python gelöst worden, Aufgabe 3 in Julia.