لمسألة ويرث وسلاسل

الخوارزميات + هياكل البيانات = البرامج - Virt N.

"كانت لدينا فرصة رائعة لإجراء تمرين تكتيكي صغير ولكنه مفيد للغاية"

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

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

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

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

بالنسبة لبعض H ، تكون الإجابة واضحة - مع كائن واحد ، يفوز الأول بألعاب مباشرة في دورة واحدة ويفقد أيضًا لعبة معكوسة واحدة (P1 = 1 ، I1 = -1). مع وجود شيئين ، يخسر اللاعب الأول في حركتين في لعبة مباشرة ويفوز في حركتين معكوستين (P2 = -2 ، I2 = 2) ، مما يمكن أن يؤدي إلى فرضية حول بساطة تقييم هذه اللعبة ، والتي يتم تأكيدها في حالة ثلاثة أشياء (P2 = 3 ، I3 = -3). لحسن الحظ (وإلا لما تم نشر هذا المنشور) لعبة بأربعة أشياء تغير الصورة إلى حد ما (P4 = -4 ، لكن I4 = -3) ، لذا فإن البحث عن اللعبة مطلوب حقًا.

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

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

هذا يعني أنه يجب علينا بناء شجرة لعبة كاملة ، ولكن قبل الشروع في البناء ، يجب علينا إنشاء نموذج للكائن قيد الدراسة ، في حالتنا ، اللعبة.

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

ولكن أولاً ، القليل من الرياضيات لتقييم مدى تعقيد المهمة - نحتاج إلى فرز جميع التحركات المحتملة في اللعبة (الانتباه ليس كل المواقف الممكنة ، هذا هو موضوع طريقة أخرى ، وهي التحركات) ونود تقييم الكمية المطلوبة من الموارد قبل بدء العمل - لتحديد ترتيب المهمة. في الخطوة الأولى ، لدينا الفرصة لإزالة أي شريحة (سأستمر في استدعاء الكائنات) من H المتاحة ، في الخطوة التالية - أي من الرقائق المتبقية H-1 أو اثنين من الرقائق في مكان قريب (لن يكون هناك أكثر من أزواج مثل H-2) ، والتي يعطي العدد الإجمالي للخيارات Hx (H-1 + H-2). من السهل أن نرى أنه بعد الخطوة الثالثة لدينا Hx (H-1 + H-2) x (H-2 + H-3 + Δ) وما إلى ذلك.

إذا قصرنا أنفسنا في كل قوس على الحدود الأولى فقط للمجموع ، فإننا نحصل على تقدير لإجمالي عدد التحركات كـ H! ، مما يعطينا تقديرًا في تربيعات H ^ H.

هذه نتيجة مزعجة للغاية ، والتي تدعي أننا سنواجه مشاكل كبيرة جدًا مع H الكبير ، بحيث أن النمذجة "المباشرة" على الأرجح ستترتب عليها تكاليف حسابية كبيرة. على سبيل المثال ، بالنسبة إلى 16 شريحة في وضع البداية ، سنحتاج إلى التفكير في حوالي 16! = 1013 حركة ، وإذا كانت خطوة واحدة هي 10E-9 ثوانٍ (تقدير متفائل جدًا) ، فإن الوقت الإجمالي سيكون حوالي 10E4 ثوانٍ أو ما يقرب من 3 ساعات ، وهو ما يزيد كثيرًا ، ولكن مقبول ، ولكن مقابل 20 شريحة فقط ، فإن وقت الحساب المتوقع هو 77 عامًا ، وهو أمر غير مقبول بشكل واضح. إن Factorial ينمو بسرعة كبيرة ولا يوجد شيء يمكن القيام به حيال ذلك.

نلفت الانتباه إلى حقيقة أن عدد الحركات يتجاوز بشكل كبير عدد المواضع المحتملة ، وهو 2 ^ N فقط ، ومن الواضح أننا سنقع في موضع منفصل لـ 16 رقائق 10E (13-5) = 10E7 مرات ، وهو أمر يحدث يوميًا مهام البحث. تذكر هذه الحقيقة ، ستكون مفيدة لنا لاحقًا.

ومع ذلك ، سنبدأ في كتابة برنامج سنحدد النموذج من أجله. أولاً ، نقوم بترقيم الرقائق من 1 إلى H ، ثم نقوم بإنشاء مصفوفة بعدد العناصر H ، ونحدد أن الرقم 1 في عنصر الصفيف مع الفهرس n يعني وجود رقم الشريحة n ، والرقم 0 - غيابه في موضع معين. مثل هذا النموذج مناسب وبسيط وبديهي ، ويتيح لك جعل عمليات إزالة الرقائق فعالة ، وكذلك تحديد حالة "القرب".

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

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

1. يتغير التقييم المحايد إلى تقييم جديد ،
2. يتغير التصنيف الإيجابي إلى تصنيف إيجابي أصغر ،
3. يتغير التقييم السلبي إلى سلبي أو إيجابي كبير.

بعد أن مررنا تمامًا بجميع التحركات ، أصبح تقييم الموقف الأولي نهائيًا.

نضيف تقديرات لإجراءاتنا لتوليد جميع المواقف ويمكننا الإعجاب بنتائج التحليل ، التي يتم عرضها في الجدول ، إضافة عداد التقدم وعداد الوقت للتحليل. في مترجم gcc (في وضع التحسين -O2) على جهاز مزود بمعالج ، حصلت على جدول يؤكد تمامًا افتراضاتنا الأولية حول الترتيب العام لتعقيد المهمة. من نفس الجدول ، نرى أنني توقفت عن توقع النتائج مع H يتجاوز 11 ، لأن وقت الحساب أصبح غير مقبول (بالنسبة لي ، ربما أنت مستعد للانتظار نصف ساعة) وافتراضنا حول الدورة والثانية لا تتوافق مع الواقع (متوسط ​​الوقت النظر في الموقف هو 100 ثانية). السؤال الذي يطرح نفسه - ماذا يجب أن نفعل إذا أردنا الحصول على تقدير لأكثر من 11 رقائق في الوضع الأولي.

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

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

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

دعونا ننتبه إلى حقيقة أن بنية البيانات التي اعتمدناها تجعل الرقائق فريدة من نوعها ، على سبيل المثال ، رقاقة واحدة (ليس لها جوار) في الموضع لا تعادل شريحة واحدة في الموضع n + 2 ، وهو خطأ تمامًا. نختار العنصر الرئيسي لموضع اللعبة - مجموعة الرقائق الموجودة بجانبها ونحدد خصائصها الرئيسية - عدد الرقائق في المجموعة. هذه المعلومات هي التي تحدد بشكل فريد أي موضع في اللعبة ، ويجب أن نقدمها في شكل مناسب للبرمجة. نختار بنية البيانات الأبسط والأكثر وضوحًا - نبدأ بمصفوفة من عناصر H ونخزن في العنصر n من المصفوفة عدد المجموعات التي تحتوي على n رقائق بالضبط. ثم على سبيل المثال. بالنسبة لموضع البداية مع 3 شرائح ، سيكون لدينا تمثيل {0،0،1}. لا يزال إجراء التنفيذ للعرض التقديمي بسيطًا وفعالًا ، على الرغم من أنه بالطبع أكثر تعقيدًا من الإصدار الأول. بعد الخطوة الأولى (التي كان هناك اثنان بدلاً من ثلاثة) نحصل على المركزين {0،1،0} و {2،0،0}.

دعونا نحاول تقدير الكسب المتوقع في عدد التحركات لبنية بيانات معينة. للحركة الأولى ، لدينا خيارات (H-1) / 2 + 1 ، وللخطوة الثانية (قمنا بتقسيم المجموعة H إلى m و N-m-1) (m-1) / 2 + (N-m-1-1) / 2 (خذ رقاقة واحدة) + (م -2) / 2 + (N-m-1-2) / 2 (خذ شيبتين) = (H-3) / 2 + (H-5) / 2 وبالقياس ، نستنتج أنه في كل خطوة نقوم بحفظ نصف التحركات على الأقل. ثم يجب أن يكون مكسبنا 2 ^ H على الأقل ، وهو أمر جيد جدًا بالنسبة إلى H. في الواقع ، سيكون الكسب أكبر ، على سبيل المثال ، للموضع {8،0 ...} في النموذج الأول ، تحتاج إلى فرز 8 حركات ، وفي الثانية فقط 1 والربح في هذه الحالة سيكون 8 مرات. حتى نتمكن من الاعتماد بقوة على 2 ^ H ، ولكن نتوقع أكثر من ذلك بكثير ، والذي سنقوم بفحصه. وبالتأكيد ، بالنسبة للبرنامج وفقًا لهذا التمثيل ، نحصل على الجدول 4 ، يوضح السطر الأخير مكاسب الأداء عند التبديل إلى الإصدار الثاني من بنية البيانات (محسوبة يدويًا). إن النمو هائل بكل بساطة وقد وصلنا بكل ثقة (وصلنا إلى القاع) من خلال سقف إمكانية تحليل ما يصل إلى 20 شريحة في وضع البداية بتكلفة زمنية معقولة.

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

دعونا ننتبه إلى النتائج ونرى بعض الأشياء غير الواضحة. على سبيل المثال ، يدعي البرنامج أن الفوز المضمون في لعبة مباشرة لرقائق 9 لا يتحقق في 9 حركات على الإطلاق ، على النحو التالي من الخوارزمية المتماثلة الاسترشادية ، ولكن في 7 فقط ، وتتزامن الخطوة الأولى مع التوجيه (علاوة على ذلك ، هو المركز الوحيد الفائز) ) ، ولكن لا يجب أن يكرر الحركات الثالثة واللاحقة حركات الخصم على الإطلاق ، كما يلي من الخوارزمية الساذجة ، والمفتاح هنا هو {1،0،0،1} ، الذي حصل على تقييم +4. الآن بعد أن قدمنا ​​تقييمًا دقيقًا للعبة ، يمكننا طرح أسئلة مثيرة للاهتمام فيما يتعلق بوجود المواقف مع تقييم مستقر (حيث نسمح للمتنافس بالذهاب لأنفسنا) ، ووجود المواقف الرئيسية في شجرة التعداد ، والعثور على المواضع بالحركة الصحيحة الوحيدة ، وما إلى ذلك (و حتى الحصول على إجابات لهذه الأسئلة ، والأسئلة الصحيحة).

هنا جدول الدرجات الموجزة

رقائق البطاطس	مباشر	ملاحظات	المناصب / الوقت	المناصب / الوقت
1	1	-1	1/0	1/0
2	-2	2	4/0	2/0
3	3	-3	17/0	7/0
4	-4	-3	82/0	20/0
5	5	4	463/0	71/0
6	5	-5	3032/0	263/0
7	7	6	22693/0	1107/0
8	-8	-7	191422/0	4945/0
9	7	-7	1798427 / 0.1	24،283 / 0
10	9	8	18634228 / 0.8	125419/0
11	11	-9	211177537 / 10.4	699165 / 0.1
12	-10	-9	*** / 127	4057686 / 0.6
13	11	10		25056975 / 3.84
14	-12	-11		160643971/28
15	13	12		1082854607/213
16	-14	-13		*** / 1698

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

لقد أتقننا الخوارزمية من أعلى إلى أسفل (حسنًا ، بالطبع ، لم نكملها بالشكل القبيح الذي رسمته على ظهر الظرف ، ويمكنك تحسين الأداء بشكل كبير من خلال إعادة كتابة الإجراءات الأساسية بعناية ، ومن المؤكد أن يتم ذلك ، ولكن المشكلة ليست أساسية يقرر) ، لذلك دعونا نذهب في الاتجاه الآخر - من الأسفل إلى الأعلى. فكرة هذه الطريقة بسيطة وسهلة الفهم ، ولكنها صعبة جدًا للاستخدام البشري - نبدأ من الموضع النهائي ، والذي يتم تقديره وفقًا لقواعد اللعبة ، ونبدأ في نقل التقدير إلى أعلى الشجرة وفقًا لنفس القواعد مثل البحث من أعلى لأسفل. بالطبع ، في الوقت نفسه ، نحن نفكر في عدم إمكانية التحركات نزولًا من الموقف الحالي ، ولكننا نفكر في جميع المواقف التي يمكننا من خلالها الوصول إلى المركز الحالي في خطوة واحدة. ننقل التقدير وفقًا للقواعد المذكورة أعلاه. علاوة على ذلك ، نطبق هذا الإجراء بشكل متكرر وعندما يتوقف عن تحقيق النتائج ، أي أنه في الجولة التالية ، لم تغير وظيفة واحدة التقييم ، وتكتمل المهمة ويكون تقييم الموقف الأولي صحيحًا ودقيقًا. يسمح لك هذا النهج بتقليل وقت البحث بشكل كبير ، خاصة إذا قمت بإجراء بعض التحسينات ، ولكن له عيبًا قويًا (وهذا أمر كلاسيكي - نغير وقت الذاكرة) ، مما يحد بشكل كبير من نطاقه - متطلبات الذاكرة العالية ، حيث يجب علينا تخزين التقديرات , ( ).في حالة اللعبة المعنية ، تقترح طريقة تمثيل البت لبنية البيانات الأولى نفسها ، هناك طرق أخرى يمكن أن تقلل من حجم الذاكرة المطلوبة (تخزين مستويات الشجرة الثلاثة المدروسة فقط باستثناء الطبقة السفلية) ، ولكن ، بالطبع ، من خلال تدهور الأداء ، حيث يصبح البحث غير تافه للغاية. ومع ذلك ، بالنسبة إلى H لا يزيد عن 20 ، لن يكون إجمالي عدد المواضع أكثر من 2 ^ 20 ، ومجموعة من هذا الحجم في الذاكرة للعناصر التي تحتوي على رقم من -20 إلى 20 ، أي رقم 8 بت ، وأنا قادر تمامًا على تخيل ولن يكون تنفيذه صعبًا. لذا ، من الممكن تمامًا كتابة برنامج لهذه الخوارزمية وتقييم الأداء الناتج ، ولكن دعونا لا نتسرع ونضع تقديرات. ليس من الصعب تحديد نوع الذاكرة التي سيتعين علينا تخصيصها ، ولكن مع المعلمات المؤقتة تكون أكثر تعقيدًا إلى حد ما.لنفترض أننا أنشأنا على الفور جميع المراكز الممكنة ، ستكون M ، ثم يمكن تقدير متوسط ​​عدد التحركات من مركز واحد بما لا يزيد عن 2 * N (تقدير تقريبي جدًا). ثم ، في كل تكرار ، نحتاج إلى إجراء نقل لا يزيد عن M * 2 * H للتقدير ، وبما أننا في كل دورة سنحسن تقدير موضع واحد على الأقل ، سيكون إجمالي الوقت للترتيب M * 2 * H * M

بعد ذلك ، ولأول طريقة لتقديم البيانات ، نحصل على 2 ^ H * M * 2 ^ H = 2 ^ (2 * H) * M (نؤكد مرة أخرى أن هذا التقدير قوي جدًا من الأعلى) ، على سبيل المثال ، بالنسبة لـ H = 20 ، تقدير وقت البحث من الأعلى -سوف يكون 20! ~ 10E18 ، وللبحث من أسفل لأعلى لدينا 2 ^ 40 * 20 = (2 ^ 10) ^ 4 * 40 = (10 ^ 3) ^ 4 * 40 ~ 10 ^ 14 ، أي لـ 20 شريحة فزنا في الوقت المناسب على الأقل 10E6 مرة ، وهو أمر جيد للغاية. سنحسب أيضًا لـ 9 شرائح أولية ، ونحصل على 9! ~ 10E6 للبحث العلوي ، و 2 ^ 9 * 2 ^ 9 * 18 ~ 10E6 للفحص من أسفل إلى أعلى ، أي بدءًا من هذا الرقم ، يفوز البحث النهائي. البيان الأخير متسرع إلى حد ما ، حيث أن إجراء تقييم الموقف التالي أصبح أطول بشكل ملحوظ - سيتعين علينا البحث عنه من بين تلك التي تم إنشاؤها بالفعل ، ولكن لهذا التمثيل الخاص في شكل صفيف بت ، يتم تنفيذ هذا الإجراء في O (1).

بالنسبة للعرض الثاني ، من الضروري تقييم عدد المواقف المختلفة ، وهي مهمة من مجال التوافقية. كمثال ، ضع في اعتبارك لعبة تحتوي على 9 شرائح مبدئية ، والتي سيكون إجمالي عدد المواضع المختلفة لها: 1+ (1 + 4) + (1 + 3 + 2) + (1 + 3 + 3 + 2) + (1 + 2 + 2 + 1 + 1) + (1 + 2 + 1 + 1) + (1 + 1 + 1) + (1 + 1) + 1 = 1 + 5 + 6 + 9 + 7 + 5 + 3 + 2 + 1 = 39.
ثم سيؤدي التقدير بنفس الطريقة إلى القيمة H * M * M = 39 * 39 * 9 ~ 10E4 ، وهو أمران من حيث الحجم أفضل في السرعة مقارنة بالتمثيل الأول ، ومع زيادة H ، سيزيد الكسب فقط. مقارنةً بالانتقال إلى القمة من أجل العرض الثاني ، يجب أن تتوقع أيضًا تحسنًا كبيرًا في الأداء ، ولكن من الصعب تقييمه ، لذلك من الأسهل المحاولة.

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

— , , . , , ( ) .

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

ملاحظة.يقولون لي هنا من الجمهور (مرحبًا ماكس) أن هناك طريقة أخرى للبحث في اللعبة - رياضية ، وبالنظر إلى فرضية اللقب المزدوج التي تفيد بأن معظم ألعاب العد تنزل إلى لعبة نيم ، لذلك نحن بحاجة فقط إلى حسابه - المجموع الموقف الأولي (في رأيي ، البيان مشكوك فيه) ، ويمكنك أيضًا تحويل اللعبة الأصلية إلى ألعاب على الرسم البياني (لا يوجد اعتراض) ، حيث يمكنك توقع تقدير 1.878 ^ N في وقت العمل (على الرغم من أن الرقم المحدد يحيرني إلى حد ما). من المحتمل أن هذه الاعتبارات لها الحق في الحياة ، على الأقل تبدو مقالات هذا المحتوى مقنعة ، لكنني ممارس خالص وأترك ​​هذه الخيارات مرة أخرى للقراء الفضوليين (ars longa، vita brevis).