Gewinnende Strategie für ein bestimmtes Spiel in Graphen

Question

Das Spiel geht wie folgt. Zwei Spieler spielen ein Spiel, Spieler 1 und Spieler 2, in dem der erste Spieler beginnt, mit der Benennung eines Helden $ H_1 $ , dann antwortet der Spieler 2 mit einem Bösewicht $ v_1 $ Wer hat in einem Film mit $ H_1 $ gespielt. Dann antwortet der Spieler 1 mit einem anderen Helden $ H_2 $ , der zusammen mit $ v_1 $ , in einem Film gespielt hat, und so weiter. Jeder Held und Bösewicht können höchstens einmal verwendet werden. Der erste Spieler, der keinen Charakter nennen kann (verfügbare Helden / Bösewichte haben keinen gemeinsamen Film mit der letzten Wahl des anderen Spielers), verliert das Spiel. Spieler 1 startet immer das Spiel.

Der Input ist ein Satz von Helden $ H $ , ein Satz von Bösewellen $ V $ ( $ | H |= | V | \ GEQ 1 $ ) und eine familie von films $ m $ , wo jeder Film ein Satz von Helden und Bösewichten ist, die in diesem Film aufgetaucht sind.

Die Frage ist: Kannst du, basierend auf $ H $ , $ v $ und $ M $ , entscheiden Sie, welcher Spieler das Spiel gewinnt, an dem beide Spieler optimal spielen?

---

Beispiel:

Angesichts der folgenden Daten: Die Helden sind eisen mann , captain amerika , thor und spider-mann . Die Bösewichte sind whiplash , ultron , tios und geier . Die Filme sind Avengers: Infinity War (Sterne Eisen Mann, Kapitän Amerika, Thor, Thanos und Spider-Man) und Spider-Man: Homecoming (Sterne Eisen Mann, Geier und Spider Man). Können Sie entscheiden, welcher Spieler die Siegerstrategie hat?

---

Mein Ansatz ist es, maximale Bipartite-Matching zu verwenden, um herauszufinden, welcher Spieler die gewinnende Strategie hat, da wir die Daten in zwei Sätze teilen können, nämlich $ H $ und $ V $ und haben die Beziehungen zwischen diesen beiden Sätzen. Der Hopcroft-Karp-Algorithmus kann zwei solcher Sätze nehmen und die maximale Kardinalität herausfinden. Bitte korrigieren Sie mich, wenn ich falsch liege: In den Fällen, in denen ein perfekter Anpassung ist, gewinnt Spieler 2 und ansonsten Spieler 1. Wann immer es ein perfektes Matching gibt, bedeutet dies, dass Spieler 2 immer Antworten auf den Helden hatte, den Spieler 1 benannt hat.

Wie würden Sie das lösen? Gibt es eine bessere, effizientere Lösung als ein maximales Bipartite-Matching.

Answer 1

Die kurze Antwort ist, der Spieler zwei gewinnt, wenn und nur, wenn das entsprechende Diagramm eine Anpassung zulässt, die "deckt" der Set $ H $ abdeckt.

---

hier ist ein bisschen erläuterung.

Ihre Idee ist fast richtig. Der Beweis ist jedoch nicht intuitiv, und Sie könnten einige Details verpassen, die Sie benötigen, wenn es sich um theoretische Frage handelt, oder wenn Sie die genaue Gewinnstrategie entwerfen müssen, und nicht nur den Gewinnspieler ausgeben.

Lassen Sie uns also mit dem von Ihrer Antwort fehlenden Teil beginnen. Angenommen, eine gegebene Instanz entspricht einem Diagramm, das eine perfekte Übereinstimmung zulässt. Laut Ihrer Strategie gewinnt der Spieler 2 in diesem Fall, der richtig ist. Nehmen Sie nun anzunehmen, dass dieselbe Instanz mit einem weiteren Bösewicht oder zehn weitere Bösewichte oder eintausend von ihnen vergeben wird. Seit eindeutig gewinnt der Spieler zwei immer noch, da die Bösewichte hinzugefügt werden, unabhängig davon, wie wir ihnen zuweisen, hilft nur dem zweiten Spieler. Ihr Anspruch hält also nicht immer. Ihre Antwort ist jedoch sehr nahe an meinem Anspruch und haben die gleiche Intuition. Es fehlt nur ein bisschen Formalität.

behaupten. Angenommen, beide Spieler spielen optimal, Spieler 1 gewinnt falls und nur, wenn gegeben, wenn ein Instanz $ i $ , das entsprechende Diagramm ist nicht zugegeben, dass ein passendes Sättigen der Set $ H $

was bedeutet das? Eine Übereinstimmung sättigt einen Satz von Scheitelpunkten $ s $ , wenn jeder Scheitelpunkt in $ S $ auf a Scheitelpunkt im Matching. Jetzt beweisen wir den Anspruch. Wir zeigen zwei gewinnende Strategien eins für Spieler zwei, wenn das Diagramm eine Übereinstimmung mit der Sinne der Sättigungen der Set $ H $ zulässt, und eins für Spieler zwei, wenn die Grafik ein solches Übereinstimmungen nicht zugeben kann .

Beweis. Nehmen Sie nun an, dass das Graph eine solche Übereinstimmung zulässt. Lassen Sie diese Übereinstimmungen $ M $ . Die Strategie läuft wie folgt. Solange der Spieler nicht verloren hat, wählen Sie für jede Wahl $ H \ in H $ für Spieler eins, wählen Sie $ v \ In V $ der Vertex, der auf $ H $ in $ M $ abgestimmt ist. .

Die Richtigkeit folgt direkt von der Tatsache, dass jeder Scheitelpunkt von Spieler zweizig einzigartig ist und an die Wahl des Spielers eins (aufgrund der Eigenschaften eines Anpassungen) ist. Intuitiv läuft der Spieler, dass der Spieler irgendwann aus Moves rennt (möglicherweise nach der Auswahl aller Helden im Set $ H $ ).

Angenommen, das Diagramm gibt keinen passenden Sättigungs-Saturating $ H $ , je nach Hallen-Satzung, gibt es eine Subset $ A \ subseteq H $ , so dass $ | n (a) | . Wählen Sie ein solches Set, das minimal inklusive ist. Wir behaupten, dass es einen passenden $ M '$ gibt, der $ n (a) $ ist. Ansonsten an der Ansonsten, wiederum aufgrund der Halle, gibt es eine Subset $ s \ Subseteq n (a) $ so, dass $ | n (S) | , aber dann entfernen $ n (s) \ cap a $ von $ A $ und $ s $ von $ n (a) $ ergibt eine Teilmenge von $ A $ , der auch den Zustand des Hallens widerspricht, der einen Widerspruch zur Wahl der Wahl des $ A $ minimal bildet. Daher gibt es einen passenden $ M '$ das sättigt $ n (a) $ . .

Nun geht die Strategie wie folgt. Wählen Sie einen Scheitelpunkt in $ A $ , das nicht auf eine beliebige Kante in $ M $ ist. Ein solcher Scheitelpunkt gibt es seit $ | n (a) | <| A | $ . Wählen Sie zuerst diesen Scheitelpunkt aus und für jede Wahl $ v \ in V $ von Spieler zwei, wählen Sie den Scheitelpunkt $ h \ in H $ Abgestimmt auf $ V $ in $ M '$ .

Wieder ist es einfach zu sehen, dass der Spieler zwei irgendwann aus den Moves ausgeführt wird (möglicherweise nach der Auswahl aller Scheitelpunkte in $ n (a) $ ) und Daher gewinnt der Spieler eins.