العثور على مسار هاميلتونيش في الرسم البياني

Question

بيان المشكلة

نظرا رسم بياني لجميع المربعات الزرقاء في الصورة التالية حيث يتم توصيل كل ساحة زرقاء بالساحات الزرقاء الأخرى في جميع الاتجاهات الكاردينية الأربعة.

تعطى أي عقدة البدء.

ما الخوارزمية التي ستسمح بإيجاد أطول طريق (ISH).

بالنظر إلى أن كل عقدة لا يمكن زيارتها مرة واحدة فقط.

بالنظر إلى أننا لا نهتم أين ينتهي المسار.

بالنظر إلى أن السرعة أكثر أهمية من الزيارة بالضرورة كل عقدة.

مثال

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

href="https://i.stack.imgur.com/yi4dt.png" er="nofollow noreferrer">

Answer 1

انتهى بي الأمر باستخدام UCT (MCTS مع UCB1) خوارزمية ولكن مع تطور.

عادة، في UCT، مرحلة المحاكاة هي لعبة محاكاة من خلال لعبة مع التحركات المختارة بشكل عشوائي. إذا انتهت اللعبة المحاكاة في فوز، فإن درجة العقدة، من حيث تم تشغيل المحاكاة، ويزيد كل درجات الوالدين طوال الطريق إلى الجذر، بزيادة 1.

في تطبيقي، فإن "اللعب" المحاكاة "هو في الواقع مجرد نزهة عشوائية أسفل شجرة البلاط المجاورة التي لم تتم زيارتها بعد. بمجرد أن تصل المحاكاة إلى عقدة الطرفية (الميت)، فإنه يعين درجة من S= D / M حيث D هو عمق العقدة الطرفية في الشجرة و M الأقصى عمق ممكن.

على شبكة 15 × 15 مع عدم وجود عقبات، كنت ستضع م إلى 225 حيث أن أطول مسار سيزور كل بلاط. لقد وضعت الألغام أقل قليلا مما أحتاج إلى أن تكون خوارزمية تعميم وتعميمها على الخرائط التي تم إنشاؤها عشوائيا والتي تحتوي عادة على 10-30 بلاط تشغلها العقبات.

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

يستخدم UCT UCB1 من أجل تحديد العقدة التي استغلالها أو استكشافها بمجرد توسيع كل طفل من العقدة الحالية وقد أبقى إلى حد كبير مع ذلك. التعديل الوحيد الذي قدمته هو مصطلح الاستغلال. في UCB1، فإن مصطلح الاستغلال هو W / V حيث W هي النتيجة المتراكمة للعقدة و V هي عدد الوقت الذي تمت زيارة العقدة. يعمل هذا بشكل رائع في لعبة حيث تريد تحديد الخطوة التي تزيد من فرصك في الفوز. في حالتي، نظرا لأن النتيجة تعكس وظيفة ثنائية للفوز= 1 وتفقد= 0 ولكن بمقياس 0= مسار قصير للغاية مقابل 1= أطول مسار ممكن وأريد أن أذهب إلى أطول مسار موجود من خلال الخوارزمية ، لقد قمت ببساطة بتعيين مصطلح الاستغلال إلى S= درجة= أطول مسار يمكن الوصول إليه من هذه العقدة.

السياق الذي أستخدمه في هذه الخوارزمية يسمح لي بحوالي 40 مللي ثانية من الوقت في بيئة Nodejs قبل أن أتحقق لتحديد خطوة. هذا عادة ما يتيح حوالي 785 اجتيازات شجرة على جهازي. في المتوسط، في ذلك الوقت، وعلى الخريطة، أظهرت هذه الخوارزمية أن هذه الخوارزمية ستجد مسارا هو 70 عقدا عميقا. وهو أكثر من ما يكفي لأغراض الرؤية حيث أن أتعرض لتشغيل الخوارزمية مرة أخرى المنعطف التالي. في الممارسة العملية، عند استخدام هذه الخوارزمية لتحديد التحركات التالية، انتهى الأمر بالسفر المسار الذي يبلغ طوله 100-110 خطوات طويلة قبل أن يضرب ميتا وغطيا جزءا كبيرا جدا من البلاط الأزرق.

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

Answer 2

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