حلّ المسائل بوصفه بحثًا

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

الأجزاء الخمسة لمسألة البحث

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

وكلمة ضمنًا هي التي تؤدي العمل. فلا يُكتب فضاء الحالات قط، بل يُولَّد عند الطلب، خَلَفًا خَلَفًا، وهذا ما يجعل البحث ممكنًا في فضاءات عدد حالاتها يفوق عدد ذرّات الكون المرصود. والحلّ متتالية أفعال من الحالة الابتدائية إلى هدف، والحلّ الأمثل هو الأقلّ كلفةً إجمالًا.

أربعة أسئلة تُطرح على أي استراتيجية

يُحكم على كل استراتيجية في هذا الدرس بالمعايير الأربعة نفسها:

• التمام - إن وُجد حلّ، هل يُضمن للخوارزمية أن تجده؟
• الأمثلية - هل تجد الحلّ الأرخص؟
• التعقيد الزمني - كم عقدةً تولّد؟
• التعقيد الفضائي - كم عقدةً تحتفظ بها في الذاكرة دفعةً واحدة؟

ويُعبَّر عن التعقيد بـمعامل التفرّع $b$، أي عدد الخلفاء لكل عقدة، والعمق $d$ لأقلّ الأهداف عمقًا.

البحث بالعرض وجدار الذاكرة

يوسّع البحث بالعرض أقلّ العقد غير الموسَّعة عمقًا، فيجد هدفًا من أقلّها عمقًا. وهو تامّ متى كان $b$ منتهيًا، ويولّد ما رتبته $b^d$ عقدة بشرط أن يُطبَّق اختبار الهدف على كل عقدة حين تولَّد. فإن أُجِّل الاختبار إلى التوسيع، كما يلزم البحث ذا الكلفة المنتظمة، وُلِّد المستوى التالي كلّه أوّلًا: $O(b^{d+1})$.

والفخّ في الفضاء. فالجبهة كلها محفوظة دفعةً واحدة، فتكون الذاكرة أيضًا $O(b^d)$ - الأسّية نفسها التي للزمن. ويجدول راسل ونورفيغ ما يعنيه ذلك عند $b = 10$ بمليون عقدة في الثانية وكيلوبايت لكل عقدة، ويستخلصان الدرس صراحةً:

متطلبات الذاكرة مشكلة أكبر للبحث بالعرض من زمن التنفيذ.

فالبحث حتى العمق 12 يستغرق نحو ثلاثة عشر يومًا، وهو ما قد يُنتظَر. لكنه يحتاج أيضًا بيتابايت من الذاكرة، ولا تملكه آلة عادية. الزمن إزعاج؛ أما الذاكرة فجدار.

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

البحث بالعمق والتعميق التكراري

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

ويأخذ التعميق التكراري النصف الجيد من كلٍّ منهما. فيُنفَّذ بحث محدود العمق بالحدّ 0، ثم 1، ثم 2، إلى أن يُوجد هدف:

والسطران اللذان فيهما $O(b^d)$، وكذلك الثلاثة عشر يومًا والبيتابايت أعلاه، تفترض اختبار الهدف حين التوليد؛ أمّا عند التوسيع فيصير كلٌّ منها $O(b^{d+1})$.

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

قبل الاختبار

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