خوارزمية البحث النجمي (*A) هي خوارزمية تهدف إلى تحديد أفضل مسار من عقدة إلى أخرى، لذا تشبه إلى حد ما خوارزميات البحث بالوسع أولًا Breadth First Search أو Dijkstra أو "البحث بالعمق أولًا Depth First Search" أو "خوارزمية البحث بالتخمين Best First Search".
تتميّز خوارزمية البحث النجمي بكفاءة ودقة عالية خاصّة في الحالات التي يتعذّر فيها معالجة المخطط معالجة مُسبقة، وهي حالة خاصّة من خوارزمية البحث بالتخمين Best First Search، مع تعريف دالة التقييم f بطريقة معيّنة، إذ تساوي f(n) = g(n) + h(n) الكلفة الدنيا، حيث تمثّلg (n) التكلفة الدنيا من العقدة الأولية إلى n، فيما تمثّل h (n) الكلفة الدنيا من n إلى أقرب هدف من n.
وتقوم خوارزمية *A على التخمين، وتضمن دائمًا العثور على أقصر مسار -المسار الذي له أقل تكلفة- في أقل وقت ممكن، لذلك فهي مثالية. يوضح الرسم البياني التالي آلية العمل لها:
خوارزمية البحث عن المسارات *A عبر متاهة لا تحتوي على عقبات
انظر الشبكة التالية:
لنفترض أنّ هذه متاهة، لاحظ أنّه لا توجد فيها أيّ جدران أو عوائق، وإنما لدينا نقطة انطلاقٍ -المربع الأخضر- ونقطة وصول ممثلة في المربع الأحمر. لنفترض أيضًا أنّه لا يمكننا التحرك قطريًا diagonally من أجل الانتقال من المربّع الأخضر إلى المربع الأحمر.
يبيّن الرسم التالي المربعات التي يمكننا الانتقال إليها بدءًا من المربع الأخضر، والتي سنصبغُها باللون الأزرق.
من أجل اختيار المربع التالي، نحتاج إلى مراعاة بعض المقاييس، وهي الآتية:
- قيمة g - تمثّل بُعد هذه العقدة عن المربع الأخضر.
- قيمة h - تمثّل بُعد هذه العقدة عن المربع الأحمر.
- قيمة f - تساوي مجموع قيمتي g وh. هذا هو العدد النهائي الذي سنستعين به لتحديد العقدة التي ينبغي أن ننتقل إليها.
لحساب هذه القيم، سنستخدم هذه الصيغة:
distance = abs(from.x - to.x) + abs(from.y - to.y)
تُعرَف هذه الصيغة بصيغة مسافة مانهاتن Manhattan Distance formula، حيث نستخدم الصيغة أعلاه لحساب قيمة g الخاصّة بالمربع الأزرق الموجود على يسار المربع الأخضر: abs(3 - 2) + abs(2 - 2 ) = 1، ونحصل على القيمة 1. سنحاول الآن حساب قيمة h بنفس الصيغة: abs(2 - 0) + abs (2 - 0) = 4. قيمة f تساوي 1 + 4 = 5، لذا فإنّ القيمة النهائية لهذه العقدة تساوي 5.
علينا فعل نفس الأمر مع جميع المربعات الزرقاء الأخرى. يمثّل الرقم الكبير في وسط المربعات في الرسم أدناه قيمة f، بينما يمثّل العدد الموجود أعلى اليسار قيمة g، ويمثّل العدد الموجود أعلى اليمين قيمة h.
لقد حسبنا قيم g وh وf الخاصّة بجميع العُقد الزرقاء. الآن، أيّها نختار؟ سنختار العقدة التي لها أصغر قيمة لـ f.
لدينا في هذه الحالة عقدتان لهما نفس قيمة f (هذه القيمة تساوي 5)، كيف نختار من بينهما؟ إمّا أن تختار إحداهما عشوائيًا، أو تضع قواعد للأولويات.
فمثلا، يمكن أن تحدّد قاعدة للأولويات من قبيل: أيمن > أسفل > أيسر > أعلى. لو طبّقنا هذه القاعدة على مثالنا، فإنّ إحدى العقدتين التي تساوي قيمة f الخاصة بها 5 تذهب إلى أسفل، وتذهب الأخرى إلى اليسار. وبما أن أولوية الاتجاه الأسفل أكبر من أولوية اليسار (أسفل>أيسر)، فسنختار المربع الذي يأخذنا إلى أسفل.
سنلوّن المربعات التي حسبنا قيمها دون أن نتحرّك إليها باللون البرتقالي، ونلوّن العقدة التي اخترناها باللون الأزرق السماوي:
سنحسب الآن نفس المقاييس التي حسبناها من قبل للعقد المحيطة بالعقدة ذات اللون الأزرق السماوي (التي اخترناها سابقًا):
سنختار العقدة الموجودة أسفل العقدة السماوية، ذلك أنّ جميع الخيارات لها نفس قيمة f:
لنحسب الآن مقاييس الجار الوحيد للعقدة السماوية:
نتّبع نفس النمط الذي اتبعناه من قبل:
سنحسب مرّةً أخرى مقاييس جار العقدة:
دعنا ننتقل إلى هناك:
أخيرًا وصلنا إلى المربع المنشود، وأنهينا المهمّة.
حل لغز باستخدام خوارزمية البحث النجمي *A
لغز الثمانية 8 puzzle هي لعبة بسيطة تُلعب على شبكة تحتوي 9 مربعات (3 × 3). إحدى هذه المربعات فارغة، والهدف هو نقل المربعات إلى أن تتصافّ الأرقام وفق الترتيب المُراد.
تريد هذه اللعبة البحث عن المسار الأقل كلفة، والذي ينطلق من حالة أولية للعبة ألغاز الثمانية، ويصل إلى الحالة المنشودة.
اقتباسمثلا: لتكن هذه هي الحالة الأولية التي سنبدأ منها.
_ 1 3 4 2 5 7 8 6
وهذه هي الحالة النهائية التي نريد الوصول إليها:
1 2 3 4 5 6 7 8 _
لنحسب مسافة مانهاتن بين الحالة الحالية والحالة النهائية.
h(n) = | x - p | + | y - q |
x وy يمثّلان إحداثيات co-ordinates الحالة الراهنة، فيما تمثّل p وq إحداثيات الحالة النهائية.
تحقّق دالة التكلفة الإجمالية f(n) الشرط التالي:
f(n) = g(n) + h(n)
حيث تمثّل g كلفة الوصول إلى الحالة الراهنة انطلاقًا من حالة أولية معيّنة، ولحل المشكلة سنحسب أولًا مسافة مانهاتن المطلوبة للوصول إلى الحالة النهائية انطلاقًا من الحالة الأولية. ستساوي دالة التكلفة g (n) = 0، لأنّنا ما نزال عند الحالة الأولية:
h(n) = 8
لو نظرت إلى الحالة الأولية ستلاحظ أنّ 1 موجود على بعد مربّع واحد على يمين المكان الذي يُفترض أن يكون فيه عند الوصول إلى الحالة المنشودة، وينطبق الأمر ذاته على 2 و5 و6. توجد _ على مسافة مربعين أُفقيين ومربّعين عموديين، لذا فإن القيمة الإجمالية لـ h(n) هي 1 + 1 + 1 + 1 + 2 + 2 = 8، بينما تساوي دالة التكلفة الإجمالية f(n) القيمة 8 + 0 = 8.
والآن نكون قد عثرنا على الحالات المحتملة التي يمكن الوصول إليها انطلاقًا من الحالة الأولية، كما أنّه لا يمكننا تحريك _ إلّا إلى اليمين أو إلى الأسفل، لذا فإنّ الحالات التي يمكن الوصول إليها بعد التحريك هي:
1 _ 3 4 1 3 4 2 5 _ 2 5 7 8 6 7 8 6 (1) (2)
مرّةً أخرى، سنحسب دالة التكلفة الإجمالية لهذه الحالات كما فعلنا أعلاه، وسنجد أنها تساوي 6 و7 على التوالي. لقد اخترنا الحالة ذات التكلفة الأقل، وهي الحالة (1).
النقلة المحتملة التالية يمكن أن تكون إمّا يسارًا أو يمينًا أو لأسفل. لن ننتقل إلى اليسار لأنّنا كنّا هناك سابقًا، لذا بقي لنا التحرك يمينًا أو إلى أسفل.
ومرّةً أخرى، وجدنا الحالات التي يمكن الوصول إليها من (1).
1 3 _ 1 2 3 4 2 5 4 _ 5 7 8 6 7 8 6 (3) (4)
دالة تكلفة (3) تساوي 6، فيما تساوي دالة تكلفة (4) القيمة 4. خذ بالحسبان أيضًا (2) التي حصلنا عليها من قبل، والتي تساوي دالة تكلفتها 7، وهنا سنختار الحالة (4) لأن لها أقل تكلفة. يمكن أن تكون النقلات المحتملة التالية إمّا يسارًا أو يمينًا أو لأسفل.
سنحصل على الحالات التالية:
1 2 3 1 2 3 1 2 3 _ 4 5 4 5 _ 4 8 5 7 8 6 7 8 6 7 _ 6 (5) (6) (7)
تكاليف الحالات (5) و(6) و(7) تساوي 5 و2 و4 على الترتيب، كذلك لدينا حالتان سابقتان (3) و(2) ذواتا تكلفتين 6 و7 على الترتيب، لكننا سنختار الحالة (6) ذات التكلفة الأقل. يمكن أن تكون التحركات المحتملة التالية إما إلى أعلى أو أسفل، ولا يحتاج الأمر إلى تفكير طويل، إذ سيقودنا النزول إلى أسفل إلى الحالة النهائية، وهذا سيجعل مسافة مانهاتن تساوي 0.
ترجمة -بتصرّف- للفصلين 13 و 12 من كتاب Algorithms Notes for Professionals.
أفضل التعليقات
لا توجد أية تعليقات بعد
انضم إلى النقاش
يمكنك أن تنشر الآن وتسجل لاحقًا. إذا كان لديك حساب، فسجل الدخول الآن لتنشر باسم حسابك.