Bài Toán 8 Puzzle–thiết Kế Và Cài đặt. | Legend's Space

Sau khi đưa bài toán về đưới dạng đồ thị, áp dụng thuật toán A* để xác đinh đường đi từ trạng thái đầu đến trạng thái đích. Các class : class BOARD: Lưu giữ thông tin về một trạng thái hiện tại của bảng, có thể dung một mảng kiểu int gồm 9 phần tử, trong đó vị trí của các số từ 1 đến 8 tương ứng là vị trí của 8 mảnh ghép, vị trí của số 0 tương ứng với khoảng trống, việc sử dụng mảng 2 chiều hay 1 chiều. đều cố những ưu nhược điểm riêng. Quan trọng nhất là hàm ước lượng khoảng cách H từ board hiện tại đến board kết thúc, có nhiều cách để ước lượng, một trong những cách phổ biến nhất là phương pháp Mahatan. Đó là tính tổng số bước cần di chuyển đối với các mảnh ghép đâng nằm sai vị trí. VD: ta có trạng thái:             trạng thái đích(cách tính mình đã nói trong entry trước.)

3-2-8                                  0-1-2 6-1-7         =>                      3-4-5 -5-4                                   6-7-8 Như vậy H ở đây bằng h(3) + h(2) + h(8) + h(6) +h(1) +  h(7) +h(5) + h(4) =   1  +  1    +    2  +  1    + 1    +   2   + 2 +    2 = 12. Class STATE, một node lưu giữ thông tin về một state tương ứng một đỉnh trên đồ thị, đồng thời lưu giữ thông tin về state trước nó pre(x) , đông thời cung cấp phương thức tạo ta các node mà từ nó có thể đi tới. Class Astar, nới xử lý thuật toán, ta có thể dùng vector để lưu các tập open và close, ưu điểm của nó là việc thêm phần tử vào rất nhanh, đồng thời việc xử lý trên container cũng rất linh hoạt khi kết hợp sử dụng với iterator. Để tiện việc xử lý ta nên khai báo enum ENDSTATE cho biết trạng thái kết thúc.

class BOARD { private: int _value[9]; public: BOARD (void); BOARD(int r_value[9]); ~BOARD(void); int H(ENDSTATE r_state);     // hàm ước lượng Heuristic. vector<BOARD> Next();       // các board có thể xây dựng từ board hiện tại. void Print(); bool operator ==(BOARD r_board); BOARD& operator =(BOARD r_board); };

class STATE { private: BOARD _board; public: int _cost; int _f;                                   // chi phí dự đoán từ đầu đến đích nếu qua x. = f+g. int _g;                                  // chi phí từ đỉnh ban đầu đến x. int _h;                                  // chi phí dự đoán từ x đến đỉnh kết thúc tính bằng H() STATE* _prevstate;                 // nút trước x trong quá trình duyệt. STATE(void); STATE(BOARD r_board, int r_cost); ~STATE(void); vector<STATE> Next(); void Print(); int H(ENDSTATE r_state); bool operator ==(STATE r_state); STATE& operator = (STATE r_state); };

class ASTAR { private: STATE _startstate; STATE _endstate; STATE _temp; vector<STATE> _open; vector<STATE> _close; vector<STATE> _next; vector<STATE>::iterator _irt; vector<STATE>::iterator _mirt; ENDSTATE _typeendstate; public: ASTAR(void); ASTAR(int  Array[]); ~ASTAR(void); void Solve();           // thuật toán được cài đặt ở đây. void Print();           // in ra quá trình giải. };

Đây chỉ là ý tưởng thiết kế và cài đặt, việc cài đặt thực tế sẽ xuất hiện một số vấn đề rất thú vị nếu bạn code bằng C++. Còn nếu code bằng C# ỏ Java sẽ khá đơn giản.

Share this:

• Facebook
• X

Related