خوارزمية وهيكل بيانات لحل اللعبة "كرات"/تعبئة الفيضان/"الفيضان"

Question

اقترح خوارزمية وهيكل بيانات لحل كرات اللعبة (http://www.deadwhale.com/play.php؟game=131). إنه أمر ممتع للغاية في نوع من الطريق العبقري غريب الأطوار.

اذكر تعقيد الفضاء الزمني (Big-O) لنهجك من حيث N., ، حجم الشبكة (n> = 14). تفضل خوارزميات جيدة الكفاءة ذات التعقيد المنخفض.

(تشير MatrixFrog بشكل صحيح إلى أن هذه اللعبة تُعرف أيضًا باسم Floodit ، وقد أعطى الحافز حلاً قبل 3 أشهر في الرابط الذي يستشهد به أدناه. كل ما يقترحونه التقليم/الجشع مع Lookahead واحد فقط ، والذي يعطي حلولًا دون المستوى الأمثل.)

تقوم اللعبة بإنشاء شبكة مربعة عشوائية من العقد NXN ، حيث يتم تلوين كل عقدة واحدة من ستة ألوان (GRN = 1 ، ylw = 2 ، أحمر = 3 ، Blu = 4 ، pur = 5 ، orn = 6). يحتوي المستوى 1 على شبكة 9 × 9 ، ثم يزيد N من كل مستوى ، حتى 14. كل مستوى يمكنك أن تأخذ ما يصل إلى 25 منعطفًا وإلا فإنك تخسر. في كل منعطف ، تختار أي لون لتغيير العقدة اليسرى العلوية إلى EG GRN-> باللون الأحمر ، بحيث يتم استيعاب أي عقد متصلة (الأفق/فير) من اللون الجديد في شكل ، ويتم إضافة 1 نقطة لكل عقدة تم استيعابها درجاتك. الهدف من التسجيل هو إكمال كل شبكة في أقل عدد ممكن من المنعطفات ، على سبيل المثال ، إذا قمت بذلك في 16 منعطفًا ، فإن تحركاتك 9 غير المستخدمة => 2*9 أوقات مضاعفة إجمالي درجاتك المتراكمة.

من الواضح أن هناك الكثير من الطرق لتحليل هذا ، والاختيار الافتراضي للتركيب العودية مع شبكة 14 × 14 هو منافس قابل للحياة ؛ ما هي الأنواع الأخرى من هياكل البيانات التي يفسحتها هذا؟ أ* ؟ لا تتعلق بالحساب ، فأنا أتساءل عما إذا كانت هناك خوارزمية "جيدة كافية".

(اعتقدت أنه قد يكون مشروعًا ممتعًا لترويج روبوت والحصول على درجات عالية عالية. على الرغم من أنني سجلت 3.5e+12 جميعًا من قبل نفسي.)

Answer 1

أمسك هذه اللعبة اهتماماتي حقًا ، لذلك قضيت بضعة أيام في العمل عليها.

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

عند الحديث عن*، فإن فعالية ذلك تتلخص حقًا في اختيارك لتقدير الإرشادات. كلما اقتربت من تخمين المسافة الفعلية ، أقل العقد التي يجب توسيعها من أجل الوصول إلى الهدف. بالنسبة لهذه المشكلة ، مررت بعدد من الأفكار لتقديرها ، لكن معظمها كسر قاعدة A* ، وهو أنه لا يمكنك تقدير المسافة الفعلية ، وإلا فإنك تكسر الأمثل A*.

هناك عدد قليل من العمل ولكن. لقد نشر آخرون في هذا الموضوع فقط عن أخذ عدد الألوان المتبقية كتقدير ، وهو أمر مقبول لأنه لا يمكن أن يكون أكثر من التقدير (يجب عليك تغيير الألوان مرة واحدة على الأقل لكل لون متبقي وليس جزءًا من منطقة "الفيضان" الرئيسية. المشكلة مع هذا الاستدلال هي أنها تقدر بشكل سيء للغاية المسافة الفعلية. خذ على سبيل المثال الخطوة الأولى ، والتي لديها عمومًا تقدير لعدد الألوان ، 6. غالبًا ما يتوسع إلى حركتين ، كل منها لديه تقدير 7 عمومًا وما إلى ذلك. الهدف. هذا ليس فعالًا للغاية وفي اختباراتي الخاصة ، يدير الأسسون الكثير حول حجم اللوحة 9 ، والذي يتطلب في كثير من الأحيان حوالي 14 حركة في الحل. تجدر الإشارة لتسريع رقيقة GS UP.

المشكلة هي أن A* جيدة حقًا عندما تقوم كل خطوة بتحسين كبير للمسافة الفعلية للحل الكلي. بالنظر إلى المشكلة مباشرة ، ربما لن تجد مجردة جيدة يمكن أن تفعل أفضل بكثير من هذا دون تقدير التكلفة. ومع ذلك ، إذا قمت بتحويل المشكلة إلى مشكلة أخرى ، فإن أفضل الاستدلال تقفز عليك. "عدد الألوان المتبقية" الإجابة على السؤال ، ما هو أصغر عدد من التحركات الممكنة المتبقية. للإجابة على هذا السؤال ، سألت نفسي "أي بقعة على السبورة تتطلب الحد الأقصى لعدد الخطوات للوصول إلى"؟ انتهى بي الأمر إلى الاستقرار على الإجابة على "عدد الخطوات التي توصلت إليها في الركن الأيمن السفلي" لأجري التجريبي. هذا سهل التنفيذ إلى حد ما عن طريق تشغيل بحث آخر* يشبه العثور على اتجاهات الخريطة ثم حساب عدد الخطوات في الحل. أدرك أن هذه نقطة تعسفية على السبورة للاختيار ، ومع ذلك فقد نجحت بشكل جيد في اختبار وتشغيل* في كل نقطة متبقية استغرق وقتًا لا بأس به على جهاز اختبار المعالج الواحد الخاص بي.

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

سأترك إعداد السجل لك.

Answer 2

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

جربت هذا على لوحات 10x10 في Mathematica ، مع خوارزمية غير محسنة للغاية ، وحصلت على حل قصير بسرعة. لا أدعي أنه مثالي ، ولكن بالنظر إلى الوقت الكافي ، فإن العشوائية في عملية تحوير الجينات ستضمن أن ينتهي بك الأمر في النهاية بحل الأمثل.

Answer 3

بالنظر إلى حالة البداية الثابتة وعدد محدود من التحركات ، أعتقد أنه يمكنك استكشاف شجرة القرار بالكامل. لكل جولة ، لا يوجد سوى 5 تحركات محتملة وحركات ضائعة (اختيار لون لن "كرم" أي جيران على الإطلاق) يمكن القضاء عليه عند بناء الشجرة. بمجرد بناء شجرة القرار ، أعتقد أنه يمكنك استكشاف قيمة نقطة كل مسار ، ولكن إذا كنت بحاجة إلى مزيد من التحسين ، فمن المؤكد أن A* سيقترب.

لكل جولة ، سيكون لدي الحالة الأساسية كمصفوفة من صفائف البتات لحالة المواقع غير المليئة بالملل (نظرًا لأن اللون لم يعد مهمًا في مواقع Globbed ، يمكنك حفظ الذاكرة على بنية بيانات الولاية عن طريق ترك البتات الملونة) وقيمة نقطة لكل قرار ممكن. ثم يمكن لخوارزمية A*، أو العرض الأول أن تزيد من قيم المسار إلى الحد الأقصى. احفظ المسار ، وبمجرد اكتمال تحليلك ، قم بإجراء جميع التحركات المحددة.

Answer 4

سيجد البحث العودية في القوة الغاشمة الحد الأقصى للنتيجة. لديك على الأكثر 5^25 دولة تنتهي للنظر فيها. العديد من الدول الوسيطة ستكون مكافئة ؛ قد يكون من الأسرع التعرف على هذه الفضاء والتقليم مساحة البحث للتكرارات. تتبع أعلى الدرجات التي تم العثور عليها بقدر ما تبحث ، جنبا إلى جنب مع المسار (تسلسل التحركات) التي استغرق الأمر للوصول إلى هناك.

Answer 5

1. إذا استطعت ، القضاء على اللون.
2. اختر اللون الذي يولد المزيد من الجيران الجديد لك!
3. Goto الخطوة 1.

Answer 6

مجريات الأمور الجيدة هي توليد خريطة المسافة المتصلة بالألوان. على سبيل المثال ، الفيضان الحالي على مسافة صفر. مجموعة من الألوان المتصلة بمربع على مسافة "أنا" على مسافة "I+1".

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

هذا يوفر تقدير جيد إلى حد ما. في وضع لوحة 14 × 14 الأولي ، أميل إلى الحصول على تقديرات من 17 إلى 18 بينما كنت بحاجة إلى 20 إلى 22 حركة لحل الأمثل. يمكن عادةً حل لوحة 14 × 14 ، مع هذا الحد الأدنى ، مع النظر في حوالي 10000 وظيفة لوح. (باستخدام تحسين إجراء خطوة تلغي اللون إذا كانت هذه الخطوة متوفرة.)

Answer 7

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

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