Wie kann ich Herausforderungen mit variablen Problemgrößen erzielen?

21

Meta unterstützt ziemlich stark das Verfassen von Fragen zum Thema Hauptthema, vorausgesetzt, diese Fragen sind spezifisch und beantwortbar. Wir haben jedoch noch keine solchen Fragen, also dachte ich, ich würde das Wasser testen. Diese Frage betritt wahrscheinlich ein gutes subjektives, ein schlechtes subjektives Gebiet, aber ich denke, das ist wahrscheinlich, was herausfordernde Fragen sein müssen. Um sicherzustellen, dass sie weiterhin qualitativ hochwertige Inhalte generieren, posten Sie bitte nicht nur wilde spekulative Ideen in den Antworten. Erklären Sie, warum sie die unten genannten Probleme vermeiden, oder weisen Sie im Idealfall auf bestehende Herausforderungen hin, bei denen die vorgeschlagene Technik in der Vergangenheit erfolgreich eingesetzt wurde.

Bei bestimmten Optimierungsherausforderungen ist ein freier Parameter beim Festlegen der Herausforderung die Größe des zu optimierenden Problems. Mit "Optimierungsherausforderung" meine ich nicht Dinge wie unser Genre mit dem , in dem Antworten normalerweise exakt / optimal sein müssen, und die Herausforderung wird entweder nach einer festen Problemgröße oder nach der größten Problemgröße bewertet, die behandelt werden kann in einer festen Zeitspanne. Ich meine speziell Herausforderungen, bei denen suboptimale Lösungen für das zugrunde liegende Problem zulässig und sogar wahrscheinlich sind und das Ziel darin besteht, möglichst gute Ergebnisse zu erzielen.

Betrachten Sie der Bestimmtheit halber beschäftigte Biberherausforderungen , obwohl dies im Prinzip auch für andere Herausforderungstypen ohne bekannte optimale Lösungen gilt (ich verwende hier nur beschäftigte Biber, weil sie die unten genannten Probleme verschlimmern). Sagen wir, ich wollte mich der Herausforderung stellen, den fleißigsten Brainfuck-Biber zu finden. Der freie Parameter bei beschäftigten Biberproblemen ist die Größe des Codes. Ich kann die Herausforderung nicht stellen, ohne in irgendeiner Weise auf die Codegröße Bezug zu nehmen. In gewisser Weise stellt jeder Wert des Problemgrößenparameters Neine separate (zunehmend schwierige) Herausforderung dar. Meine Hauptfrage ist, wie ich eine solche Herausforderung bewältigen kann, ohne auf Probleme mit dem Gleichgewicht zu stoßen.

Die naheliegende Lösung besteht darin, Folgendes zu beheben N: "Suchen Sie ein abschließendes Brainfuck-Programm mit NQuellcode-Bytes, das so viele Zeichen wie möglich druckt / so viele Ticks wie möglich ausführt." Dies hat massive Balancing Probleme: wenn ich die Größe zu klein wählen, jemanden schnell finden könnte diebeschäftigtste Biber und die Herausforderung ist vorbei. Wenn ich die Größe zu groß wähle, druckt die optimale Lösung vor dem Beenden eine astronomische Menge von Zeichen aus, was bedeutet, dass es wahrscheinlich trivial ist, solche Programme zu finden, und die Herausforderung wird zu einer mühsamen Aufgabe / Übung in Geduld - dies verlässt auch das Gebiet, in dem Vielbeschäftigte Biber können programmgesteuert gefunden werden, und stattdessen müssten die Leute damit beginnen, ihre Ergebnisse formal zu beweisen, was viele Leute vielleicht nicht für sehr lustig halten. Natürlich ist dieses Problem bei geschäftigen Biberherausforderungen aufgrund des Wachstums der optimalen Lösungen stärker ausgeprägt als bei anderen Arten, aber es gilt trotzdem für andere Herausforderungen.

Die nächste Option wäre, keine NEinschränkungen zu machen und sie über eine Funktion in die Wertung einzubeziehen. Sogar für "normale" Herausforderungen ist es unglaublich schwierig, die Balance der kombinierten Punktzahlen zu finden, aber im Falle vielbeschäftigter Biber ist dies im Grunde unmöglich, da optimale Lösungen schneller wachsen Nals jede berechenbare Funktion. Das heißt, ich kann immer die beste vorhandene Antwort schlagen, indem ich zu einem ausreichend großen NProgramm gehe, in dem ich leicht ein Programm finden kann, das so lange läuft, dass ich ohne großen Aufwand eine bessere Punktzahl erzielen kann.

Ich habe auch darüber nachgedacht, einen Fix festzulegen Nund es Leuten zu ermöglichen, auch Biber für größere einzureichen N, die als aufeinanderfolgende Krawattenbrecher verwendet werden. Dies hat insofern ein ähnliches Problem, als jemand "zufällig einen ebenso gut beschäftigten Biber" für einen findet N, wodurch er ein Unentschieden schafft und dann so ziemlich alles für den nächsten Nabgibt, bei dem es einfacher ist, eine große Punktzahl zu finden (auch wenn das Auffinden der Biber) optimale Punktzahl wird schwieriger). Wie würden Sie in diesen Fällen mit mehreren Personen umgehen, die dieselbe Lösung verwenden? Es zu verbieten wäre auch komisch, wenn es optimal wäre.

Vielleicht könnte man einen Mittelweg einschlagen, indem man eine begründete Vermutung anstellt Nund dann nach beschäftigten Bibern für alle Größen innerhalb von (sagen wir) 5 Bytes fragt N, so dass in beide Richtungen ein gewisser Spielraum besteht (und man dann die ~ 10 Punkte kombiniert in eine einzelne nach der einen oder anderen Technik). Dies ist auch nicht ganz zufriedenstellend, da meine anfängliche Einschätzung für Nimmer noch weit außerhalb des Bereichs liegen könnte, der für interessante Herausforderungen sorgt.

TL; DR: In Fällen, in denen die Herausforderung darin besteht, ein Problem mit variabler Größe (suboptimal) zu lösen und zu optimieren, wie kann ich die Größe in die Herausforderung einbeziehen? Idealerweise möchte ich, dass die Leute mit einem Wert arbeiten können, der Nnahe am oberen Ende des Bereichs der handhabbaren Größen liegt. Aber für den Fall, dass sich herausstellt, dass dafür optimale Lösungen möglich sind N, wäre es großartig, wenn Lösungen für etwas größere NProbleme anfangen würden, so dass die Herausforderung mit einer interessanteren Problemgröße fortgesetzt werden könnte.

Martin Ender
quelle
6
Ich mag dies als Modell für das Verfassen von Fragen, da es nicht spezifisch für PPCG ist. Es ist nicht "Wie sollen wir das machen?" aber "Was ist ein guter Weg, um dies zu tun?". Ich könnte mir vorstellen, dass solche Herausforderungen auf einer Website für Programmierer oder bei einem persönlichen Wettbewerb durchgeführt werden.
Xnor
Setzen Sie den Tldr an der Spitze!
Majora320
1
@ Majora320 ... aber dann ändern Sie d zu w :-)
Luis Mendo

Antworten:

3

Finde die nächste N

Die Herausforderung würde anzeigen, Ndass die Einsendungen bei beginnen sollten.

Dann würden die Leute aktuell Antworten einreichen N. Wenn sich eine bestimmte Übermittlung als optimal herausstellt, Nwird sie um 1 erhöht und der Vorgang wiederholt.

Es gibt verschiedene Möglichkeiten, dies zu bewerten:

  1. Erziele die beste Einreichung zum aktuellen Zeitpunkt N
  2. Geben Sie einen Punkt für die beste Einreichung zum aktuellen NZeitpunkt sowie einen Punkt für jede optimale Lösung
  3. Wie Nummer 2, aber geben Sie der Person einen Punkt, die bewiesen hat, dass eine bestimmte Vorlage optimal war.
Nathan Merrill
quelle
1

Geben Sie Punkte für Lösungen innerhalb eines begrenzten N an

Erlaube Nes, innerhalb fester Grenzen zu sein. Die Untergrenze sollte offensichtlich triviale Antworten ausschließen und die Obergrenze sollte nicht zu weit von der Untergrenze entfernt sein.

Geben Sie dann 1 Punkt für jede Person, die Ninnerhalb der Grenzen die beste Lösung für jede Person hat . Wenn höher Nbedeutet, dass die Lösung schwieriger ist, geben Sie ihnen N Punkte. (oder eine Formel basierend auf N).

Diese Methode ähnelt der von AZsPCs , es werden jedoch keine Teilpunkte angegeben.

Nathan Merrill
quelle