الإصلاح الذي غيّر نسبة النجاح أكثر بكثير ممّا غيّر الكلفة

ثماني ملكات، واحدة في كل عمود، والحالة هي الصفوف الثمانية التي تقف عليها. وكلفة الحالة عدد الأزواج المتهاجمة. وتسلّق التلال بأشدّ صعود ينظر في النقلات $8 \times 7 = 56$ لملكة واحدة، ويأخذ أفضلها (وإحدى الفُضلى عشوائيًّا عند التساوي)، ويقف حين لا يكون شيء أفضل.

ومن 2,000 بداية عشوائيّة يحلّ 14.75% منها، أي 295 تشغيلًا، في 4.1 خطوة حين يفوز، و3.1 خطوة قبل أن يعلق.

أ. الإصلاح المعتاد

إنّما يعلق لأنّ التضاريس فيها هضاب: مناطق بأكملها تترك فيها كلُّ نقلة متاحة الكلفةَ حيث هي بالضبط. والعلاج المعتاد أن يُسمح بـنقلات جانبيّة، حتى حدٍّ ما، على أمل أن تكون الهضبة كتفًا وراءه انحدار.

اسمح بمئة نقلة جانبيّة متتالية، فتعطي البدايات الـ2,000 نفسها

$$94.55\% \qquad 19.5 \qquad 63.6$$

أي 94.55% محلولة، و19.5 خطوة عند النجاح، و63.6 عند الإخفاق. ونسبة نجاح تنتقل من 14.75% إلى 94.55% هي من الأرقام التي يُتبنّى عليها التغيير.

ب. كم يكلّف الحصول على جواب فعلًا

تسلّق التلال رخيص وقابل لإعادة البدء، فلا أحد يشغّله مرّةً واحدة. والمقدار الذي يهمّ هو العمل المتوقّع حتى يظهر حلّ:

$$\mathbb{E}[n] = \frac{1 - p}{p}\,\mathbb{E}[n \mid \text{fail}] + \mathbb{E}[n \mid \text{success}].$$

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

فالصيغة البسيطة تخفق نحو ستّ مرّات من سبع، لكنّها تخفق في 3.1 خطوة وتكلّف 21.9 خطوة إجمالًا. والصيغة المحسَّنة تنجح دائمًا تقريبًا، وتأخذ 19.5 خطوة لتفعل، وتكلّف 23.1 إجمالًا. فارتفاع نسبة النجاح ستّة أضعاف يساوي، إذا عُدّ بالخطوات وفي هذه المسألة، أقلّ قليلًا من لا شيء.

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

ج. المقارنة بين خطوات من طبائع مختلفة

يبدو التلدين المحاكى أسوأ بكثير في ذلك الجدول، والمقارنة غير منصفة كما هي. فخطوة تسلّق التلال تقيّم الخلفاء الـ56 قبل أن تتحرّك؛ وخطوة التلدين تقيّم واحدًا على الأكثر. فلنعدّ العمل، أي كلف الخلفاء المحسوبة فعلًا، بدل التكرارات. وثمّة أمران يُسقطهما عدّ الخطوات ولهما وزن هنا: كل تشغيل تسلّق يخفق يفحص النقلات الـ56 مرّةً أخيرة ليجد ألّا شيء منها يصلح، ولا يخطو مقابل ذلك خطوة. وسحبة واحدة من كل ثماني سحبات في التلدين تقع على صفّ الملكة نفسه فلا تقيّم شيئًا. وبعدّ الأمرين يكون العمل المتوقّع لكل حلّ:

• تسلّق بلا جانبيّة: $1{,}547$ تقييمًا
• تسلّق بجانبيّة: $1{,}298$
• تلدين: $1{,}622$ تقييمًا

ولو ضُربت مجاميع الخطوات في 56 لأعطت $1{,}224$ و$1{,}295$ وفاتها الفحص الأخير. وهذا الفحص يكلّف الصيغة البسيطة $5.78 \times 56 \approx 324$ تقييمًا لكل حلّ، لأنّها تخفق 5.78 مرّة مقابل كل نجاح، ويكلّف الصيغة الجانبيّة نحو 3. وهذا الفحص غير المعدود يقلب الترتيب: فبالتقييمات تجعل النقلات الجانبيّة الحلّ أرخص بنسبة 16%، حيث قال عدّ الخطوات إنّه أغلى بنسبة 6%.

وصارت الثلاثة في حدود عامل 1.25 بعضها من بعض. فالتلدين يشتري أعلى نسبة نجاح لكل تشغيل، 98.8%، بأعلى كلفة بين الثلاثة، لكن بفارق يسير ما إن تعدّ الشيء نفسه على الجانبين.

وهذا هو النصف الثاني من الدرس. فجدول القسم ب يعدّ خطوات، وهي ليست الوحدة نفسها في كل سطر؛ وهذه القائمة تعدّ تقييمات، وهي كذلك. وهما يسندان استنتاجين مختلفين: إصلاح يساوي أقلّ قليلًا من لا شيء، أو إصلاح يساوي 16%. وليس أيٌّ منهما التحسّن بستّة أضعاف الذي توحي به نسبة النجاح.

د. ما نأخذه من ذلك

• نسبة النجاح لكل تشغيل ليست كلفة. ففي كل إجراء قابل لإعادة البدء يكون المعيار هو العمل المتوقّع حتى الحلّ، وقد لا تكلّف طريقة تخفق ستّ مرّات من سبع إلا 19% أكثر من طريقة تخفق مرّة من ثماني عشرة.
• قِس الإخفاقات لا النجاحات وحدها، وقِس كل إخفاق كاملًا. فالفرق هنا يسكن في كلفة أن تعرف أنّ هذا التشغيل لن ينجح: 3.1 خطوة مقابل 63.6، يُضاف إليها الفحص الأخير الذي لا يجد شيئًا، وهو ربع كلفة الإخفاق في الصيغة البسيطة.
• عُدّ العمليّات لا التكرارات حين تختلف التكرارات. فالخطوة هي ما يقرّره التنفيذ، ومقارنة خطوات بين خوارزميّتين مختلفتَي حجم الخطوة لا تقارن شيئًا. وعدّ العمليّات يلتقط أيضًا العمل الذي ليس خطوة أصلًا.
• أبلغ عن المرجع الذي حسّنته بالمحاسبة نفسها. فتغييرٌ يرفع الرقم المعروض ستّة أضعاف ويحسّن المجموع بنسبة 16% جديرٌ بأن يُعرف قبل تبنّيه لا بعده.