dùng thuật toán breadth first search (bfs) giải bài toán 8 puzzle

[luckypuca]

có anh chị nào đã học qua môn trí tuệ nhân tạo không ạ , mong mọi người hướng dẫn giúp em ứng dụng thuật toán bfs vào giải bài toán 8 puzzle , em không biết cách để đưa thuật toán vào bài này ....cám ơn mọi người nhiều ...

[Here i am]

phần code còn thiếu bạn tự viết nhé

#include <stdio.h>#include <string.h>#include <queue>#include <set>using std::queue;using std::set; class puzzle{public:    char data[9];    short count;        bool goal()    {        //do somethings    }     bool canMoveLeft()    {        //do somethings    }     bool canMoveRight()    {        //do somethings    }     bool canMoveUp()    {        //do somethings    }     bool canMoveDown()    {        //do somethings    }     puzzle movedUp()    {        puzzle res;        res.count=count+1;        //        //do somethings to move        //         return res;    }     puzzle movedDown()    {        puzzle res;        res.count=count+1;        //        //do somethings to move        //        return res;    }     puzzle movedLeft()    {        puzzle res;        res.count=count+1;        //        //do somethings to move        //        return res;    }     puzzle movedRight()    {        puzzle res;        res.count=count+1;        //        //do somethings to move        //        return res;    }}; bool operator<(const puzzle&a,const puzzle&b){    return memcmp(&a.data[0],&b.data[0],9)<0;} int main(){    queue<puzzle> Queue;    set<puzzle> Set;    puzzle root;        root.count=0;    //define the root here    //    //     Queue.push(root);    bool found=false;    while(Queue.empty()==false)    {        puzzle t=Queue.front();        Queue.pop();        if(Set.insert(t).second==false) continue;        if(t.goal()==true)        {            found=true;            printf("%d\n",t.count);            break;        }         if(t.canMoveUp()==true) Queue.push(t.movedUp());        if(t.canMoveDown()==true) Queue.push(t.movedDown());                if(t.canMoveLeft()==true) Queue.push(t.movedLeft());        if(t.canMoveRight()==true) Queue.push(t.movedRight());    }    if(found==false) printf("9999\n");    return 0;}

[luckypuca]

phần code còn thiếu bạn tự viết nhé

 int main(){    queue<puzzle> Queue;    set<puzzle> Set;    puzzle root;        root.count=0;    //define the root here    //    //     Queue.push(root);    Set.insert(root);    bool found=false;    while(Queue.empty()==false)    {        puzzle t=Queue.front();        Queue.pop();        if(Set.insert(t).second==false) continue;        if(t.goal()==true)        {            found=true;            printf("%d\n",t.count);            break;        }         if(t.canMoveUp()==true) Queue.push(t.movedUp());        if(t.canMoveDown()==true) Queue.push(t.movedDown());                if(t.canMoveLeft()==true) Queue.push(t.movedLeft());        if(t.canMoveRight()==true) Queue.push(t.movedRight());    }    if(found==false) printf("9999\n");    return 0;}

bạn ơi bạn có thể giải thích các dòng code bfs cho mình được không vì mình mới hoc môn trí tuệ nhân tạo này nên chưa rõ ý nghĩa và cách hoạt động của các dòng code trong cách làm này ....mong bạn thông cảm ...cám ơn bạn nhiều ....

[Here i am]

sử dụng hàng đợi, ban đầu đưa trạng thái xuất phát vào hàng đợi, với mỗi vòng lặp, lấy trạng thái ở vị trí đầu tiên trong hàng đợi ra(phải là đầu tiên và chỉ lấy 1), kiểm tra xem nó có phải trạng thái đích chưa, nếu đúng rồi thì dừng, nếu không đúng thì kiểm tra xem ta đã xét qua trạng thái này chưa(do việc di chuyển sang phải rồi lại sang trái hoặc tạo ra chu trình) nếu đã xét rồi thì phải bỏ qua nó, bạn có thể không cần bỏ qua mà chương trình chạy vẫn đúng, như sẽ rất ì ạch ,liệt kê tất cả các trạng thái lân cận của trạng thái đang xét và đẩy vào hàng đợi rồi tiếp tục vòng lặp.

goal(): kiểm tra trạng thái đang xét có phải là đích hay không
canMoveLeft(): kiểm tra trạng thái đang xét có thể di chuyển sang trái hay không
movedDown(): tạo ra một trạng thái mơi là trạng thái đang xét di chuyển xuống( chỉ sử dụng khi có thể di chuyển xuống)

để thuận tiện cho việc kiểm tra một trạng thái đã xét hay chưa, ta sử dụng set, cấu tạo của nó là một cây nhị phân cân bằng, cấu trúc set yêu cầu sử dụng toán tử < để so sánh các phần tử của nó, do đó cần phải định nghĩa thêm operator<(const puzzle&a,const puzzle&b), mỗi khi insert một phần tử vào set thì nó sẽ cho biết có bị trùng hay không

 queue<puzzle> Queue;//khai báo hàng đợi    set<puzzle> Set;//khai báo set    puzzle root;       root.count=0;//số lần di cuyển ban đâu là 0    //define the root here    //trạng thái ban đầu như thế nào ?    //     Queue.push(root);//đẩy trạng thái ban đầu vào hàng đợi    bool found=false;    while(Queue.empty()==false)    {        puzzle t=Queue.front();        Queue.pop();//lấy thằng đầu tiên trong hàng đợi ra và loại nó khoti hàng đợi        if(Set.insert(t).second==false) continue;//nếu trạng thái này đã xét thì bỏ qua        if(t.goal()==true)//nếu đây là trạng thái đích        {            found=true;            printf("%d\n",t.count);            break;        }         if(t.canMoveUp()==true) Queue.push(t.movedUp());        if(t.canMoveDown()==true) Queue.push(t.movedDown());               if(t.canMoveLeft()==true) Queue.push(t.movedLeft());        if(t.canMoveRight()==true) Queue.push(t.movedRight());    }    if(found==false) printf("9999\n");//nếu xết hết mọi tổ hợp có thể có mà vẫn không tìm được trạng thái đích

[luckypuca]

cảm ơn bạn rất nhiều