خوارزمية البحث بتفضيل الأولية
المحتويات

في البداية، 'خوارزمية البحث بتفضيل الأولية، هي تبسيط عن خوارزمية *A التي قدمها بيتر هارت في العام 1968. تستعمل هذه الخوارزمية الأدوات التالية:
ومن ناحية أخرى، قائمة (OPEN) للعقد التي ولدت وطبقت دالة الكشف (Heuristic Function) عليها ولكن لم تفحص بعد أي لم يتم توليد عقد تابعة منها. هذه القائمة هي من نوع صف تفضيل للأولوية (Priority Queue) حيث العقد ذات القيم الأعلى في دالة الكشف لها أولوية أكبر.
وعلى صعيد آخر، الدالة 'h التي تخمن التكلفة الإضافية للوصول من العقدة الحالية إلى العقدة الهدف. هي إذن قياس لتكلفة الوصول للحل أي العقد الأفضل تأخذ قيماً دنيا والعقد الأسوء تأخذ قيماً عليا، وليست قياس لجودة العقد أي العقد الأفضل تأخذ قيماً أعلى.
من جانب آخر، الدالة 'f التي تعرف كحاصل جمع للدالتين السابقتين أي ('g + h) و قيمتها إذن تمثل تخمين للوصول من الحالة الابتدائية إلى الحالة الهدف عن طريق العقدة الحالية.
من جانب آخر، دالة الكشف (Heuristic Function) التي تخمن أحقية كل عقدة يتم توليدها. هذه الدالة تمكن الخوارزمية من البحث في الطرق الواعدة في الوصول للهدف أولاً.
في هذا الإطار، قائمة (CLOSED) للعقد التي فحصت وتم توليد العقد التابعة منها. هذه القائمة تبقى في الذاكرة لفحصها عند توليد عقد جديدة لمعرفة إن كانت مولدة سابقاً وتم المرور بها.
من جانب آخر، الدالة g التي تقيس التكلفة للوصول من العقدة الابتدائية إلى العقدة الحالية. هذه الدالة تعطي قيم حقيقية وليست تقدير.
ملاحظات على الخوارزمية
وفي السياق ذاته، الخوارزمية يمكن أن تمثل في أفضل حالة إذا طبقت باستعمال السم البياني (GRAPHS) , و يمكن أن تكون تبسط بتطبيق الرسم الشجري (TREES)إن لم نقم بفحص إذا ما كانت العقدة الجديدة في قائمة OPEN أو CLOSED, هذا يجعل توليد العقد أسرع ولكن يمكن أن ينتج عن توالي البحث عدة مرات إذا تكررت العقد.
في هذا الإطار، المسافة من عقدة إلى الهدف الذي يقدر عن طريق الدالة 'h يعتمد على خوارزمية التخمين، فإن كانت القيمة أقرب للحقيقة فإن الخوارزمية ستلتقي حالاً بالهدف بطريقة مباشرة ولكن كلما ابتعدت 'h عن الواقع أي أصبحت قيمتها 0 اعتمد البحث أكثر على قيمة g. فإن كانت قيمة g هي ,0 أصبحت استيراجية البحث عشوائية. و إن كانت دائماً 1, أصبح البحث بأولوية العمق. أما إن كانت قيمة 'h معتدلة فإن طريقاً أمثل للهدف سيكتشف.
إضافةً إلى ذلك، إن دور الدالة g يدعنا نختار أي عقدة نتوسع لاحقًا ليس فقط على أساس قيمة 'h بل كذلك على جودة الطريق إلى العقدة كان، فإن أردنا إيجاد الحل بأقل عدد من الخطوات نضع التكلفة من الانتقال من عقدة إلى عقدة كثوابت، وإن أردنا إيجاد الطريق الأرخص وكانت التكلفة مختلفة للانتقال من عقدة إلى أخرى فعلينا أن نأخذ هذه القيم بالاعتبار. إذن يمكن استخدام هذه الخوارزمية إن كنا مهتمين لإيجاد الطريق الأكثر تكلفة أو الأسرع وصولاً.
الخوارزمية
وعلى صعيد آخر، نبدأ بالقائمة OPEN تحتوي فقط على عقدة للحالة الابتدائية قيمتها للدالة g صفر، إذن قيمة الدالة 'f هي 0 +'h أو فقط 'h , و القائمة CLOSED تكون خالية من العقد.
إلى أن نجد العقدة للحالة الهدف نكرر الإجراء التالي:
ومن ناحية أخرى، إن لم تكن SUCCESSOR في القائمة OPEN نرى أن كانت موجودة في CLOSED , أي تم فحصها سابقاً وإن كانت موجودة نسميها OLD و نكرر عملية المقارنة بين SUCCESSOR و OLD . هنا علينا أن ننقل التعديلات إلى توابع OLD و هذا معقد لأن OLD تشير إلى توابعها والتوابع بدورهم يشيرو إلى توابعهم إلى أن ينتهي كل فرع عند عقدة في القائمة OPEN لديها قيمة g مكافئة أو أقل أو أن لا يكون لديها توابع إي نستعمل خوارزمية المسح بأولوية العمق عند العقدة OLD و نغير قيمة g و 'f لكل عقدة نمر بها. بهذه الطريقة كل رابط رجعي لعقدة يشير إلى أفضل عقدة سابقة، ومن انتشار قيمة g باتجاه الأسفل أصبح من الممكن أن يصبح الطريق الذي نتبعه أفضل من الطريق من خلال العقدة السابقة الحالية فإن كانت الحالة هكذا نغير العقدة السابقة ونكمل المسح.
وفي هذا الصدد، نفحص إن كانت BESTNODE هي العقدة الهدف، فإن كانت وجدنا الحل وإلا نولد العقدة التابعة (SUCCESSOR) لها.
ومن ناحية أخرى، نجعل SUCCESSOR تشير رجعياً إلى BESTNODE , و هذه الإشارة ستساعد في استرجاع الطريق إن وجدنا العقدة الهدف.
كذلك، نحسب g(SUCCESSOR) = g(BESTNODE) + the cost from BESTNODE to SUCCESSOR أي التكلفة للوصول لSUCCESSOR هو مقدار التكلفة BESTNODE إضافة للتكلفة من BESTNODE إلى SUCCESSOR .
وعلى صعيد آخر، إن كانت SUCCESSOR موجودة في القائمة OPEN , أي مولدة ولكن لم يتم توليد عقد منها، نسمي العقدة الموجودة في القائمة ب OLD و نقارن بين OLD و طريق الوصول إليها وبين SUCCESSOR و طريق الوصول إليها من BESTNODE ,أي نقارن قيمة g لكل منهما فإن كانت (g(OLD أقل لا نفعل شيئاً وإن كانت (g(SUCCESSOR أقل نجعل الرابط الرجعي ل OLD يشير إلى BESTNODE و نجعل القيمة الأدنى محفوظة في (g(OLD و نعدل قيمة (f'(OLD .
من جانب آخر، نختار العقدة في القائمة OPEN ذات القيمة الأدنى للدالة 'f و نسميها العقدة الأفضل (BESTNODE) ثم ننقلها من القائمة OPEN إلى القائمة CLOSED.
لكل عقدة تابعة نقوم بالآتي:
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟