البحث الكلاسيكي: من البحث بالعرض إلى A*

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

أ. ما مسألة البحث

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

ولا يُكتب فضاء الحالات قط. بل يُولَّد خَلَفًا واحدًا في كل مرة، عند الطلب، وهذا ما يتيح لهذه الخوارزميات العمل في فضاءات عدد حالاتها يفوق عدد ذرّات الكون المرصود. فلا يُعدّ شيء لا يُزار.

ويُحكم على كل استراتيجية أدناه بأربعة أسئلة. هل هي تامّة - هل تجد حلًّا متى وُجد؟ هل هي مثلى - هل تجد الأرخص؟ ما كلفتها الزمنية بعدد العقد المولَّدة، وكلفتها الفضائية بعدد العقد المحفوظة دفعةً واحدة؟ وتُكتب الإجابات بـمعامل التفرّع $b$ وعمق $d$ لأقلّ الأهداف عمقًا.

ب. البحث غير المستنير والجدار الذي يصطدم به

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

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

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

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

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

ج. إضافة استدلال

يقدّر الاستدلال $h(n)$ الكلفة المتبقية من $n$ إلى هدف. والطريقة البديهية لاستعماله هي توسيع العقدة التي تبدو أقرب، $f(n) = h(n)$ - وهو البحث الجشع بالأفضل أولًا. وعلى خريطة طرق مع استدلال المسافة المستقيمة يتجه إلى الوجهة مباشرةً تقريبًا.

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

ويصلح A* هذا الإغفال بالضبط:

$$f(n) = g(n) + h(n)$$

الكلفة المتكبَّدة أصلًا زائد الكلفة المقدَّرة الآتية، فيقدّر $f(n)$ الكلفة الكلية لحلّ يمرّ عبر $n$. ووضع $h = 0$ يعيد البحث بالكلفة المنتظمة؛ وإهمال $g$ يعيد البحث الجشع؛ وA* هو الحالة العامة التي تحويهما.

وتتوقف الأمثلية عندئذ على شرطين على الاستدلال.

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

الاتساق. أما البحث في المخططات - حيث قد تُبلَغ الحالة عبر عدة مسارات - فشرطه الأقوى هو

$$h(n) \le c(n, a, n') + h(n')$$

لكل خَلَف $n'$ يُبلَغ بالفعل $a$: وهي متباينة مثلثية على التقدير. تجعل $f$ غير متناقصة على امتداد أي مسار، فأول مرة يوسّع فيها A* عقدةً يكون قد وجد أرخص طريق إليها. وكل استدلال متسق مقبول.

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

د. يستحق التحقق على خريطة حقيقية

ركن أراد-بوخارست من خريطة رومانيا عند راسل ونورفيغ صغير بما يكفي ليُبحَث بثلاث طرق ويُقارَن. فالبحث بالكلفة المنتظمة يجد طريق 418 كم عبر ريمنيكو فيلتشيا وبيتشتي، موسّعًا لذلك كل مدن الخريطة. والبحث الجشع لا يوسّع إلا أربع مدن ويعيد الطريق عبر فاغاراش - 450 كم، أي أسوأ بـ 32 كم بالضبط. أما A* فيعيد طريق 418 كم موسّعًا مدنًا أقل من الكلفة المنتظمة. فالأمثلية والجهد خاصيتان منفصلتان، والاستدلال هو ما يشتري الثانية دون إنفاق الأولى.

والحدّ العملي لـ A* هو الذاكرة لا الصحة: فهو يحتفظ بكل عقدة مولَّدة كي تبقى قيم $f$ قابلة للمقارنة. وA* بالتعميق التكراري يقايض عملًا مكرَّرًا ببصمة أصغر بكثير، تمامًا كما فعل التعميق التكراري للبحث بالعرض.

هـ. حين لا يهمّ المسار

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

وتسلّق التلال المجرّد - الانتقال دائمًا إلى أفضل جار - يعلق بثلاث طرق مميِّزة: عند قمة محلية أعلى من جيرانها وليست الأعلى؛ وعلى هضبة تتقارب فيها درجات الجيران فلا ميل يُتَّبع؛ وعلى حيد لا تحسّن عليه أي حركة مفردة مع أن تركيبًا منها كان سيحسّن. وإعادات التشغيل العشوائية تساعد: فإن نجحت كل محاولة باحتمال $p$، كان العدد المتوقع للمحاولات $1/p$.

والتلدين المحاكى يفلت بطريقة أخرى. فيختار جارًا عشوائيًا، ويقبل التحسّن دائمًا، ويقبل حركةً مسيئة بمقدار $\Delta E$ باحتمال $e^{-\Delta E/T}$. فالحركات السيئة شائعة مبكرًا حين تكون درجة الحرارة $T$ مرتفعة، ونادرة لاحقًا - إذ تهزّ الخوارزمية السطحَ بما يكفي للقفز خارج أمثلية محلية، ثم تكفّ عن الهزّ تدريجيًا. وإن خفّض جدول التبريد $T$ ببطء كافٍ، قارب احتمالُ إيجاد أمثلية عالمية الواحدَ، وهي عبارة عن النهاية لا وعدٌ بشأن جدول سريع بما يكفي للتنفيذ.

الشكل أدناه سطحٌ وعِر فيه سبع قمم محلّية وقمة شاملة واحدة. اختر بدايةً: يصعد تسلّق التلّ ثم يقف عند النتوء الذي كان عليه، بينما يتجاوز التلدين عدةً منها. وليست أيٌّ من الجولتين هي الدرس وحدها، لذا تحمل القراءة المعدّل أيضًا: يبلغ تسلّق التلّ الأمثلَ انطلاقًا من 26.4٪ من حالات البداية الـ201، معدودةً بدقة، وهو p في إعادات البدء المتوقّعة 1/p. ثم حرّك درجة الحرارة وراقب عدد الحركات المُسيئة المقبولة، فذلك العدد هو آليّة الخلاص نفسها.

إلى أين بعد ذلك

مسار التدريب البحث والاستدلالات يعالج هذا كله باختبارات وخلية قابلة للتنفيذ تبحث خريطة رومانيا بثلاث طرق. والبحث الخصومي والأدنى-الأعظم يتناول الحالة التي لا يكون فيها العائق المسافةَ بل خصمًا، وبحث A* هو مدخل المرجع.