Ratespiel

Ich habe diese Frage gelöst . Es ist wie folgt

Joe wählt eine ganze Zahl aus der Liste $1,2,\cdots,N$ mit einer Wahrscheinlichkeit $p_i$ zu pflücken $i$ für alle $1\leq i \leq N$. Dann gibt er Jason$K$versucht seine Nummer zu erraten. Bei jeder Vermutung wird Joe Jason mitteilen, ob seine Zahl höher oder niedriger als Jasons Vermutung ist. Wenn Jason Joes Nummer auf einer der beiden richtig errät$K$Vermutlich endet das Spiel und Jason gewinnt. Jason verliert anders. Wenn Jason alles weiß$p_i's$ und spielt optimal, wie hoch ist die Wahrscheinlichkeit, dass er gewinnt?
$1\leq N\leq 200000$
$1\leq K\leq 20$

Ich habe dieses Problem durch dynamische Programmierung versucht. Lassen$DP[i][j][k]$ speichert die Gewinnwahrscheinlichkeit so, dass die Zahl zwischen liegt $i$ und $j$ inklusive und nur $k$Chancen bleiben. Damit

$$DP[i][j][k] = \max_{i\leq l\leq j} \{p_l + DP[i][l-1][k-1] + DP[l+1][j][k-1]\}\\DP[i][j][1] = \max_{i\leq l\leq j}p_l\ \quad \quad \text{Base Case}$$ Da der Bereich von $N$ jedoch sehr hoch ist, ist diese Lösung nicht durchführbar. Während ich nach einer $\mathcal{O}(n)$ -Lösung suchte, stieß ich auf die folgende Lösung (im Internet, die akzeptiert wurde)

• Sortieren ( $p[]$ )
• $\sum_{i=0}^{\min(n,2^k-1)}p_i$

Wenn wir beide Lösungen am Eingang $N=5,K=2, p=[0.2, 0.3, 0.4, 0.1, 0.0]$ ausführen, erhalten wir die gleiche Antwort. Meine Frage ist also, wie der obige Algorithmus funktioniert und ob wir ausgehend von meiner dp-Formulierung zu derselben Schlussfolgerung gelangen können (wenn sie korrekt ist).

Der Grund, warum die Sortierlösung funktioniert, ist, dass Sie mit jeder deterministischen Strategie höchstens Werte erraten können , wenn Sie Vermutungen erhalten. Dies kann durch Induktion bewiesen werden, indem zuerst der Basisfall und dann für notiert wird. Nachdem Sie den ersten Wert erraten haben, haben Sie Vermutungen übrig und Sie raten entweder links oder rechts von Ihrer ursprünglichen Vermutung, je nachdem über das Ergebnis der ursprünglichen Vermutung, also durch Induktion, die Werte ergibt, können Sie nach der ersten erraten. Wenn Sie also die ursprüngliche Vermutung hinzufügen, erhalten Sie .$K$$2^K - 1$$K = 1$$K + 1$$K$$2(2^K - 1)$$2^{K+1} - 1$

Wenn einer dieser Werte der richtige Wert ist, wird er erraten und Sie werden gewinnen. Keiner der anderen Werte wird jemals erraten. Die Wahrscheinlichkeit, dass Sie gewinnen, ist also die Summe der Wahrscheinlichkeiten für die Werte, die Ihre deterministische Strategie erraten kann. Offensichtlich besteht die optimale Lösung darin, die obersten Wahrscheinlichkeiten zu nehmen.$2^K - 1$$N - 2^K + 1$$2^K - 1$$2^K - 1$

Nach ein paar Monaten ist mein Kopf klarer geworden und es scheint ziemlich leicht zu sehen, wie das funktioniert.

Wenn Sie eine Vermutung haben, wählen Sie die mit der höchsten Wahrscheinlichkeit.

Wenn Sie 2 Vermutungen haben, wählen Sie die 3 mit der höchsten Wahrscheinlichkeit aus. Die erste Vermutung, Sie wählen die zweite unter den drei. Bei der zweiten Auswahl werden Sie zu einer von zwei Seiten der ersten Auswahl geleitet. Jede Seite führt zum Fall von 1 Vermutung, und auf jeder Seite befinden sich bereits die obersten 2 Prob in jeder. Das ist optimal. Prob of Winning ist die Summe der 3 Prob.

..

Das klare Muster ist also, dass Sie, wenn Sie Vermutungen haben, die besten mit den höchsten Wahrscheinlichkeiten auswählen . Die erste Auswahl befindet sich in der Mitte der oberen . Danach rekursieren Sie zu beiden Seiten des mittleren. Auf beiden Seiten haben Sie die oberen Wahrscheinlichkeiten, die sich dort befinden, weil Sie den mittleren Drehpunkt auswählen und den nehmen top .$k$$2^k - 1$$2^k - 1$$\frac{(2^k - 1) -1}{2} = 2^{k-1} - 1$$2^k - 1$

Dies gibt die Gewinnwahrscheinlichkeit als die Summe der besten Wahrscheinlichkeiten an.$2^k - 1$