Mahjong-Solitaire Solver خوارزمية، والتي تحتاج إلى سرعة

Question

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

جميع البلاط معروفة من التخطيطات، ولكن الحل ليس كذلك. في الوقت الحالي، لدي قواعد قليلة تضمن الإزالة الآمنة لأزواج معينة من نفس البلاط (والتي لا يمكن أن تكون عقبة أمام الحل الممكن).

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

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

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

هذا يعمل بشكل جيد على تخطيط يحتوي على، على سبيل المثال، 36 أو 72 بلاط. ولكن عندما يكون هناك المزيد، تصبح هذه الخوارزمية عديمة الفائدة إلى حد كبير بسبب كمية هائلة من المناصب للبحث عنه.

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

مع أطيب التحيات، nhaa123

Answer 1

أنا لا أفهم تماما كيف يعمل الحلال الخاص بك. عندما يكون لديك خيار من التحركات، كيف تقرر أي إمكانية لاستكشاف أولا؟

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

• بحث
• شعاع البحث

(جوجل هو صديقك)

Answer 2

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

http://www.math.ru.nl/~debondtt/mjsolver.html.

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

Answer 3

بدلا من متجه يحتوي على مواقع "سيئة"، استخدم مجموعة تحتوي على وقت بحث مستمر بدلا من خطي خطي.