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

فصل	خوارزمية البحث
هيكل البيانات	الرسم البياني
الأداء في أسوأ الأحوال	${\displaystyle O(|E|\log |V|)=O(b^{d})}$
أسوأ حالة تعقيد الفضاء	${\displaystyle O(|V|)=O(b^{d})}$

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

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

نشر بيتر هارت ونيلز نيلسون وبرتراند رافائيل من معهد ستانفورد للأبحاث (الآن معهد ستانفورد للأبحاث الدولي ) الخوارزمية لأول مرة في عام 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* ستعيد مسارًا أقل تكلفة من البداية إلى الهدف.

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

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

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

إذا كانت القاعدة 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]

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

دالة reconstruct_path ( cameFrom , current ) total_path := {current} بينما current في cameFrom . المفاتيح : current := cameFrom [ current ] total_path . prepend ( current ) return total_path  
      
       
          
        
     

// A* يجد مسارًا من البداية إلى الهدف. 
// h هي الدالة الإرشادية. h(n) تقدر التكلفة للوصول إلى الهدف من العقدة n. 
function A_Star ( start , goal , h ) // مجموعة العقد المكتشفة التي قد تحتاج إلى (إعادة) التوسع. // في البداية، تكون عقدة البداية فقط معروفة. // يتم تنفيذ هذا عادةً كقائمة كومة صغيرة أو قائمة أولوية بدلاً من مجموعة تجزئة. openSet := {start}   
    
    
    
      

    // بالنسبة للعقدة n، cameFrom[n] هي العقدة التي تسبقها مباشرة على المسار الأرخص من البداية 
إلى n المعروف حاليًا. cameFrom : = خريطة فارغة    
        

    
// بالنسبة للعقدة n، gScore[n] هي تكلفة المسار الأرخص من البداية إلى n المعروف حاليًا. gScore := خريطة بقيمة افتراضية لا نهائية gScore [ start ] : = 0           
      

    // بالنسبة للعقدة n، fScore[n] := gScore[n] + h(n). يمثل fScore[n] أفضل تخمين لدينا حاليًا فيما يتعلق 
بمدى رخص مسار من البداية إلى النهاية إذا مر عبر n. fScore : = خريطة بقيمة افتراضية لا نهائية fScore [ start ] := h ( start )    
           
      

    بينما openSet ليس فارغًا // يمكن أن تحدث هذه العملية في وقت O(Log(N)) إذا كانت openSet عبارة عن كومة صغيرة أو قائمة انتظار ذات أولوية current : = العقدة في openSet التي لها أقل قيمة fScore [ ] if current = goal return reconstruct_path ( cameFrom , current )    
        
                  
           
              

        openSet . إزالة ( الحالي ) 
لكل جار للتيار // d(الحالي، الجار) هو وزن الحافة من الحالي إلى الجار // tentative_gScore هي المسافة من البداية إلى الجار عبر التيار tentative_gScore : = gScore [ الحالي ] + d ( الحالي ، الجار ) إذا كان tentative_gScore < gScore [ الجار ] // هذا المسار إلى الجار أفضل من أي مسار سابق. سجله! cameFrom [ الجار ] := current gScore [ الجار ] := tentative_gScore fScore [ الجار ] : = tentative_gScore + h ( الجار ) إذا لم يكن الجار في openSet openSet . إضافة ( الجار )            
            
            
                 
               
                
                  
                  
                    
                    
                    

    // المجموعة المفتوحة فارغة ولكن لم يتم الوصول إلى الهدف مطلقًا، 
مما أدى إلى فشل الإرجاع     

ملاحظة: في هذا الكود الزائف، إذا تم الوصول إلى عقدة من خلال مسار واحد، وإزالتها من openSet، ثم الوصول إليها لاحقًا من خلال مسار أرخص، فسيتم إضافتها إلى openSet مرة أخرى. هذا ضروري لضمان أن المسار الذي تم إرجاعه هو المسار الأمثل إذا كانت الدالة الإرشادية مقبولة ولكنها غير متسقة . إذا كانت الدالة الإرشادية متسقة، فعند إزالة عقدة من openSet، يتم ضمان أن المسار إليها هو المسار الأمثل، وبالتالي فإن الاختبار ' tentative_gScore < gScore[neighbor]' سيفشل دائمًا إذا تم الوصول إلى العقدة مرة أخرى.

مثال على خوارزمية A* في العمل حيث تكون العقد عبارة عن مدن متصلة بالطرق وh(x) هي المسافة في خط مستقيم إلى نقطة الهدف:

المفتاح: أخضر: البداية؛ أزرق: الهدف؛ برتقالي: تمت الزيارة

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

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

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

يمكن اعتبار خوارزمية ديكسترا ، كمثال آخر لخوارزمية البحث ذات التكلفة الموحدة، حالة خاصة من A* حيث ⁠ ⁠${\displaystyle h(x)=0}$ لجميع x . ^{[12] [13]} يمكن تنفيذ البحث العام أولاً بالعمق باستخدام A* من خلال مراعاة وجود عداد عالمي C تم تهيئته بقيمة كبيرة جدًا. في كل مرة نعالج فيها عقدة، نعين C لجميع جيرانها المكتشفين حديثًا. بعد كل تعيين واحد، نقوم بتقليل العداد C بمقدار واحد. وبالتالي، كلما تم اكتشاف العقدة مبكرًا، زادت قيمتها ⁠ ⁠${\displaystyle h(x)}$ . يمكن تنفيذ كل من خوارزمية ديكسترا والبحث أولاً بالعمق بكفاءة أكبر دون تضمين قيمة ⁠ ⁠${\displaystyle h(x)}$ في كل عقدة.

في الرسوم البيانية المحدودة ذات أوزان الحواف غير السلبية، من المؤكد أن A* ستنتهي وستكون كاملة ، أي أنها ستجد دائمًا حلًا (مسار من البداية إلى الهدف) إذا كان موجودًا. في الرسوم البيانية غير المحدودة ذات عامل التفرع المحدود وتكاليف الحواف المحدودة بعيدًا عن الصفر ( لبعض الثوابت )، من المؤكد أن A* ستنتهي فقط إذا كان هناك حل. ^[1]${\textstyle d(x,y)>\varepsilon >0}$${\displaystyle \varepsilon }$

يقال إن خوارزمية البحث مقبولة إذا كان من المضمون أن تعيد الحل الأمثل. إذا كانت الدالة الاستدلالية المستخدمة بواسطة A* مقبولة ، فإن A* مقبولة. "الدليل" البديهي على ذلك هو كما يلي:

عندما ينهي A* بحثه، يكون قد وجد مسارًا من البداية إلى الهدف تكون تكلفته الفعلية أقل من التكلفة المقدرة لأي مسار من البداية إلى الهدف عبر أي عقدة مفتوحة (قيمة العقدة ) . عندما يكون الاستدلال مقبولًا، تكون هذه التقديرات متفائلة (ليست تمامًا${\displaystyle f}$ - انظر الفقرة التالية)، لذلك يمكن لـ A* تجاهل هذه العقد بأمان لأنها لا يمكن أن تؤدي بأي حال من الأحوال إلى حل أرخص من الحل الذي لديه بالفعل. بعبارة أخرى، لن يتجاهل A* أبدًا إمكانية وجود مسار أقل تكلفة من البداية إلى الهدف وبالتالي سيستمر في البحث حتى لا توجد مثل هذه الاحتمالات.

الإثبات الفعلي أكثر تعقيدًا بعض الشيء لأن قيم العقد المفتوحة لا يُضمن أنها متفائلة حتى لو كانت ${\displaystyle f}$القاعدة مقبولة. وذلك لأن قيم العقد${\displaystyle g}$ المفتوحة لا يُضمن أنها مثالية، وبالتالي لا يُضمن أن يكون المجموع متفائلًا .${\displaystyle g+h}$

الخوارزمية A فعالة بشكل مثالي فيما يتعلق بمجموعة من الخوارزميات البديلة Alts في مجموعة من المشكلات P إذا كانت مجموعة العقد الموسعة بواسطة A في حل P لكل مشكلة P وكل خوارزمية A′ في Alts هي مجموعة فرعية (ربما مساوية) من مجموعة العقد الموسعة بواسطة A′ في حل P. الدراسة النهائية للكفاءة المثلى لـ A* ترجع إلى رينا ديختر وجوديا بيرل. ^[10] لقد نظروا في مجموعة متنوعة من التعريفات لـ Alts و P بالاقتران مع كون الاستدلال A* مقبولًا فحسب أو متسقًا ومقبولًا . النتيجة الإيجابية الأكثر إثارة للاهتمام التي أثبتوها هي أن A*، مع الاستدلال المتسق، فعالة بشكل مثالي فيما يتعلق بجميع خوارزميات البحث المشابهة لـ A* المقبولة في جميع مشكلات البحث "غير المرضية". وبشكل تقريبي، فإن مفهومهم للمشكلة غير المرضية هو ما نعنيه الآن بـ "حتى كسر التعادل". لا تصمد هذه النتيجة إذا كانت الخوارزمية A* مقبولة ولكنها غير متسقة. في هذه الحالة، أظهر ديشتر وبيرل وجود خوارزميات مقبولة شبيهة بخوارزمية A* يمكنها توسيع عدد أقل من العقد بشكل تعسفي مقارنة بخوارزمية A* في بعض المشكلات غير المرضية.

تتعلق الكفاءة المثلى بمجموعة العقد الموسعة، وليس عدد توسعات العقد (عدد تكرارات الحلقة الرئيسية لـ A*). عندما تكون القاعدة المستخدمة مقبولة ولكنها غير متسقة، فمن الممكن أن يتم توسيع العقدة بواسطة A* عدة مرات، وهو عدد أسي من المرات في أسوأ الحالات. ^[14] في مثل هذه الظروف، يمكن لخوارزمية ديكسترا أن تتفوق على A* بهامش كبير. ومع ذلك، وجدت الأبحاث الأحدث أن هذه الحالة المرضية تحدث فقط في بعض المواقف المصطنعة حيث يكون وزن حافة الرسم البياني للبحث أسيًا في حجم الرسم البياني وأن بعض القواعد غير المتسقة (ولكن المقبولة) يمكن أن تؤدي إلى انخفاض عدد توسعات العقد في عمليات البحث A*. ^{[15] [16]}

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

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

• الترجيح A*/الترجيح الثابت. ^[17] إذا كانت h _a ( n ) دالة استدلالية مقبولة، ففي النسخة المرجحة من بحث A*، يستخدم المرء h _w ( n ) = ε h _a ( n ) ، ε > 1 كدالة استدلالية، وينفذ بحث A* كالمعتاد (والذي يحدث في النهاية بشكل أسرع من استخدام h _a نظرًا لأن عدد العقد المتوسعة أقل). وبالتالي، يمكن أن يكون للمسار الذي تم العثور عليه بواسطة خوارزمية البحث تكلفة لا تزيد عن ε مرة تكلفة المسار الأقل تكلفة في الرسم البياني. ^[18]
• يستخدم الترجيح الديناميكي ^[19] دالة التكلفة ⁠ ⁠${\displaystyle f(n)=g(n)+(1+\varepsilon w(n))h(n)}$ ، حيث ، وحيث ⁠ ⁠ هو عمق البحث و N هو الطول المتوقع لمسار الحل.${\displaystyle w(n)={\begin{cases}1-{\frac {d(n)}{N}}&d(n)\leq N\\0&{\text{خلافًا لذلك}}\end{cases}}}$${\displaystyle d(n)}$
• يستخدم الترجيح الديناميكي للعينات ^[20] أخذ عينات من العقد لتقدير الخطأ الاستدلالي وإزالة التحيز منه بشكل أفضل.
• ${\displaystyle A_{\varepsilon }^{*}}$^[21] يستخدم دالتين استدلاليتين . الأولى هي قائمة FOCAL، والتي تستخدم لاختيار العقد المرشحة، والثانية h _F تستخدم لاختيار العقدة الأكثر وعدًا من قائمة FOCAL.
• يختار A _ε ^[22] العقد باستخدام الدالة ⁠ ⁠${\displaystyle Af(n)+Bh_{F}(n)}$ ، حيث A و B ثابتان. إذا لم يكن من الممكن تحديد أي عقد، فستعود الخوارزمية إلى الوراء باستخدام الدالة ⁠ ⁠${\displaystyle Cf(n)+Dh_{F}(n)}$ ، حيث C و D ثابتان.
• تحاول AlphA* ^[23] تعزيز استغلال العمق أولاً من خلال تفضيل العقد الموسعة حديثًا. تستخدم AlphA* دالة التكلفة ، حيث ، حيث λ و Λ ثابتان مع ، و π ( n ) هو الأصل لـ n ، و ñ هي العقدة الموسعة مؤخرًا.${\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{خلاف ذلك}}\end{cases}}}$${\displaystyle \lambda \leq \لامدا }$

تعتمد التعقيد الزمني لـ A* على الخوارزمية. في أسوأ حالة لمساحة بحث غير محدودة، يكون عدد العقد الموسعة أسيًا في عمق الحل (أقصر مسار) d : O ( b ^d ) ، حيث b هو عامل التفرع (متوسط ​​عدد الخلفاء لكل حالة). ^[24] يفترض هذا أن حالة الهدف موجودة على الإطلاق، ويمكن الوصول إليها من حالة البداية؛ إذا لم تكن كذلك، وكانت مساحة الحالة غير محدودة، فلن تنتهي الخوارزمية.

إن الدالة الاستدلالية لها تأثير كبير على الأداء العملي للبحث A*، حيث تسمح الدالة الاستدلالية الجيدة لـ A* بإزالة العديد من العقد b ^d التي قد يتوسعها البحث غير المستنير. ويمكن التعبير عن جودتها من حيث عامل التفرع الفعال b * ، والذي يمكن تحديده تجريبيًا لحالة مشكلة من خلال قياس عدد العقد الناتجة عن التوسع، N ، وعمق الحل، ثم حل ^[25]

${\displaystyle N+1=1+b^{*}+(b^{*})^{2}+\dots +(b^{*})^{d}.}$

تعتبر الطرق الجيدة هي تلك التي تحتوي على عامل تفرع فعال منخفض (يكون الأمثل هو b * = 1 ).

تكون التعقيدات الزمنية متعددة الحدود عندما تكون مساحة البحث عبارة عن شجرة، وتوجد حالة هدف واحدة، وتلبي الدالة الاستدلالية h الشرط التالي:

${\displaystyle |h(x)-h^{*}(x)|=O(\log h^{*}(x))}$

حيث h ^* هي الطريقة المثلى، وهي التكلفة الدقيقة للوصول من x إلى الهدف. بعبارة أخرى، لن ينمو خطأ h بشكل أسرع من لوغاريتم "الطريقة المثالية" h ^* التي تعيد المسافة الحقيقية من x إلى الهدف. ^{[18] [24]}

إن تعقيد الفضاء لـ A* هو تقريبًا نفس تعقيد جميع خوارزميات البحث البياني الأخرى، حيث يحتفظ بجميع العقد المولدة في الذاكرة. ^[1] في الممارسة العملية، تبين أن هذا هو أكبر عيب في بحث A*، مما أدى إلى تطوير عمليات بحث استدلالية محدودة بالذاكرة، مثل التعميق التكراري A* ، وA* المحدودة بالذاكرة، و SMA* .

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

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

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

A* يشبه البحث الشعاعي إلا أن البحث الشعاعي يحافظ على حد لعدد المسارات التي يتعين عليه استكشافها. ^[30]

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

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

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

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

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

Original text

Rate this translation

Your feedback will be used to help improve Google Translate