• 0
مصفوفة

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

سؤال

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

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

ولتسهيل عملية البحث يجب تقسيم المنطقة او الأرضية التي تبحث فيها الخوارزمية الى مناطق ويفضل ان تكون مربعة والأمر راجع اليك .

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

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

1- مناطق البيئة التي تعمل عليها A* .

كل منطقة لها احداثيات تمثلها على الخريطة نفترض انها x وy اذا اخذنا بالإعتبار انها ثنائية الأبعاد بالإضافة الى الإحداثيات فإنها تتكون من ثلاث معاليم مهمة في عملية البحث …

أ‌- القيمة g وتعني موقع هذه المنطقة عن منطقة البداية نأخذ بعين الإعتبار الحواجز في منطقة البداية تأخذ g القيمة 0.

ب‌- القيمة h وتعني موقع المنطقة عن الهدف متجاهلة الحواجز في منطقة النهاية تأخذ h القيمة 0 .

ت‌- القيمة f وتساوي g+h والمنطقة الأقل قيمة هي الأولى باختبارها اولا .

ث‌- القيمة From او Parent لك الحرية في تسميته وتعني المنطقة التي اتيت منها الى هذه المنطقة .

ج‌- القيمة pos او place لإحداثيات المنطقة.

2- منطقة البداية .

3- منطقة النهاية.

4- الحواجز.

11987309.jpg

ملاحظة: جميع صور الشرح مأخوذة من برنامج قمت بتصميمه بواسطة 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 تشير الى المنطقة الحالية .

82515587.jpg

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

أمور خفية :

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

79000954.jpg

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

32627200.jpg

الشيفرة الفعلية للخوارزمية في البرنامج الذي أخذنا منه الصور الشيفرة الفعلية للخوارزمية في البرنامج الذي أخذنا منه الصور وسوف اضع الشيفرة المصدرية للبرنامج كاملا في وقت لاحق بإذن الله


QList<NodeItem*> Widget::AStar()
{
QList<NodeItem*> openList;
QList<NodeItem*> closedList;
openList<<Start;
while(openList.count()) {
int mini=0;
NodeItem* currentNode;
for(int i=0;i<openList.count();i++)
{
if(openList.at(i)->F<openList.at(mini)->F)
mini=i;
}
currentNode=openList.at(mini);
if(currentNode==End)
{
NodeItem* cu=currentNode;
QList<NodeItem*> Nodes;
while(cu->From)
{
Nodes<<cu->From;
cu=cu->From;
}
Nodes.removeAt(Nodes.length()-1);
return Nodes;
}
openList.removeOne(currentNode);
closedList<<currentNode;
QList<NodeItem*> jeeran=getJeerans(currentNode);
for(int i=0;i<jeeran.count();i++)
{
NodeItem* nn=jeeran.at(i);
if(closedList.contains(nn))continue;
int g=currentNode->G+1;
bool gm=0;
if(!openList.contains(nn))
{
gm=true;
nn->H=abs(End->getPlace().x()-nn->getPlace().x())+
abs(End->getPlace().y()-nn->getPlace().y());
openList<<nn;
}
else if(g<nn->G)
{
gm=true;
}
if(gm)
{
nn->From=currentNode;
nn->G=g;
nn->F=nn->G+nn->H;
}
}


}
QList<NodeItem*> v; return v;
}
QList<NodeItem*> Widget::getJeerans(NodeItem* from)
{
QList<NodeItem*> nodes;
int x=from->getPlace().x();
int y=from->getPlace().y();
foreach(NodeItem* n,this->NIS)
{
if(n->getPlace()==QPoint(x+1,y))
{
if(n->isEmpty())
nodes<<n;
}
if(n->getPlace()==QPoint(x-1,y))
{
if(n->isEmpty())
nodes<<n;
}
if(n->getPlace()==QPoint(x,y+1))
{
if(n->isEmpty())
nodes<<n;
}
if(n->getPlace()==QPoint(x,y-1))
{
if(n->isEmpty())
nodes<<n;
}
}
return nodes;
}

أرحب بأي اضافة للمقال ...

المصدر مدونتي www.al-dwal.org

9

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

8 إجابة على هذا السؤال .

  • 0

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

ولتسهيل عملية البحث يجب تقسيم المنطقة او الأرضية التي تبحث فيها الخوارزمية الى مناطق ويفضل ان تكون مربعة والأمر راجع اليك .

إضافة : الخوارزمية تعمل مع أي مشكلة حتى لو لم تكن " خريطة " كما في هذا المقال ، حيث يمكن أن تقوم بتحويل بعض المشاكل إلى " شجرة من الحالات " States "، و تكون عملية حساب التكلفة Cost بقانون ما ،

فمثلاً في لعبة مثل X/O يمكن حلها بانشاء شجرة من الحالات المتوقعة ثم ايجاد أفضل مسار من جذر الشجرة Initial State حتى الهدف Goal State ، ويمكن حساب التكلفة ، بطرح عدد X من عدد O مثلاً ( مثال اعتباطي طبعاً )

أ‌- القيمة g وتعني موقع هذه المنطقة عن منطقة البداية نأخذ بعين الإعتبار الحواجز في منطقة البداية تأخذ g القيمة 0.

ب‌- القيمة h وتعني موقع المنطقة عن الهدف متجاهلة الحواجز في منطقة النهاية تأخذ h القيمة 0 .

يفضّل أن تضع نقطة بين الجمل حتى لايحدث سوء فهم لدى القارئ :

أ‌- القيمة g وتعني موقع هذه المنطقة عن منطقة البداية نأخذ بعين الإعتبار الحواجز . في منطقة البداية تأخذ g القيمة 0.

ب‌- القيمة h وتعني موقع المنطقة عن الهدف متجاهلة الحواجز . في منطقة النهاية تأخذ h القيمة 0 .

وأخيراً : مقال من أروع مايكون ، بكل ماتحمله هذه الكلمة من معنى .

من بعد إذنك سيتم اضافة الموضوع لفهرس قسم برمجة الألعاب ونقله أيضاً إلى قسم الذكاء الاصطناعي " الجديد " ، وترك وصله له في قسم برمجة الألعاب .

تم تعديل بواسطه الشمري
3

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

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

is a best-first graph search algorithm that finds the least-cost path from a given initial node to one goal node

فإلا عنده ترجمة لها الله يجزاه خير او تعريف أكاديمي آخر حتى اضيفها للمقال

وشكرا لك .

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

نقلت الموضوع هنا ، حيث يمكن أن تحصل على تعليقات أفضل من أهل الذكاء :-) .

مع العلم أنه سيتم اضافة الموضوع لفهرسة قسم برمجة الألعاب أيضاً ، تحت بند الذكاء الاصطناعي .

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

جهد جميل اخي مصفوفه بارك الله بك .. وعلى فكره كنت من اوائل الذين اعطوك +1 smile.gifblush.gif

ومشكور اخي الشمري على النقل .... وادعمنا دائما smile.gif

فإلا عنده ترجمة لها الله يجزاه خير او تعريف أكاديمي آخر حتى اضيفها للمقال

اخي العزيز الـــ Best first search يحسن الــ breadth >>> BFS من خلال اصدار اوامر لجميع مسارات العقد الحاليه وفقا لاجراءات وارشادات معينه للوصول الى الهدف , حيث تقوم هذه الارشادات او الاجراءات بمحاولات للتنبؤ بقرب المسارات للحل النهائي , والمسار الذي يحكم عليه بانه افضل واقصر حل للوصول الى الحل المطلوب هو الذي يتم اختياره ... وهذه الاجراءات طبعا بناء على حساب ال cost او المسافات وبناء على القواعد المعطاه ..

ان شاء الله ان تكون وصلت الفكره اخي العزيز ومجهودك مشكور عليه وجعله الله في ميزان حسناتك ..

سبب التعديل :- ارفقت ملف يحتوي على العديد من الخوازميات التي قد تفيد ان شاء الله ومن ضمنها A* و BFS و DFS وغيرها ..

all.pdf

تم تعديل بواسطه ( HASSAN )
2

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

شكرا جزيلا لك استاذ حسن.

يعطيك العافية على الملف كنت بحاجة لملف مثله +1 :) .

تم تعديل بواسطه مصفوفة
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

+1

مشكور اخوي ويا ليث تضع الكود كامل من فضلك :happy:

تحياتي الك

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

بسم الله..

اهنئك على هذا الموضوع :lol: " اول مرة اشوف شرح عربى للموضوع نفسه" وارجو ان ينفع الله به كل من يقرأه....

لدى بعض الإستفسارات عن بعض النقاط اللتى لا أستطيع فهمها

كيف سيتم تطبيق from فى حالة ان الطريق الذى سلكه البحث كانت نهايته مسدودة ..وكيف سيحدد الطريق الأقرب من دون الدخول الى الطريق ذو النهاية المسدودة

هذا كله اولا ..

ثانيا ..انا هعيط عشان افهم الطريقة دى ...شفت فيديوهات وشرح ليها بعدد شعر راسى ... ربنا يستر ومعيدش السنة دى بسببها لاأنها مش مخليانى اعرف اذاكر

شكرا لك

تم تعديل بواسطه احمد أبوسعدة
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .