استراتيجية الفوز في لعبة معينة على الرسوم البيانية

Question

اللعبة تسير على النحو التالي.يلعب لاعبان لعبة، اللاعب 1 واللاعب 2، حيث يبدأ اللاعب الأول بتسمية البطل $h_1$, ، ثم يرد اللاعب 2 بالشرير $v_1$ الذي لعب في فيلم مع $h_1$.ثم يرد اللاعب 1 ببطل آخر $h_2$ الذي لعب في فيلم معًا $v_1$, ، وهكذا دواليك.يمكن استخدام كل بطل وشرير مرة واحدة على الأكثر.اللاعب الأول الذي لا يمكنه تسمية أي شخصية (الأبطال/الأشرار المتوفرون ليس لديهم فيلم مشترك مع الاختيار الأخير للاعب الآخر)، يخسر اللعبة.اللاعب 1 يبدأ اللعبة دائمًا.

الإدخال عبارة عن مجموعة من الأبطال $ح$, ، مجموعة من الأشرار $V$ ($|H| = |V| \geq 1$) وعائلة من الأفلام $م$, حيث كل فيلم عبارة عن مجموعة من الأبطال والأشرار الذين ظهروا في ذلك الفيلم.

السؤال هو:هل تستطيع، على أساس $ح$, $V$ و $م$, هل تقرر أي لاعب يفوز باللعبة بافتراض أن كلا اللاعبين يلعبان على النحو الأمثل؟

---

مثال:

نظرا للبيانات التالية:الأبطال هم رجل حديدي, كابتن أمريكا, ثور و الرجل العنكبوت.الأشرار هم الإصابة, أولترون, ثانوس و نسر.الأفلام هي المنتقمون:حرب اللانهاية (نجوم آيرون مان، كابتن أمريكا، ثور، ثانوس، سبايدر مان) و الرجل العنكبوت:العودة للوطن (نجوم الرجل الحديدي، النسر والرجل العنكبوت).هل يمكنك أن تقرر أي لاعب لديه الإستراتيجية الفائزة؟

---

النهج الذي أتبعه هو استخدام الحد الأقصى من المطابقة الثنائية لمعرفة اللاعب الذي لديه الإستراتيجية الفائزة، لأنه يمكننا تقسيم البيانات إلى مجموعتين، وهما: $ح$ و $V$ ولها علاقات بين هاتين المجموعتين.يمكن لخوارزمية Hopcroft-Karp أن تأخذ مجموعتين من هذه المجموعات وتكتشف الحد الأقصى لعدد العناصر.أرجوا أن تصحح لي إذا كنت مخطئا:في الحالات التي يوجد فيها تطابق مثالي، يفوز اللاعب 2 ويفوز اللاعب 1.عندما يكون هناك مطابقة مثالية، فهذا يعني أن اللاعب 2 كان لديه دائمًا إجابات للبطل الذي ذكره اللاعب 1.

كيف يمكنك حل هذا؟هل هناك حل أفضل وأكثر كفاءة من بعض المطابقة الثنائية القصوى.

Answer 1

الإجابة المختصرة هي أن اللاعب الثاني يفوز فقط إذا كان الرسم البياني المقابل يعترف بمطابقة "تغطي" المجموعة $ح$.

---

وهنا قليلا من التوضيح.

فكرتك تكاد تكون صحيحة.ومع ذلك، فإن الدليل ليس بديهيًا وقد تفوتك بعض التفاصيل التي تحتاجها إذا كان سؤالًا نظريًا أو إذا كنت بحاجة إلى تصميم استراتيجية الفوز الدقيقة وليس فقط إخراج اللاعب الفائز.

فلنبدأ بالجزء المفقود من إجابتك.افترض أن مثيلًا معينًا يتوافق مع رسم بياني يعترف بالمطابقة المثالية.وفقًا لاستراتيجيتك، يفوز اللاعب 2 في هذه الحالة وهذا صحيح.الآن افترض أن نفس المثال تم تقديمه مع شرير آخر، أو عشرة أشرار آخرين، أو ألف منهم.من الواضح أن اللاعب الثاني ما زال يفوز منذ إضافة الأشرار، بغض النظر عن كيفية تعيينهم، فهو يساعد اللاعب الثاني فقط.لذا فإن مطالبتك لا تصمد دائمًا.ومع ذلك، فإن إجابتك قريبة جدًا من ادعائي ولها نفس الحدس.إنه يفتقد فقط القليل من الشكليات.

مطالبة. بافتراض أن كلا اللاعبين يلعبان على النحو الأمثل، يفوز اللاعب 1 إذا وفقط إذا تم إعطاؤه مثالاً $أنا$, ، الرسم البياني المقابل لا يسمح بمطابقة تشبع المجموعة $ح$.

فماذا يعني ذلك؟المطابقة تشبع مجموعة من القمم $س$, ، إذا كان كل قمة في $س$ هو حادث لقمة في المطابقة.الآن نثبت هذا الادعاء.نعرض استراتيجيتين فائزتين واحدة للاعب الثاني عندما يعترف الرسم البياني بمطابقة مجموعة التشبع $ح$ وواحد للاعب الثاني عندما لا يسمح الرسم البياني بمثل هذه المطابقة.

دليل. الآن افترض أن الرسم البياني يسمح بمثل هذه المطابقة.دع هذه المطابقة تكون $م$.الاستراتيجية تسير على النحو التالي.طالما أن اللاعب الأول لم يخسر، لكل اختيار $ح \في H$ بالنسبة للاعب الأول، اختر $v \في V$ قمة الرأس مطابقة ل $ح$ في $م$.

تنبع الصحة مباشرة من حقيقة أن كل قمة للاعب الثاني فريدة ومجاورة لاختيار اللاعب الأول (بسبب خصائص المطابقة).بشكل بديهي، سوف تنفد حركات اللاعب الأول في مرحلة ما (ربما بعد اختيار جميع الأبطال في المجموعة $ح$).

الآن بافتراض أن الرسم البياني لا يعترف بالتشبع المطابق $ح$, وفقا لنظرية هول، هناك مجموعة فرعية $A \subseteq H$, ، مثل ذلك $|غير متوفر | < $.اختر مجموعة ذات الحد الأدنى من التضمين.نحن ندعي أن هناك مطابقة $م'$ أن يشبع $ن(أ)$.بافتراض خلاف ذلك، مرة أخرى بسبب هول، هناك مجموعة فرعية $S \subseteq N(A)$ مثل ذلك $|N(S) | < دولار سنغافوري, ، ولكن بعد ذلك يتم الإزالة $N(S) \cap A$ من $أ$ و $س$ من $ن(أ)$ ينتج مجموعة فرعية من $أ$ وهذا يتناقض أيضًا مع شرط هول الذي يشكل تناقضًا مع اختيار $أ$ ليكون الحد الأدنى.وبالتالي، هناك مطابقة $م'$ أن يشبع $ن(أ)$.

الآن تسير الإستراتيجية على النحو التالي.اختر قمة في $أ$ هذا ليس حادثا على أي حافة في $م$.مثل هذه القمة موجودة منذ ذلك الحين $|غير متوفر | < |أ|$.اختر هذه القمة في البداية ولكل اختيار $v \في V$ من اللاعب الثاني، اختر الرأس $ح \في H$ متطابقة مع $v$ في $م'$.

مرة أخرى، من السهل أن نرى أن اللاعب الثاني سوف ينفد من الحركات في مرحلة ما (ربما بعد اختيار جميع القمم في $ن(أ)$) وبالتالي يفوز اللاعب الأول.