بحث A*

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

وتُقيَّم كل عقدة بـ ‎f(n) = g(n) + h(n)‎، حيث g هي الكلفة المعلومة لأفضل مسار وُجد إلى n، وh تقدّر الكلفة المتبقية من n إلى هدف. وبما أن f تقدير للكلفة الكلية لحلّ يمرّ عبر n، فتوسيع أصغر f دائمًا هو ملاحقة الطريق الذي يبدو حاليًا أرخص إجمالًا.

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

والاستدلال يحدّد الكفاءة لا الصحة. فمع h المساوي للصفر تمامًا يؤول A* إلى البحث بالكلفة المنتظمة، فيكون أمثل لكنه يستكشف على اتساع. ومع استدلال قريب من الكلفة المتبقية الحقيقية يمضي إلى الهدف مباشرةً تقريبًا. ومن ثمّ فالاستدلالات المقبولة الأقوى هي الرافعة الرئيسية للأداء، وكثير من بحوث البحث الكلاسيكية معنيّ ببنائها.

في إيجاد المسارات على خريطة طرق، تكون g المسافة المقطوعة فعلًا لبلوغ مدينة، وh المسافةَ المستقيمة من تلك المدينة إلى الوجهة. والمسافة المستقيمة مقبولة لأن لا طريق يمكن أن يكون أقصر من الخط المباشر.

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

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