AI-K58, bài 4: Tìm kiếm mù

1 bình luận cho AI-K58, bài 4: Tìm kiếm mù

• 

  20/11/2018 - 17:52

  admin  says:

  Thuật toán tìm kiếm mù trong mê cung, viết bằng C++

  #include <iostream> #include <vector> using namespace std; const int M = 8; // số dòng const int N = 10; // số cột // bản đồ mặc định int a[M][N] = { { 0,-1, 0, 0,-1,-1,-1, 0, 0, 0,}, { 0, 0, 0, 0, 0, 0,-1, 0, 0, 0,}, {-1, 0,-1,-1,-1, 0,-1, 0, 0, 0,}, { 0, 0, 0, 0, 0, 0,-1,-1, 0, 0,}, {-1, 0,-1, 0,-1, 0, 0, 0,-1,-1,}, { 0, 0,-1,-1,-1, 0,-1,-1, 0, 0,}, { 0, 0,-1, 0, 0, 0,-1, 0, 0, 0,}, { 0, 0, 0, 0,-1,-1,-1, 0, 0, 0,} }; // một hình trạng: vị trí ô đang xét (dòng và cột) struct state { int row, col; state(int r = 0, int c = 0) : row(r), col(c) {} }; state goal(3, 0); // trạng thái đích vector<state> S; // tập hợp các trạng thái đang được xem xét int value = 0; // biến đếm số trạng thái đã được xem xét // vẽ hình trạng ở ô (i,j) void draw(int i, int j) { if (i == goal.row && j == goal.col) { cout << " # "; return; } switch (a[i][j]) { case 0: cout << " . "; break; case -1: cout << " X "; break; case -2: cout << " ? "; break; default: cout << ((a[i][j] < 10) ? " " : "") << a[i][j] << " "; } } // in bản đồ, trước khi in xóa màn hình, in xong chờ bấm enter void printMap() { system("cls"); for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) draw(i, j); cout << endl; } cin.get(); } // thêm ô [row,col] vào tập S, đặt trạng thái bằng -2 (ô đang xét) void addState(int row, int col) { S.push_back(state(row, col)); a[row][col] = -2; } // kết nạp những ô xung quanh trạng thái node void expand(state n) { a[n.row][n.col] = ++value; if (n.row > 0 && a[n.row-1][n.col] == 0) addState(n.row-1, n.col); if (n.row < (M-1) && a[n.row+1][n.col] == 0) addState(n.row+1, n.col); if (n.col > 0 && a[n.row][n.col-1] == 0) addState(n.row, n.col-1); if (n.col < (N-1) && a[n.row][n.col+1] == 0) addState(n.row, n.col+1); } // thuật toán tìm kiếm mù void search(state start) { S.push_back(start); while(true) { // in bản đồ hiện tại printMap(); // đã xem xét hết các trạng thái, không tìm được lời giải if (S.size() == 0) { cout << "Khong tim duoc duong di!!!" << endl; return; } // Trường hợp S hoạt động như stack //state node = S.back(); //S.pop_back(); // Trường hợp S hoạt động như queue state node = S.front(); S.erase(S.begin()); // đã tìm đến được trạng thái goal, trả lại kết quả if (node.row == goal.row && node.col == goal.col) { cout << "Co tim duoc duong di!!!" << endl; return; } expand(node); } } void main() { // bắt đầu tìm kiếm từ trạng thái [3,5], đích đến là trạng thái goal search(state(3, 5)); }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98

  #include <iostream> #include <vector> using namespace std;   const int M = 8;    // số dòng const int N = 10;   // số cột   // bản đồ mặc định int a[M][N] = {     { 0,-1, 0, 0,-1,-1,-1, 0, 0, 0,},     { 0, 0, 0, 0, 0, 0,-1, 0, 0, 0,},     {-1, 0,-1,-1,-1, 0,-1, 0, 0, 0,},     { 0, 0, 0, 0, 0, 0,-1,-1, 0, 0,},     {-1, 0,-1, 0,-1, 0, 0, 0,-1,-1,},     { 0, 0,-1,-1,-1, 0,-1,-1, 0, 0,},     { 0, 0,-1, 0, 0, 0,-1, 0, 0, 0,},     { 0, 0, 0, 0,-1,-1,-1, 0, 0, 0,} };   // một hình trạng: vị trí ô đang xét (dòng và cột) struct state {     int row, col; state(int r = 0, int c = 0) : row(r), col(c) {} };   state goal(3, 0);    // trạng thái đích vector<state> S;     // tập hợp các trạng thái đang được xem xét int value = 0;       // biến đếm số trạng thái đã được xem xét   // vẽ hình trạng ở ô (i,j) void draw(int i, int j) { if (i == goal.row && j == goal.col) { cout << " # "; return; } switch (a[i][j]) { case  0: cout << " . "; break; case -1: cout << " X "; break; case -2: cout << " ? "; break; default: cout << ((a[i][j] < 10) ? " " : "") << a[i][j] << " "; } }   // in bản đồ, trước khi in xóa màn hình, in xong chờ bấm enter void printMap() { system("cls");     for (int i = 0; i < M; i++) {         for (int j = 0; j < N; j++) draw(i, j);         cout << endl;     }     cin.get(); }   // thêm ô [row,col] vào tập S, đặt trạng thái bằng -2 (ô đang xét) void addState(int row, int col) {     S.push_back(state(row, col));     a[row][col] = -2; }   // kết nạp những ô xung quanh trạng thái node void expand(state n) {     a[n.row][n.col] = ++value;     if (n.row > 0     && a[n.row-1][n.col] == 0) addState(n.row-1, n.col);     if (n.row < (M-1) && a[n.row+1][n.col] == 0) addState(n.row+1, n.col);     if (n.col > 0     && a[n.row][n.col-1] == 0) addState(n.row, n.col-1);     if (n.col < (N-1) && a[n.row][n.col+1] == 0) addState(n.row, n.col+1); }   // thuật toán tìm kiếm mù void search(state start) {     S.push_back(start);     while(true) { // in bản đồ hiện tại printMap(); // đã xem xét hết các trạng thái, không tìm được lời giải         if (S.size() == 0) {             cout << "Khong tim duoc duong di!!!" << endl;             return;         } // Trường hợp S hoạt động như stack //state node = S.back(); //S.pop_back(); // Trường hợp S hoạt động như queue         state node = S.front(); S.erase(S.begin()); // đã tìm đến được trạng thái goal, trả lại kết quả         if (node.row == goal.row && node.col == goal.col) {             cout << "Co tim duoc duong di!!!" << endl;             return;         }         expand(node);     } }   void main() { // bắt đầu tìm kiếm từ trạng thái [3,5], đích đến là trạng thái goal     search(state(3, 5)); }

  Trả lời