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

خوارزمية البحث 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 بالشكل التالي من النهاية (المنطقة الحالية بالنسبة للتطبيق الفعلي) الى البداية .

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

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