• 0
مصطفى 36a2

تطبيق خوارزمية Depth First Search لرسم متاهة

سؤال

post-256536-0-12949100-1392204171.png

السلام عليكم ورحمة الله وبركاته

تعتبر خوارزمية Depth First Search أحد الخوارزميات للمرور على جميع النقاط المتصلة connected nodes في مخطط Graph ما ..

لا أريد التكرار فالموضوع عليه الكثير من الشروحات الواضحة على youTube  كما أن صفحة wikipedia فيها شرح ممتاز (وفيديو ملحق لإنشاء متاهة أيضاً :) )

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

تخيل أن هذه شجرة :

post-256536-0-94603100-1392205049.png

هذه الأشجاء التخيلية التي تحوي فروعاً وتقاطعات تُسمّى Graphs (مخططات )

المهم ..

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

هناك عدة طرق يمكننا من خلالها ضمان المرور على جميع الفروع .(المرور على جميع الفروع والتقاطعات(العقد) يُسمّى traversing )

إحداها طريقة Depth first Search

تحتاج لتطبيقها إلى مكدّس ومعرفة بسيطة في الحلقات والشروط .

خوارزمية DFS :

0-نضع الجذر في المكدس

ونبدأ الحلقة طالما أن المكدس غير فارغ :

1- نقوم بوضع علامة على العنصر في قمة المكدس للدلالة على انه قد تمت زيارته

2- نقوم باختبار وجود عناصر مرتبطة بالعنصر الحالي(قمة المكدس ) وهل هي صالحة للزيارة (تكون صالحة للزيارة إن كانت مرتبطة بالعنصر ولم تتم زيارتها من قبل )

3- كل عنصر يحقق الشرط في الخطوة 2 نضعه في المكدس

4- إن لم يحقق أي عنصر الشرط في الخطوة 2 نقوم بإخراج العنصر الحالي من المكدس

5- ان كان المكدس غير فارغ نذهب للخطوة 1

 

لنحول الخوارزمية إلى كود

نحتاج إلى آلية تكديس وسنستعمل std::stack, وآلية loop ويمكن أن نستعمل for  ,

وسنحتاج آلية لإعادة القيام بالعملية على العقدة الجديدة (يمكن أن نستعمل العودية recursion ولكن سنطبق اليوم بواسطة حلقة while)

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

مثال للمصفوفة :

1 2 3

4 5 6

7 8 9

نقول أن 1 مع 4 و 2 مرتبطة , وكذلك :  9 مع 6 و 8 وهكذا

(يمكن لك أن تعتبر وجود ارتباطات بالمائل مثل 5 و 9 ان أردت )

يمكننا وضع علامة على النقطة التي تمت زيارتها ببساطة بتغيير قيمة المصفوفة مثلاً من 0 إلى 1

أخيراً  : نلاحظ أن الخطوة 4 لم تعد تحتاج إلى for loop  لأن العقد المرتبطة في حالة المصفوفة هي 4 كحد أقصى لذلك سنكتبها يدوياً

 

لنبدأ ..على بركة الله

تحويل الخوارزمية إلى كود :

أولا ودوماً أولاً : تطبيق بنية الـGraph

ببساطة مصفوفة يمكن ان تحوي 0 أو 1 .. bool :)

bool graph[30][30]={false};

القيمة false تعني أننا لم نزر أي عقدة بعد .

ثانياً : كيفية الامساك بعقدة ما ..

في حالتنا عن طريق الموضع في المصفوفة

سنكتب  struct بسيط يُمثّل الموضع

struct coord{
    int x;
    int y;
    coord(int x1,int y1){
        x=x1;
        y=y1;
    }
};

ولا ننسى آلية التكديس

stack <coord> s;

والآن  الحلقة التي سنعمل بداخلها الخطوات من 1 إلى 5 , وبها سنتابع بقية العمل , ولكن قبل الدخول إليها علينا دفع الجذر إلى المكدس (أو أي عقدة نرغب في البدء منها )

while(!s.empty()){ }

سنقوم بملء التابع السابق كما توضّح الخوارزمية

 

1-عملية وضع علامة على الفرع الذي تمت زيارته

        graph[s.top().y][s.top().x]=true;

2-اختبار صلاحية زيارة جميع العقد المرتبطة , وبعد انتهاء العقد المرتبطة ( أو عدم وجودها فالأمر سيان ) أخرج العقدة الحالية من stack

سنختبر كل جهة على حدة كما يلي:

//look at left        if(valid(s.top().y,s.top().x-1)){            s.push(coord(s.top().y,s.top().x-1));        }        //look at right        else if(valid(s.top().y,s.top().x+1)){            s.push(coord(s.top().y,s.top().x+1));        }        //look up        else if(valid(s.top().y-1,s.top().x)){            s.push(coord(s.top().y-1,s.top().x));        }        //look down        else if(valid(s.top().y+1,s.top().x)){            s.push(coord(s.top().y+1,s.top().x));        }        else{            s.pop();        }

الكود بصيغته النهائية :

الكود :

أولاً : البنى والتوابع المساعدة

struct coord{    int x;    int y;    coord(int y1,int x1){        x=x1;        y=y1;    }};const int X=10,Y=10;bool graph[Y][X]={false};stack <coord> s;bool valid(int y,int x){    if(x<X&&x>=0)        if(y<Y&&y>=0)            if(graph[y][x]==false)                return true;    return false;}

والتنفيذ في الدالةmain

int main(){    //push the current node    s.push(coord(0,0));    while(!s.empty())    {        graph[s.top().y][s.top().x]=true;        //look at left        if(valid(s.top().y,s.top().x-1)){            s.push(coord(s.top().y,s.top().x-1));        }        //look at right        else if(valid(s.top().y,s.top().x+1)){            s.push(coord(s.top().y,s.top().x+1));        }        //look up        else if(valid(s.top().y-1,s.top().x)){            s.push(coord(s.top().y-1,s.top().x));        }        //look down        else if(valid(s.top().y+1,s.top().x)){            s.push(coord(s.top().y+1,s.top().x));        }        else{            s.pop();        }    }    return 0;}

كي نتابع عملية السير سنكتب تابع بسيط لإظهار المخطط بعد كل تغيير

هذا مثال

void printGraph(){/*Put here any implementation to return the pointer to top left*/        cout << s.size() << " " << s.top().x <<" " <<s.top().y<< endl;    for(int i=0;i<Y;i++)    {        for(int j=0;j<X;j++)        {            cout<<(graph[i][j]?'#':' ');        }        cout <<endl;    }/*Put here any implementation to Sleep for 10-100 milli second*/    }

في ويندوز سأستعمل تابعين من الـ API

void printGraph(){    COORD topLeft={0,0};    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),topLeft);    cout << s.size() << " " << s.top().x <<" " <<s.top().y<< "     " << endl;    for(int i=0;i<Y;i++)    {        for(int j=0;j<X;j++)        {            cout<<(graph[i][j]?' ':'#');        }        cout <<endl;    }    Sleep(30);}

ثم ضع استدعاء التابع داخل حلقة while الخاصة بالخوارزمية

جرب الكود التالي  في ويندوز (++C)

#include<stack>#include<iostream>#include<windows.h>using std::stack;using std::cout;using std::endl;struct coord{    int x;    int y;    coord(int y1,int x1){        x=x1;        y=y1;    }};const int X=10,Y=10;bool graph[Y][X]={false};stack <coord> s;void printGraph(){    COORD topLeft={0,0};    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),topLeft);    cout << s.size() << " " << s.top().x <<" " <<s.top().y<< "     " << endl;    for(int i=0;i<Y;i++)    {        for(int j=0;j<X;j++)        {            cout<<(graph[i][j]?' ':'#');        }        cout <<endl;    }    Sleep(30);}bool valid(int y,int x){    if(x<X&&x>=0)        if(y<Y&&y>=0)            if(graph[y][x]==false)                return true;    return false;}int main(){    //put flag on the visited node    int x=0,y=0;    //push the current node    s.push(coord(x,y));    while(!s.empty())    {        printGraph();        graph[s.top().y][s.top().x]=true;        //look at left        if(valid(s.top().y,s.top().x-1)){            s.push(coord(s.top().y,s.top().x-1));        }        //look at right        else if(valid(s.top().y,s.top().x+1)){            s.push(coord(s.top().y,s.top().x+1));        }        //look up        else if(valid(s.top().y-1,s.top().x)){            s.push(coord(s.top().y-1,s.top().x));        }        //look down        else if(valid(s.top().y+1,s.top().x)){            s.push(coord(s.top().y+1,s.top().x));        }        else{            s.pop();        }    }    return 0;}

 

تجدر الإشارة إلى فكرة هامّة جداً ..

يعتمد المعالج في استدعاء التوابع على مكدّس خاص بالاستدعاءات

ويمكننا الاستغناء عن مكدسنا std::stack والاستعانة بالمكدس الخاص بالاستعداءات

وذلك عن طريق وضع العملية في تابع بدلاً من while , وبدلاً من عملية push سنقوم باستدعاء التابع مرة أخرى , وبمجرد انتهاء التابع أو عمل return  سيتم عمل pop للقيمة الحالية

انظر الكود التالي(أبسط من السابق)

#include<iostream>#include<windows.h>using std::cout;using std::endl;const int X=10,Y=10;bool graph[Y][X]={false};void printGraph(){    COORD topLeft={0,0};    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),topLeft);    for(int i=0;i<Y;i++)    {        for(int j=0;j<X;j++)        {            cout<<(graph[i][j]?' ':'#');        }        cout <<endl;    }    Sleep(30);}bool valid(int y,int x){    if(x<X&&x>=0)        if(y<Y&&y>=0)            if(graph[y][x]==false)                return true;    return false;}void function(int y,int x){    printGraph();    graph[y][x]=true;    //look at left    if(valid(y,x-1)){        //s.push(coord(s.top().y,s.top().x-1));        function(y,x-1);    }    //look at right    if(valid(y,x+1)){        //s.push(coord(s.top().y,s.top().x+1));        function(y,x+1);    }    //look up    if(valid(y-1,x)){        //s.push(coord(s.top().y-1,s.top().x));        function(y-1,x);    }    //look down    if(valid(y+1,x)){        //s.push(coord(s.top().y+1,s.top().x));        function(y+1,x);    }//        s.pop();        return ;}int main(){    function(0,0);    return 0;}

ولكننا خسرنا ميزة تتبع المكدس فلم يعد بإمكاننا مثلاً كتابة

cout << s.size() << " " << s.top().x <<" " <<s.top().y<< "     " << endl;

إذا جربت الكود , فستلاحظ أنه يسير بطريقة عادية ليمر على جميع عناصر المصفوفة , ولكن جرب كتابة

 function(5,5);

وسيبدأ من المنتصف , وعندها ستلاحظ سلوكاً غير متوقع (ربما) في المرور على جميع العناصر .

 

والآن إلى إنشاء المتاهة:

ببساطة سنتحرك خطوتين بدلاً من خطوة واحدة , وبذلك سنترك فراغات تُشكّل الحوائط !

#include<cstdio>#include<windows.h>const int X=21,Y=21;bool graph[Y][X]={false};void printGraph(){    COORD topLeft={0,0};    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),topLeft);    for(int i=0;i<Y;i++)    {        for(int j=0;j<X;j++)        {            putchar(graph[i][j]?' ':'#');        }        putchar('\n');    }}bool valid(int y,int x){    if(x<X&&x>=0)        if(y<Y&&y>=0)            if(graph[y][x]==false)                return true;    return false;}void function(int y,int x){    printGraph();    //look at left    if(valid(y,x-2)){        //s.push(coord(s.top().y,s.top().x-1));        graph[y][x-1]=true;        graph[y][x-2]=true;        function(y,x-2);    }    //look at right    if(valid(y,x+2)){        //s.push(coord(s.top().y,s.top().x+1));        graph[y][x+1]=true;        graph[y][x+2]=true;        function(y,x+2);    }    //look up    if(valid(y-2,x)){        //s.push(coord(s.top().y-1,s.top().x));        graph[y-1][x]=true;        graph[y-2][x]=true;        function(y-2,x);    }    //look down    if(valid(y+2,x)){        //s.push(coord(s.top().y+1,s.top().x));        graph[y+1][x]=true;        graph[y+2][x]=true;        function(y+2,x);    }//        s.pop();        return ;}int main(){    function(5,5);    Sleep(100000);    return 0;}

جرب الكود , وستلاحظ أن المتاهة سهلة جداً  للحل

ولجعلها صعبة وعشوائية سنغير فقط طريقة الرؤية للكود ! ماذا يعني هذا ؟ يعني أن نجعل اختبارات (اليسارواليمين .. ) غير ثابته , فمثلاً يمكن أن نختبر المرور للأسفل قبل اليمين وهكذا ..

لاحظ اختلافات الكود :

#include<cstdio>#include<cstdlib>#include<ctime>#include<windows.h>const int X=31,Y=31;bool graph[Y][X]={false};void printGraph(){    COORD topLeft={0,0};    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),topLeft);    for(int i=0;i<Y;i++)    {        for(int j=0;j<X;j++)        {            putchar(graph[i][j]?' ':'#');        }        putchar('\n');    }}bool valid(int y,int x){    if(x<X&&x>=0)        if(y<Y&&y>=0)            if(graph[y][x]==false)                return true;    return false;}void function(int y,int x){    printGraph();    for(int i=0;i<10;i++){//to ensure passing all valid moves        int dx=0,dy=0;        while(dx^dy==0){            dy=rand()%2;//zero or one            dx=rand()%2;//zero or one        }        if(rand()%2==1)            dx*=-1,            dy*=-1;        if(valid(y+2*dy,x+2*dx)){            //s.push(coord(s.top().y,s.top().x-1));            graph[y+dy][x+dx]=true;            graph[y+2*dy][x+2*dx]=true;            function(y+2*dy,x+2*dx);        }    }        return ;}int main(){    srand(time(0));    function(5,5);    Sleep(100000);    return 0;{

في الختام أود لفت الانتباه إلى أنه من الأمور الهامة جداً عند دراسة الخوارزميات عدم خلط الخورازمية بالتطبيق ,

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

 

والله ولي التوفيق

3

شارك هذا الرد


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

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

  • 0

جزاك الله خيرا .. :)

أحب أن أضيف :

DFS = Stack

BFS  = Breadth First Search = Queue

1

شارك هذا الرد


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

شكراً جزيلاً لك أخ حسام ..

وعلى ذكر الـBFS

هذا كود يبين كيفية تآكل المصفوفة (إن صح التعبير ) عند استخدام BFS

#include<queue>#include<stack>#include<iostream>#include<windows.h>using std::queue;using std::stack;using std::cout;using std::endl;struct coord{    int x;    int y;    coord(int y1,int x1){        x=x1;        y=y1;    }};const int X=20,Y=20;bool graph[Y][X]={false};#define data_structure_queue#ifdef data_structure_stack    stack <coord> s;    #define front top#else    queue <coord> s;#endifvoid printGraph(){    COORD topLeft={0,0};    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),topLeft);    for(int i=0;i<Y;i++)    {        for(int j=0;j<X;j++)        {            putchar(graph[i][j]?' ':'#');        }        putchar(10);    }}bool valid(int y,int x){    if(x<X&&x>=0)        if(y<Y&&y>=0)            if(graph[y][x]==false)                return true;    return false;}int main(){    //put flag on the visited node    int x=0,y=0;    //push the current node    s.push(coord(x,y));    while(!s.empty())    {        printGraph();        graph[s.front().y][s.front().x]=true;        //look at left        if(valid(s.front().y,s.front().x-1)){            graph[s.front().y][s.front().x-1]=true;            s.push(coord(s.front().y,s.front().x-1));        }        //look at right        else if(valid(s.front().y,s.front().x+1)){            graph[s.front().y][s.front().x+1]=true;            s.push(coord(s.front().y,s.front().x+1));        }        //look up        else if(valid(s.front().y-1,s.front().x)){            graph[s.front().y-1][s.front().x]=true;            s.push(coord(s.front().y-1,s.front().x));        }        //look down        else if(valid(s.front().y+1,s.front().x)){            graph[s.front().y+1][s.front().x]=true;            s.push(coord(s.front().y+1,s.front().x));        }else            s.pop();    }    return 0;}

وهذا كود المتاهة البسيطة المولدة باستخدام BFS ( فقط الحلفة while لتوفير الأسطر )

while(!s.empty())    {        printGraph();        graph[s.front().y][s.front().x]=true;        //look at left        if(valid(s.front().y,s.front().x-2)){            graph[s.front().y][s.front().x-1]=true;            graph[s.front().y][s.front().x-2]=true;            s.push(coord(s.front().y,s.front().x-2));        }        //look at right        else if(valid(s.front().y,s.front().x+2)){            graph[s.front().y][s.front().x+1]=true;            graph[s.front().y][s.front().x+2]=true;            s.push(coord(s.front().y,s.front().x+2));        }        //look up        else if(valid(s.front().y-2,s.front().x)){            graph[s.front().y-1][s.front().x]=true;            graph[s.front().y-2][s.front().x]=true;            s.push(coord(s.front().y-2,s.front().x));        }        //look down        else if(valid(s.front().y+2,s.front().x)){            graph[s.front().y+2][s.front().x]=true;            graph[s.front().y+1][s.front().x]=true;            s.push(coord(s.front().y+2,s.front().x));        }else            s.pop();    }

وبجعل ترتيب الاختبارات عشوائياً نصل للمتاهة الحقيقية

#include<queue>#include<stack>#include<iostream>#include<ctime>#include<windows.h>using std::queue;using std::stack;using std::cout;using std::endl;struct coord{    int x;    int y;    coord(int y1,int x1){        x=x1;        y=y1;    }};const int X=20,Y=20;bool graph[Y][X]={false};#define data_structure_queue#ifdef data_structure_stack    stack <coord> s;    #define front top#else    queue <coord> s;#endifvoid printGraph(){    COORD topLeft={0,0};    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),topLeft);    for(int i=0;i<Y;i++)    {        for(int j=0;j<X;j++)        {            putchar(graph[i][j]?' ':'#');        }        putchar(10);    }}bool valid(int y,int x){    if(x<X&&x>=0)        if(y<Y&&y>=0)            if(graph[y][x]==false)                return true;    return false;}int main(){    //put flag on the visited node    int x=0,y=0;    //push the current node    s.push(coord(x,y));    srand(time(0));    while(!s.empty())    {        printGraph();        graph[s.front().y][s.front().x]=true;        bool noValids=true;        for(int i=0;i<10;i++){            int dx=0,dy=0,sign=rand()%2;            while(dx^dy==0){                dx=rand()%2;                dy=rand()%2;            }            if(sign)dx*=-1,dy*=-1;            if(valid(s.front().y+2*dy,s.front().x+2*dx))            {                graph[s.front().y+1*dy][s.front().x+1*dx]=true;                graph[s.front().y+2*dy][s.front().x+2*dx]=true;                s.push(coord(s.front().y+2*dy,s.front().x+2*dx));                noValids=false;                break;            }        }        if(noValids)            s.pop();    }    return 0;}

سبحان الله .. جميلة

post-256536-0-28983200-1392225802_thumb.

جزاك الله خيراً

 

بالتوفيق

تم تعديل بواسطه مصطفى 36a2
1

شارك هذا الرد


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

مشكور أخ مصطفى ..

0

شارك هذا الرد


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

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

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



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

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

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