خوارزمية البحث A*

خوارزمية A* (تُنطق "إيه-ستار") هي خوارزمية لاجتياز الرسوم البيانية وإيجاد المسارات ، وتُستخدم في العديد من مجالات علوم الحاسوب نظرًا لشموليتها وأمثليتها وكفاءتها العالية. ^{[ 1 ]} بمعلومية رسم بياني مُثقَّل ، وعقدة مصدر ، وعقدة هدف، تجد الخوارزمية أقصر مسار (بالنسبة للأوزان المُعطاة) من المصدر إلى الهدف.

أحد أبرز عيوبه العملية هو${\displaystyle O(b^{d})}$يُعرَّف تعقيد المساحة في خوارزمية A* بأنه العمق الذي يُمثله d لأقصر مسار (طول أقصر مسار من عقدة المصدر إلى أي عقدة هدف مُعطاة)، و b عامل التفرع (الحد الأقصى لعدد الحلول اللاحقة لأي حالة مُعطاة). في أنظمة توجيه الرحلات العملية ، تتفوق عليها عمومًا الخوارزميات التي تُعالج الرسم البياني مُسبقًا لتحقيق أداء أفضل، ^{[ 2 ]} وكذلك الأساليب ذات الذاكرة المحدودة؛ ومع ذلك، لا تزال خوارزمية A* هي الحل الأمثل في كثير من الحالات. ^{[ 3 ]}

نشر بيتر هارت ونيلز نيلسون وبرترام رافائيل من معهد ستانفورد للأبحاث (الذي يُعرف الآن باسم SRI International ) الخوارزمية لأول مرة عام 1968. ^{[ 4 ]} ويمكن اعتبارها امتدادًا لخوارزمية ديكسترا . تحقق خوارزمية A* أداءً أفضل باستخدام أساليب استدلالية لتوجيه عملية البحث.

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

تم ابتكار خوارزمية A* كجزء من مشروع Shakey ، الذي كان يهدف إلى بناء روبوت متحرك قادر على تخطيط حركاته بنفسه. اقترح نيلز نيلسون في البداية استخدام خوارزمية Graph Traverser ^{[ 5 ]} لتخطيط مسار Shakey. ^{[ 6 ]} تعتمد خوارزمية Graph Traverser على دالة استدلالية h ( n ) ، وهي المسافة المُقدَّرة من العقدة n إلى عقدة الهدف، وتتجاهل تمامًا g ( n ) ، وهي المسافة من عقدة البداية إلى n . اقترح بيرترام رافائيل استخدام المجموع، g ( n ) + h ( n ) . ^{[ 7 ]} ابتكر بيتر هارت المفاهيم التي نسميها الآن مقبولية واتساق الدوال الاستدلالية. صُممت خوارزمية A* في الأصل لإيجاد المسارات الأقل تكلفة عندما تكون تكلفة المسار هي مجموع تكاليفه، ولكن ثبت أنه يمكن استخدام A* لإيجاد المسارات المثلى لأي مشكلة تُحقق شروط جبر التكلفة. ^{[ 8 ]}

تضمنت الورقة البحثية الأصلية لخوارزمية A* لعام 1968 ^{[ 4 ]} نظرية تنص على أنه لا يمكن لأي خوارزمية شبيهة بـ A* ^{[ a ]} توسيع عدد أقل من العقد مقارنةً بـ A* إذا كانت الدالة الاستدلالية متسقة وتم اختيار قاعدة كسر التعادل لـ A* بشكل مناسب. نُشر "تصحيح" بعد بضع سنوات ^{[ 9 ]} زعم أن الاتساق ليس شرطًا، ولكن تبين خطأ هذا الادعاء في عام 1985 في دراسة ديتشر وبيرل الحاسمة حول أمثلية A* (التي تُسمى الآن الكفاءة المثلى)، والتي قدمت مثالًا على خوارزمية A* ذات دالة استدلالية مقبولة ولكنها غير متسقة، حيث توسع عددًا أكبر من العقد بشكل تعسفي مقارنةً بخوارزمية بديلة شبيهة بـ A*. ^{[ 10 ]}

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

في كل تكرار من حلقتها الرئيسية، تحتاج خوارزمية A* إلى تحديد أي من مساراتها يجب تمديده. وتفعل ذلك بناءً على تكلفة المسار وتقدير التكلفة اللازمة لتمديد المسار حتى الوصول إلى الهدف. وبشكلٍ أدق، تختار خوارزمية A* المسار الذي يقلل من

${\displaystyle f(n)=g(n)+h(n)}$

حيث n هي العقدة التالية على المسار، و g ( n ) هي تكلفة المسار من عقدة البداية إلى n ، و h ( n ) هي دالة استدلالية تُقدّر تكلفة المسار الأرخص من n إلى الهدف. وتختلف هذه الدالة الاستدلالية باختلاف المسألة.

تستخدم التطبيقات النموذجية لخوارزمية A* قائمة انتظار ذات أولوية لإجراء عملية اختيار متكررة للعقد ذات التكلفة الدنيا (المُقدَّرة) للتوسع. تُعرف قائمة الانتظار هذه باسم المجموعة المفتوحة أو الحافة أو الحدود . في كل خطوة من خطوات الخوارزمية، تُزال العقدة ذات أدنى قيمة f ( x ) من قائمة الانتظار، ويتم تحديث قيم f و g لجيرانها وفقًا لذلك، ثم تُضاف هذه العقد المجاورة إلى قائمة الانتظار. تستمر الخوارزمية حتى تصبح إحدى العقد المُزالة (أي العقدة ذات أدنى قيمة f من بين جميع عقد الحافة) عقدة هدف. ^{[ ب ]} تُصبح قيمة f لهذا الهدف هي أيضًا تكلفة أقصر مسار، لأن h عند الهدف تساوي صفرًا في طريقة استدلالية مقبولة.

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

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

إذا حققت الدالة الاستدلالية h الشرط الإضافي h ( x ) ≤ d ( x , y ) + h ( y ) لكل حافة ( x , y ) في الرسم البياني (حيث d يمثل طول تلك الحافة)، فإن h تُسمى دالة رتيبة أو متسقة . مع دالة استدلالية متسقة، يضمن A* إيجاد المسار الأمثل دون معالجة أي عقدة أكثر من مرة، ويُكافئ A* تشغيل خوارزمية ديكسترا بتكلفة مُخفَّضة d' ( x , y ) = d ( x , y ) + h ( y ) − h ( x ) . ^{[ 11 ]}

الشفرة الزائفة

يصف الكود الزائف التالي الخوارزمية:

دالة إعادة بناء المسار ( من المصدر ، الحالي ) المسار_الكلي := {الحالي} بينما الحالي في مفاتيح المصدر : الحالي : = من المصدر [ الحالي ] المسار_الكلي.إضافة ( الحالي ) إرجاع المسار_الكلي// خوارزمية A* تجد مسارًا من البداية إلى الهدف. // h هي الدالة الاستدلالية. h(n) تُقدّر تكلفة الوصول إلى الهدف من العقدة n. دالة a_star ( البداية ، الهدف ، h ) // مجموعة العقد المكتشفة التي قد تحتاج إلى (إعادة) توسيعها. // في البداية، تكون عقدة البداية فقط معروفة. // عادةً ما يتم تنفيذ ذلك باستخدام كومة دنيا أو قائمة انتظار ذات أولوية بدلاً من مجموعة تجزئة. open_set := {البداية}// بالنسبة للعقدة n، فإن came_from[n] هي العقدة التي تسبقها مباشرةً على أرخص مسار معروف حاليًا من نقطة البداية // إلى n. came_from := خريطة فارغة// بالنسبة للعقدة n، فإن g_score[n] هي التكلفة المعروفة حاليًا لأرخص مسار من البداية إلى n. g_score := خريطة بقيمة افتراضية لا نهائية g_score [ start ] := 0// بالنسبة للعقدة n، f_score[n] := g_score[n] + h(n). يمثل f_score[n] أفضل تقدير لدينا حاليًا حول مدى انخفاض تكلفة المسار من البداية إلى النهاية إذا مر عبر n. f_score := خريطة بقيمة افتراضية لا نهائية. f_score [ start ] : = h ( start )بينما open_set غير فارغة // يمكن أن تتم هذه العملية في زمن O(Log(N ) ) إذا كانت open_set عبارة عن كومة دنيا أو طابور أولوية. current : = العقدة في open_set التي لها أقل قيمة f_score [] إذا كان current = goal أعد reconstruct_path ( came_from , current )open_set.remove ( current ) for each neighbor of current // d(current,neighbor) is the weight of the edge from current to neighbor // tentative_g_score is the distance from start to the neighbor through current tentative_g_score := g_score [ current ] + d ( current , neighbor ) if tentative_g_score < g_score [ neighbor ] // this path to neighbor is better than any previous path. Record it! came_from [ neighbor ] : = current g_score [ neighbor ] : = tentative_g_score f_score [ neighbor ] := tentative_g_score + h ( neighbor ) if neighbor not in open_set open_set.add ( neighbor )// المجموعة المفتوحة فارغة ولكن لم يتم الوصول إلى الهدف أبدًا، يتم إرجاع حالة الفشل

ملاحظة: في هذه الشفرة الزائفة، إذا تم الوصول إلى عقدة عبر مسار، ثم إزالتها من المسار open_set، ثم الوصول إليها لاحقًا عبر مسار أقل تكلفة، فسيتم إضافتها إلى المسار open_setمرة أخرى. هذا ضروري لضمان أن المسار المُعاد هو الأمثل إذا كانت الدالة الاستدلالية مقبولة ولكنها غير متسقة . إذا كانت الدالة الاستدلالية متسقة، فعند إزالة عقدة من open_setالمسار إليها، يُضمن أن يكون المسار هو الأمثل، وبالتالي tentative_g_score < g_score[neighbor]سيفشل الاختبار دائمًا إذا تم الوصول إلى العقدة مرة أخرى. تُسمى الشفرة الزائفة المُطبقة هنا أحيانًا بنسخة البحث في الرسم البياني من خوارزمية A*. ^{[ 12 ]} وهذا على عكس النسخة التي لا تتضمن tentative_g_score < g_score[neighbor]اختبار إعادة إضافة العقد إلى المسار open_set، والتي تُسمى أحيانًا بنسخة البحث في الشجرة من خوارزمية A* وتتطلب دالة استدلالية متسقة لضمان الأمثلية.

بينما يضمن معيار القبول مسار الحل الأمثل، فإنه يعني أيضًا أن خوارزمية A* يجب أن تفحص جميع المسارات المتساوية في الجدارة للعثور على المسار الأمثل. لحساب أقصر المسارات التقريبية، من الممكن تسريع البحث على حساب الأمثلية عن طريق تخفيف معيار القبول. غالبًا ما نرغب في تحديد حد لهذا التخفيف، بحيث نضمن ألا يكون مسار الحل أسوأ من (1 + ε ) ضعف مسار الحل الأمثل. يُشار إلى هذا الضمان الجديد باسم "القبول- ε" .

يوجد عدد من الخوارزميات المقبولة من النوع ε :

• خوارزمية A* الموزونة/الأوزان الثابتة. ^{[ 18 ]} إذا كانت h _{_a}( n ) دالة استدلالية مقبولة، ففي النسخة الموزونة من بحث A*، تُستخدم h _{_w} ( n ) = ε_ha ( n ) ، حيث ε > 1، كدالة استدلالية، ويُجرى بحث A* كالمعتاد (وهو ما يحدث في النهاية بشكل أسرع من استخدام h _{_a} نظرًا لتوسيع عدد أقل من العقد). وبالتالي، يمكن أن تكون تكلفة المسار الذي تجده خوارزمية البحث على الأكثر ε ضعف تكلفة المسار الأقل تكلفة في الرسم البياني. ^{[ 19 ]}
• القطع المكافئ المحدب لأعلى/لأسفل (XUP/XDP). ^{[ 20 ]} تعديل لدالة التكلفة في خوارزمية A* الموزونة لدفع الحل الأمثل نحو نقطة البداية أو الهدف. يوفر XDP مسارات شبه مثالية بالقرب من نقطة البداية، بينما توفر مسارات XUP مسارات شبه مثالية بالقرب من الهدف. كلا الطريقتين تؤديان إلى نتائج مُرضية.${\displaystyle \epsilon }$- المسارات المثلى بشكل عام.

  ${\displaystyle f_{\text{XDP}}(n)={\frac {1}{2\epsilon }}\left[\ g(n)+(2\epsilon -1)+{\sqrt {(g(n)-h(n))^{2}+4\epsilon g(n)h(n)}}\ \right]}$.

  ${\displaystyle f_{\text{XUP}}(n)={\frac {1}{2\epsilon }}\left[\ g(n)+h(n)+{\sqrt {(g(n)+h(n))^{2}+4\epsilon (\epsilon -1)h(n)^{2}}}\ \right]}$.

• منحنى صاعد/هابط مُجزأ (pwXU/pwXD). ^{[ 21 ]} مشابه لـ XUP/XDP ولكن بدوال مُجزأة بدلاً من القطع المكافئ. مسارات الحل هي أيضًا${\displaystyle \epsilon }$-أفضل.

  ${\displaystyle f_{\text{pwXD}}(n)={\begin{cases}g(n)+h(n),&{\text{if }}h(n)>g(n)\\g(n)+(2\epsilon -1)h(n)/\epsilon ,&{\text{if }}h(n)\leq g(n)\end{cases}}}$

  ${\displaystyle f_{\text{pwXU}}(n)={\begin{cases}g(n)/(2\epsilon -1)+h(n),&{\text{if }}g(n)<(2\epsilon -1)h(n)\\(g(n)+h(n))/\epsilon ,&{\text{if }}g(n)\geq (2\epsilon -1)h(n)\end{cases}}}$

• يستخدم الترجيح الديناميكي ^{[ 22 ]} دالة التكلفة${\displaystyle f(n)=g(n)+(1+\varepsilon w(n))h(n)}$، حيث${\displaystyle w(n)={\begin{cases}1-{\frac {d(n)}{N}}&d(n)\leq N\\0&{\text{otherwise}}\end{cases}}}$وحيث​${\displaystyle d(n)}$يمثل عمق البحث و N هو الطول المتوقع لمسار الحل.
• يستخدم الترجيح الديناميكي المأخوذ عينات ^{[ 23 ]} أخذ عينات من العقد لتحسين تقدير الخطأ الاستدلالي وإزالة التحيز منه.
• ${\displaystyle A_{\varepsilon }^{*}}$[ ^{24 ]} يستخدم دالتين استدلاليتين. الأولى هي قائمة FOCAL، والتي تُستخدم لاختيار العقد المرشحة، والثانية هي ^h F _التي تُستخدم لاختيار العقدة الأكثر وعدًا من قائمة FOCAL.
• يختار A _ε ^{[ 25 ]} العقد باستخدام الدالة ⁠${\displaystyle Af(n)+Bh_{F}(n)}$حيث A و B ثابتان. إذاتعذر تحديد أي عقد، فسيتراجع الخوارزمية باستخدام الدالة .${\displaystyle Cf(n)+Dh_{F}(n)}$، حيث C و D ثابتان.
• تحاول خوارزمية AlphA* ^{[ 26 ]} تعزيز استغلال البيانات من خلال البحث العميق أولاً، وذلك بتفضيل العقد التي تم توسيعها مؤخراً. وتستخدم AlphA* دالة التكلفة.${\displaystyle f_{\alpha }(n)=(1+w_{\alpha }(n))f(n)}$، أين${\displaystyle w_{\alpha }(n)={\begin{cases}\lambda &g(\pi (n))\leq g({\tilde {n}})\\\Lambda &{\text{otherwise}}\end{cases}}}$حيث λ و Λ ثابتان مع${\displaystyle \lambda \leq \Lambda }$، π ( n ) هو الأصل لـ n ، و ñ هي العقدة التي تم توسيعها مؤخرًا.

باعتبارها خوارزمية بحث استدلالية، فإن أداء خوارزمية A* يتأثر بشكل كبير بجودة الدالة الاستدلالية.${\textstyle h(n)}$إذا كانت الطريقة الاستدلالية قريبة من التكلفة الحقيقية للوصول إلى الهدف، فإن خوارزمية A* قادرة على تقليل عدد عمليات توسيع العقد بشكل ملحوظ. من ناحية أخرى، قد تؤدي الطريقة الاستدلالية غير الدقيقة إلى العديد من عمليات التوسيع غير الضرورية.

أسوأ الحالات

في أسوأ الأحوال، تقوم خوارزمية A* بتوسيع جميع العقد.${\textstyle n}$والتي${\textstyle f(n)=g(n)+h(n)\leq C^{*}}$، أين${\textstyle C^{*}}$هي تكلفة عقدة الهدف الأمثل.

لماذا لا يمكن أن يكون الأمر أسوأ

لنفترض وجود عقدة${\textstyle N'}$في القائمة المفتوحة مع${\textstyle f(N')>C^{*}}$وهي العقدة التالية التي سيتم توسيعها. بما أن عقدة الهدف تحتوي على${\textstyle f(goal)=g(goal)+h(goal)=g(goal)=C^{*}}$، و${\textstyle f(N')>C^{*}}$، ستكون قيمة f للعقدة الهدف أقل وسيتم توسيعها قبل${\textstyle N'}$لذلك، لا تقوم خوارزمية A* بتوسيع العقد باستخدام${\textstyle f(n)>C^{*}}$.

لماذا لا يمكن أن يكون أفضل

افترض وجود خوارزمية مثلى توسع عددًا أقل من العقد من${\textstyle C^{*}}$في أسوأ الأحوال، باستخدام نفس الأسلوب الاستدلالي. هذا يعني أنه لا بد من وجود عقدة ما.${\textstyle N'}$بحيث${\textstyle f(N')<C^{*}}$ومع ذلك، يختار البرنامج عدم توسيعه.

والآن، لنفترض رسمًا بيانيًا معدلًا حيث توجد حافة جديدة من التكلفة${\textstyle \varepsilon }$(مع${\textstyle \varepsilon >0}$) تُضاف من${\textstyle N'}$إلى الهدف. إذا${\textstyle f(N')+\varepsilon <C^{*}}$ثم يمر المسار الأمثل الجديد عبر${\textstyle N'}$ومع ذلك، بما أن الخوارزمية لا تزال تتجنب التوسع${\textstyle N'}$، فسوف يفوت المسار الأمثل الجديد، مما ينتهك أمثليته.

لذلك، لا يمكن لأي خوارزمية مثلى، بما في ذلك خوارزمية A*، أن توسع عددًا أقل من العقد من${\textstyle C^{*}}$في أسوأ الأحوال.

الترميز الرياضي

غالبًا ما يُوصف تعقيد خوارزمية A* في أسوأ الحالات بأنه${\textstyle O(b^{d})}$، أين${\displaystyle b}$هو عامل التفرع و${\textstyle d}$يمثل هذا عمق الهدف الأقل عمقًا. ورغم أن هذا يعطي فكرة عامة، إلا أنه لا يعكس بدقة السلوك الفعلي لخوارزمية A*.

يأخذ الحد الأكثر دقة في الاعتبار عدد العقد التي${\textstyle f(n)\leq C^{*}}$. لو${\displaystyle \varepsilon }$أصغر فرق ممكن في${\textstyle f}$إذا كانت التكلفة بين العقد المتميزة، فقد تتوسع خوارزمية A* إلى ما يلي:

${\displaystyle O\left({\frac {C^{*}}{\varepsilon }}\right)}$

يمثل هذا تعقيد الوقت والمساحة في أسوأ الحالات.

تُستخدم خوارزمية A* غالبًا لحل مشكلة إيجاد المسار الشائعة في تطبيقات مثل ألعاب الفيديو، ولكنها صُممت في الأصل كخوارزمية عامة لاجتياز الرسوم البيانية. ^{[ 4 ]} ولها تطبيقات في مشاكل متنوعة، بما في ذلك مشكلة التحليل النحوي باستخدام القواعد النحوية العشوائية في معالجة اللغات الطبيعية . ^{[ 27 ]} ومن الأمثلة الأخرى البحث المعلوماتي مع التعلم عبر الإنترنت. ^{[ 28 ]}

ما يميز خوارزمية A* عن خوارزمية البحث الأفضل أولاً الجشعة هو أنها تأخذ التكلفة / المسافة المقطوعة بالفعل، g ( n ) ، في الاعتبار.

يمكن اعتبار بعض المتغيرات الشائعة لخوارزمية ديكسترا حالة خاصة من خوارزمية A* حيث يكون الاستدلال${\displaystyle h(n)=0}$لجميع العقد؛ ^{[ 13 ] [ 14 ]} بدورها، تُعد كل من خوارزمية ديكسترا وخوارزمية A* حالتين خاصتين من البرمجة الديناميكية . ^{[ 29 ]} وتُعد خوارزمية A* نفسها حالة خاصة من تعميم خوارزمية التفرع والتقييد . ^{[ 30 ]}

خوارزمية A* تشبه خوارزمية البحث الشعاعي باستثناء أن خوارزمية البحث الشعاعي تضع حدًا لعدد المسارات التي يتعين عليها استكشافها. ^{[ 31 ]}

• في أي وقت A* ^{[ 32 ]}
• المجموعة أ*
• د*
• الحقل د*
• هامش
• حساب التوفير الإضافي أ* (FSA*)
• خوارزمية التكيف المعممة A* (GAA*)
• البحث الاستدلالي التدريجي
• A* المخفضة ^{[ 33 ]}
• خوارزمية التعمق التكراري A* (IDA*)
• البحث عن نقطة القفز
• التخطيط مدى الحياة A* (LPA*)
• خوارزمية A* ثنائية الاتجاه الجديدة (NBA*) ^{[ 34 ]}
• الذاكرة المبسطة المحدودة A* (SMA*)
• ثيتا*

يمكن أيضًا تكييف خوارزمية A* لتصبح خوارزمية بحث ثنائية الاتجاه ، ولكن يجب توخي الحذر الشديد فيما يتعلق بمعيار التوقف. ^{[ 35 ]}

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

• نيلسون، ن. ج. (1980). مبادئ الذكاء الاصطناعي . بالو ألتو، كاليفورنيا: شركة تيوغا للنشر. ISBN 978-0-935382-01-3.
• والش، توبي. أقصر تاريخ للذكاء الاصطناعي .

• نوع مختلف من خوارزمية A* يسمى خوارزمية البحث عن المسار الهرمي A* (HPA*)
• برايان غرينستيد. "خوارزمية البحث A* في جافا سكريبت (مُحدَّثة)" . مؤرشف من الأصل بتاريخ 15 فبراير 2020. تم الاطلاع عليه بتاريخ 8 فبراير 2021 .