ذكاء صنعي

07/03/2012 19:30:22

استخدام خوارزمية البحث *A لإيجاد المسار الأقصر والخالي من العوائق

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

مكونات الخوارزمية:
1- مناطق البيئة التي تعمل عليها A* .
كل منطقة لها احداثيات تمثلها على الخريطة نفترض انها x وy اذا اخذنا
بالإعتبار انها ثنائية الأبعاد .اذا المنطقة تتكون من خمسة معاليم مهمة في عملية البحث …
     أ‌- القيمة g وتعني موقع هذه المنطقة عن
منطقة البداية نأخذ بعين الإعتبار الحواجز في منطقة البداية تأخذ g     القيمة 0.
     ب‌- القيمة h وتعني موقع المنطقة عن الهدف متجاهلةالحواجز في منطقة النهاية تأخذ h القيمة 0 .
     ت‌- القيمة f وتساوي g+h والمنطقة الأقل قيمة هي الأولى باختبارها اولا .
     ث‌- القيمة From او Parent لك الحرية في تسميته وتعني المنطقة التي اتيت منها الى هذه المنطقة .
     ج‌- القيمة pos او place لإحداثيات المنطقة.
2- منطقة البداية .
3- منطقة النهاية.
4- الحواجز.



ملاحظة: جميع صور الشرح مأخوذة من برنامج قمت بتصميمه بواسطة Qt .

اللون الأسود للحواجز والأخضر للبداية والأصفر للنهاية والخلايا المربعة عبارة عن مناطق


احداثياتها من الطرف الأيسر العلوي (0,0) وتزدادا بمقدار واحد عند تحركنا لليمين او للأسفل .



كيف تعمل الخوارزمية:

تبدأ عملية البحث من نقطة البداية وتتحرك باربع اتجاهات شمال جنوب شرق غرب


1 – هناك قائمتان openList و closedList


openList تحتوي على المناطق التي لم يتم اختبارها أي لم تتفرع منها مناطقها


المجاورة لها و closedList تحتوي على المناطق التي تم اختبارها أي تفرعت منها المناطق المجاورة لها .


2- ثم نضيف منطقة البداية الى openList .


3- تبدأ عملية التكرار while مادامت تتوفر مناطق في openList


     أ‌- البحث عن أقل قيمة ل f في المناطق المتوفرة في openList


ملاحظة:في البداية لن تتوفر الا منطقة البداية لذا سوف يتم إختيارها .


     ب‌- نجعل المنطقة التي قيمة f لها هي الأقل (الخطو أ)


المنطقة الحالية currentRegion ونضعها في closedList ونحذفها من openList .


     ت‌- التأكد من ان المنطقة الحالية currentRegion هي


منطقة النهاية في حال كانت ليست هي منطقة النهاية نكمل وإلا فإننا نتتبع سلسلة from للمناطق


لنرسل قائمة بالمناطق التي نمر بها والتي تعتبر الأقصر والتي ليست بها حواجز .


     ث‌- نبحث عن الجيران للمنطقة الحالية بحيث لايكون الجار عبارة عن حاجز


وان لايكون في القائمة المغلقة closedList وفي حال كان في القائمة المفتوحة نضيف اليها


معلومات g و h و f ونجعل قيمة From تشير الى المنطقة الحالية


واذا كان غير متوفر في القائمة openList نضيفه الى القائمة ونضع له المعلومات g و h و f


ونجعل قيمة From تشير الى المنطقة الحالية .





     ج‌- نرجع لبداية التكرار

أمور خفية :
1- سوف تشمل عملية البحث مناطق مغلقة ومناطق بعيدة والمسار الذي يصل اول الى منطقة النهاية
هو الأقرب لذلك تم ايجاد القيمة From لتصلنا الى المسار الأقصر للمنطقة التي نفذنا منها الى منطقة النهاية.




لاحظ في هذه الرسمة لقد شملت عملية البحث جميع المناطق (ليس هذا دائما مايحدث)


حتى لامسنا خط النهاية ثم تتبعنا القيمة From بالشكل التالي من النهاية(المنطقة الحالية بالنسبة للتطبيق الفعلي)


الى البداية .




للحصول على الكود يمكنكم زيارة المدونة

http://www.al-dwal.org/?p=119


مشاركة/حفظ

الكاتب:

مصدر الخبر: http://www.al-dwal.org/?p=119

عودة عودة إلى ذكاء صنعي عودة عودة إلى الصفحة الرئيسية طباعة طباعة إرسال إلى صديق إرسال إلى صديق

التعليقات

ليس هناك تعليقات حتى الآن، كن أول من يضيف تعليقاً

أضف تعليق


تصنيفات الموقع