الخوارزميـــــــــــــــــــــــة

الخوارزمية

1. نبدأ بالقائمة OPEN تحتوي فقط على عقدة للحالة الابتدائية قيمتها للدالة g صفر, إذن قيمة الدالة 'f هي 0 +'h أو فقط 'h , و القائمة CLOSED تكون خالية من العقد.
2. إلى أن نجد العقدة للحالة الهدف نكرر الإجراء التالي:

* نختار العقدة في القائمة OPEN ذات القيمة الأدنى للدالة 'f و نسميها العقدة الأفضل (BESTNODE) ثم ننقلها من القائمة OPEN إلى القائمة CLOSED.
* نفحص إن كانت BESTNODE هي العقدة الهدف, فإن كانت وجدنا الحل و إلا نولد العقدة التابعة (SUCCESSOR) لها.
* لكل عقدة تابعة نقوم بالآتي:

1. نجعل SUCCESSOR تشير رجعياً إلى BESTNODE , و هذه الإشارة ستساعد في استرجاع الطريق إن وجدنا العقدة الهدف.
2. نحسب g(SUCCESSOR) = g(BESTNODE) + the cost from BESTNODE to SUCCESSOR أي التكلفة للوصول لSUCCESSOR هو مقدار التكلفة BESTNODE إضافة للتكلفة من BESTNODE إلى SUCCESSOR .
3. إن كانت SUCCESSOR موجودة في القائمة OPEN , أي مولدة و لكن لم يتم توليد عقد منها , نسمي العقدة الموجودة في القائمة ب OLD و نقارن بين OLD و طريق الوصول إليها و بين SUCCESSOR و طريق الوصول إليها من BESTNODE ,أي نقارن قيمة g لكل منهما فإن كانت (g(OLD أقل لا نفعل شيئاً و إن كانت (g(SUCCESSOR أقل نجعل الرابط الرجعي ل OLD يشير إلى BESTNODE و نجعل القيمة الأدنى محفوظة في (g(OLD و نعدل قيمة (f'(OLD .
4. إن لم تكن SUCCESSOR في القائمة OPEN نرى أن كانت موجودة في CLOSED , أي تم فحصها سابقاً و إن كانت موجودة نسميها OLD و نكرر عملية المقارنة بين SUCCESSOR و OLD . هنا علينا أن ننقل التعديلات إلى توابع OLD و هذا معقد لأن OLD تشير إلى توابعها و التوابع بدورهم يشيرو إلى توابعهم إلى أن ينتهي كل فرع عند عقدة في القائمة OPEN لديها قيمة g مكافئة أو أقل أو أن لا يكون لديها توابع إي نستخدم خوارزمية المسح بأولوية العمق عند العقدة OLD و نغير قيمة g و 'f لكل عقدة نمر بها. بهذه الطريقة كل رابط رجعي لعقدة يشير إلى أفضل عقدة سابقة , و من انتشار قيمة g باتجاه الأسفل أصبح من الممكن أن يصبح الطريق الذي نتبعه أفضل من الطريق من خلال العقدة السابقة الحالية فإن كانت الحالة هكذا نغير العقدة السابقة و نكمل المسح.