2015/08/09

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

السلام عليكم ورحمة الله وبركاته
تعتبر خوارزمية Depth First Search أحد الخوارزميات للمرور على جميع النقاط المتصلة connected nodes في مخطط Graph ما ..
لا أريد التكرار فالموضوع عليه الكثير من الشروحات الواضحة على youTube  كما أن صفحة wikipedia فيها شرح ممتاز (وفيديو ملحق لإنشاء متاهة أيضاً :) )
ولكن لتبسيط الأمر .. تخيل أن لدينا شجرة كثيرة الفروع , حتى أن فروعها متداخلة , يعني يمكن أن يتقاطع فرعان ويندمجا !
تخيل أن هذه شجرة :
https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Minimum_spanning_tree.svg/2000px-Minimum_spanning_tree.svg.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 وليس هو الخوارزمية , وقد وضعته كمثال رسومي جيد لبيان جمال الخوارزمية ليس أكثر .

والله ولي التوفيق
===================كاتب المقال: مصطفى 36a2==================
مرسلة بواسطة في
التسميات: , , , ,

ليست هناك تعليقات:

إرسال تعليق

الاشتراك في: تعليقات الرسالة (Atom)