Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Phương pháp tối ưu giải 8 puzzle?

  1. #1
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Mặc định Phương pháp tối ưu giải 8 puzzle?

    Tôi code đoạn code sau, nhưng phương pháp có vẻ ko đc tối ưu cho lắm. Vì với những bài ko có đáp án. Nó chạy mãi ko ngừng. @@!! Có ai giỏi về AI thì xem giúp nên bổ sung gì vào nhé.
    C++ Code:
    1. // ConsoleApplication.cpp : Defines the entry point for the console application.
    2. //
    3. /*  Author: doicanhden@gmail.com
    4.     Date: 08/04/2012
    5. */
    6. #include "stdafx.h"
    7. #include <conio.h>
    8. #include <iostream>
    9. #include <vector>
    10. #include <algorithm>
    11. using namespace std;
    12.  
    13. int map[9][4] =
    14. {
    15. /*  { T, B, L, R}   */
    16.     { 0, 3, 0, 1}, { 1, 4, 0, 2}, { 2, 5, 1, 2},
    17.     { 0, 6, 3, 4}, { 1, 7, 3, 5}, { 2, 8, 4, 5},
    18.     { 3, 6, 6, 7}, { 4, 7, 6, 8}, { 5, 8, 7, 8}
    19. };
    20. struct puzzleState
    21. {
    22.     int _box[9];
    23.     int _o;
    24.     int _p;
    25.     puzzleState(int _1, int _2, int _3,
    26.                 int _4, int _5, int _6,
    27.                 int _7, int _8, int _9,
    28.                 int zeroPos):_p(-1)
    29.     {
    30.         _box[0] = _1; _box[1] = _2; _box[2] = _3;
    31.         _box[3] = _4; _box[4] = _5; _box[5] = _6;
    32.         _box[6] = _7; _box[7] = _8; _box[8] = _9;
    33.  
    34.         _o = zeroPos;
    35.     }
    36.     inline puzzleState create(int move)
    37.     {
    38.         /* Tạo trạng thái trả về. */
    39.         puzzleState ret = *this;
    40.  
    41.         /* Di chuyển ô trống. */
    42.         swap(ret._box[_o], ret._box[ map[_o][move] ]);
    43.  
    44.         /* Lưu vị trí mới của ô trống. */
    45.         ret._o = map[_o][move];
    46.  
    47.         return ret;
    48.     }
    49.     inline bool isFinal()
    50.     {
    51.         static puzzleState final1(1, 2, 3,  4, 5, 6,  7, 8, 0, 8);
    52.         static puzzleState final2(0, 1, 2,  3, 4, 5,  6, 7, 8, 0);
    53.         return *this == final1 || *this == final2;
    54.  
    55.         //return (_box[0] == 1 && _box[1] == 2 && _box[2] == 3 &&
    56.         //      _box[3] == 4 && _box[4] == 5 && _box[5] == 6 &&
    57.         //      _box[6] == 7 && _box[7] == 8 && _box[8] == 0) ||
    58.  
    59.         //     (_box[0] == 0 && _box[1] == 1 && _box[2] == 2 &&
    60.         //      _box[3] == 3 && _box[4] == 4 && _box[5] == 5 &&
    61.         //      _box[6] == 6 && _box[7] == 7 && _box[8] == 8);
    62.     }
    63.     inline void print()
    64.     {
    65.         cout << "** Trang thai puzzle **********" << endl;
    66.         cout << "** " << _box[0] << "         " << _box[1] << "         " << _box[2] << "     **" << endl;
    67.         cout << "** " << _box[3] << "         " << _box[4] << "         " << _box[5] << "     **" << endl;
    68.         cout << "** " << _box[6] << "         " << _box[7] << "         " << _box[8] << "     **" << endl;
    69.         cout << "*******************************" << endl;
    70.     }
    71.     inline bool operator==(const puzzleState& state)
    72.     {
    73.        
    74.         return (_box[0] == state._box[0] &&
    75.                 _box[1] == state._box[1] &&
    76.                 _box[2] == state._box[2] &&
    77.                 _box[3] == state._box[3] &&
    78.                 _box[4] == state._box[4] &&
    79.                 _box[5] == state._box[5] &&
    80.                 _box[6] == state._box[6] &&
    81.                 _box[7] == state._box[7] &&
    82.                 _box[8] == state._box[8]);
    83.     }
    84. };
    85. void BFS(const puzzleState &state)
    86. {
    87.     vector<puzzleState> que;
    88.  
    89.     que.push_back(state);
    90.     int iPos(0);
    91.     do
    92.     {
    93.         if(que.at(iPos).isFinal())
    94.         {
    95.             cout << "Tim ra trang thai cuoi. " << endl;
    96. labs_found:
    97.             for (int i(iPos); -1 != i; i = que.at(i)._p)
    98.                 que.at(i).print();
    99.             return;
    100.         }
    101.         else
    102.             for(int i(0); i < 4; i++)
    103.             {
    104.                 puzzleState newState = que.at(iPos).create(i);
    105.  
    106.                 if(newState.isFinal())
    107.                 {
    108.                     cout << "Tim ra trang thai cuoi. " << endl;
    109.                     newState.print();
    110.                     goto labs_found;
    111.                 }
    112.  
    113.                 if(que.end() == find(que.begin(), que.end(), newState))
    114.                 {
    115.                     newState._p = iPos;
    116.                     que.push_back( newState );
    117. //                  newState.print();
    118.                 }
    119.  
    120.                
    121.             }
    122.             iPos++;
    123.     } while (iPos < que.size());
    124.  
    125. }
    126. int _tmain(int argc, _TCHAR* argv[])
    127. {
    128.     puzzleState begin(1, 4, 3,
    129.                       7, 6, 2,
    130.                       5, 8, 0,
    131.                       8);
    132.     BFS(begin);
    133.     _getch();
    134.     return 0;
    135. }
    Đã được chỉnh sửa lần cuối bởi doicanhden : 08-04-2012 lúc 02:43 PM.
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  2. #2
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Một ví dụ, lời giải gồm 22 bước. Tổng cộng 70282 trạng thái được sinh ra.
    đầu vào:
    C++ Code:
    1.     puzzleState begin(7, 5, 6,
    2.                       4, 1, 2,
    3.                       8, 0, 3,
    4.                       7);
    Code:
    Tim ra trang thai cuoi. Sizeof Queue: 70282
    ** Trang thai puzzle **********
    ** 1         2         3     **
    ** 4         5         6     **
    ** 7         8         0     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         2         3     **
    ** 4         5         6     **
    ** 7         0         8     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         2         3     **
    ** 4         5         6     **
    ** 0         7         8     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         2         3     **
    ** 0         5         6     **
    ** 4         7         8     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         2         3     **
    ** 5         0         6     **
    ** 4         7         8     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         2         3     **
    ** 5         6         0     **
    ** 4         7         8     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         2         0     **
    ** 5         6         3     **
    ** 4         7         8     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         0         2     **
    ** 5         6         3     **
    ** 4         7         8     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         6         2     **
    ** 5         0         3     **
    ** 4         7         8     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         6         2     **
    ** 5         7         3     **
    ** 4         0         8     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         6         2     **
    ** 5         7         3     **
    ** 4         8         0     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         6         2     **
    ** 5         7         0     **
    ** 4         8         3     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         6         0     **
    ** 5         7         2     **
    ** 4         8         3     **
    *******************************
    ** Trang thai puzzle **********
    ** 1         0         6     **
    ** 5         7         2     **
    ** 4         8         3     **
    *******************************
    ** Trang thai puzzle **********
    ** 0         1         6     **
    ** 5         7         2     **
    ** 4         8         3     **
    *******************************
    ** Trang thai puzzle **********
    ** 5         1         6     **
    ** 0         7         2     **
    ** 4         8         3     **
    *******************************
    ** Trang thai puzzle **********
    ** 5         1         6     **
    ** 7         0         2     **
    ** 4         8         3     **
    *******************************
    ** Trang thai puzzle **********
    ** 5         0         6     **
    ** 7         1         2     **
    ** 4         8         3     **
    *******************************
    ** Trang thai puzzle **********
    ** 0         5         6     **
    ** 7         1         2     **
    ** 4         8         3     **
    *******************************
    ** Trang thai puzzle **********
    ** 7         5         6     **
    ** 0         1         2     **
    ** 4         8         3     **
    *******************************
    ** Trang thai puzzle **********
    ** 7         5         6     **
    ** 4         1         2     **
    ** 0         8         3     **
    *******************************
    ** Trang thai puzzle **********
    ** 7         5         6     **
    ** 4         1         2     **
    ** 8         0         3     **
    *******************************
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  3. #3
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Nếu yêu cầu của bạn chỉ là: "Với những bài không có đáp án nó chạy mãi không ngừng"
    thì cách giải quyết đơn giản là kiểm tra điều kiện ngừng trước khi chạy

    Nếu nhớ không nhầm thì loại bài "đẩy số" này tập các trạng thái chia làm 2 vùng không liên thông với nhau. Và sẽ có 1 thông số nào đó, mà ở vùng này thì luôn chẵn và vùng kia thì luôn lẻ.
    Ví dụ: Chia thành các ô đen / trắng như bàn cờ, thì count(số lẻ ở ô đen) + count(số chẵn ở ô trắng) không đổi tính chẵn lẻ qua mỗi bước đẩy số. Vậy cứ đếm trạng thái đầu vào, nếu cùng tính chẵn lẻ với trạng thái đích thì là có nghiệm

  4. #4
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    hjx. Nếu có code hoặc thêm tài liệu có lẽ sẻ dễ hiểu hơn~~. Bạn nhớ có nhớ đã đọc nó ở đâu không? Tìm lại giùm tôi nhé.Tks. Các đề dạng puzzle hầu như đều có nghiệm, chỉ là giải nhanh hay chậm thôi. Như ví dụ trên, tôi cứ nghĩ là ko có nghiệm nhưng thử cây đến độ sâu 22 thì xuất hiện nghiệm. ~~~
    Mở rộng thêm yêu cầu: "Phương pháp giải nhanh hơn có dùng hàm đánh giá trạng thái puzzle"
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

Các đề tài tương tự

  1. Algorithm Lỗi khi sử dụng thuật toán DFS cho bài toán 8 số (8 puzzle)
    Gửi bởi mrhuymap1491 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 4
    Bài viết cuối: 26-11-2013, 11:17 AM
  2. xin code cài đặt game 8 puzzle bằng giải thuật A* viết bằng c#
    Gửi bởi thanhcn12 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 0
    Bài viết cuối: 21-10-2013, 01:05 PM
  3. Giải thuật để chia hình ảnh thành các ô vuông nhỏ như trong game Picture Puzzle?
    Gửi bởi Mr.Pakapun trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 25-12-2012, 05:03 PM
  4. Graphic Vấn đề về lập trình 15 Puzzle với C#.
    Gửi bởi truongof007 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 5
    Bài viết cuối: 01-05-2011, 10:46 AM
  5. Giải bài toán n-puzzle với n > 9
    Gửi bởi Yin Yang trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 9
    Bài viết cuối: 18-12-2010, 07:13 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn