Tài nguyên dạy học

Thống kê

  • truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • Thành viên trực tuyến

    3 khách và 0 thành viên

    Phân tích và giải bài toán n puzzle

    690D7484665348AAB082432277C1D129
    (Tài liệu chưa được thẩm định)
    Nguồn: https://yinyangit.wordpress.com/2010/12/16/algorithm-phan-tich-va-giải-bai-toan-n-puzzle/
    Người gửi: Phạm Thị Thu Hương (trang riêng)
    Ngày gửi: 21h:00' 20-11-2019
    Dung lượng: 2.3 KB
    Số lượt tải: 4
    Mô tả:

    Trong bài trước tôi đã giới thiệu chương trình minh họa giải bài toán n-puzzle kèm theo mã nguồn (VC# 2008). Bài viết này sẽ dùng mã nguồn đó để phân tích và giải thích nên tôi chỉ trích những đoạn code quan trọng lên đây.

    Download mã nguồn (VC# 2008 – 229KB)

     

    I.   Giới thiệu:

    Vui lòng đọc tại đây

    II. Thuật toán tìm kiếm A*

    A* là một giải thuật tìm kiếm thường được sử dụng trong các vấn đề liên quan đến đồ thị và tìm đường đi. Nó được chọn không chỉ vì tính hiệu quả mà còn vì rất dễ dàng để hiểu và cài đặt. Bạn cần nắm rõ thuật toán này trước khi tiếp tục. Tôi giải sử bạn đã biết về các lý thuyết này, tuy nhiên để tiện lợi cho việc tham khảo bạn có thể đọc ở hai link bên dưới:
    –  Giải thuật tìm kiếm A*

    –  A* search algorithm

    III. Phân tích bài toán

    – Như đã giới thiệu trong bài trước, có những trạng thái của bảng số không thể chuyển về trạng thái đích, ta gọi là cấu hình hợp lệ và không hợp lệ. Tỉ lệ giữa chúng là ½, điều này có thể nhận ra dễ dàng từ phương pháp tính xem bài toán có thể đưa về trạng thái đích hay không.

    – Rất dễ thấy là mỗi trạng thái của bảng số là một hoán vị của m x m phần tử (với m là cạnh), như vậy không gian trạng thái của nó là (m x m)!, với 8-puzzle là 9! = 362880 (m = 3) và 15-puzzle là 16! = 20922789888000 (m =4). Bạn có thể khi m tăng lên 1 đơn vị thì không gian trạng thái tăng lên rất nhanh, điều này khiến cho việc giải quyết các phiên bản m>3 ít khi được áp dụng.

    – Để áp dụng thuật toán A* giải bài toán này, bạn cần một hàm heuristic h để ước lượng giá trị của mỗi trạng thái của bảng số. Có một số cách bạn có thể đã biết tới như tính dựa vào khoảng cách sai lệch của các ô số với vị trí đúng, hoặc đơn giản là đếm xem có bao nhiêu ô sai vị trí,… Ở đây tôi chọn theo cách thứ nhất, tức là tính tổng số ô sai lệch của các ô số so với vị trí đúng của nó. Đây là cách tính thường được sử dụng và nó có tên gọi là Manhattan.

    *Nếu bạn tìm kiếm trên mạng về Manhattan bạn sẽ thấy rằng đây là tên một quận của thành phố New York, nơi mà các con đường chạy ngang dọc như một bàn cờ lớn, nhờ thế việc tìm được cũng như di chuyển rất thuận lợi.

    Tham khảo: http://en.wikipedia.org/wiki/Taxicab_geometry

    -Ví dụ:

    Tính khoảng cách Manhattan

    Tính khoảng cách Manhattan

    Trong bảng số 3×3 trên, để di chuyển ô số 5 vào đúng vị trí ta cần di chuyển nó 1 lần, để di chuyển ô số 7 về đúng vị trí ta cần cần 4 lần (qua 4 ô khác). Để có được kết quả này ta làm phép tính đơn giản: lấy tổng khoảng cách của dòng và cột giữa hai vị trí (ví dụ với ô số 7):

    –       Lấy tọa độ của ô số 7 ta có row1 = 0 và column1 = 2

    –       Lấy tọa độ của ô số 7 khi ở vị trí đúng, ta có ow2 = 2 và column2 = 0

    –       Vậy khoảng cách Manhattan của hai ô này là:

    |row1 – row2| + |column1 – column2| = |0 – 2| + |2 – 0| = 4

    Theo đó, ta tính được h = 0+1+4+2+2+0+1+1+1 = 12

    Như vậy ở trạng thái đích thì bảng số sẽ có giá trị thấp nhất là 0.

    *Từ giá trị của một ô số ta tính vị trí dòng và cột của nó như sau:

    Ví dụ ô số 7 có thứ tự trong bảng là 6 (tính từ 0 với m là cạnh) ta có row = 6 / 3 = 2, col = 6 % 3 = 0. Vậy tổng quát lại ta có:

    RowIndex = Index / m

    ColIndex = Index % m


    IV.  Triển khai thuật toán A*

    Trước khi tiếp tục bạn nên có một cái nhìn tổng quát về các lớp chính được tôi sử dụng trong project. Sau đó tôi sẽ giải thích một vài đoạn code chính để bạn dễ hiểu.

    Class Form và Board thuộc phần giao diện, tôi dùng lớp Board để hiển thị bảng số lên trên form. Bạn có thể dễ dàng sửa lại lớp này để thay đổi cách hiển thị mà không làm ảnh hường đến hoạt động của chương trình.

    –       Lớp Matrix: Đại diện cho một bảng số, có thể coi là một node trong cây tìm kiếm khi bạn cài đặt giải thuật.

    • Value: mảng lưu bảng số
    • Score: lưu trữ giá trị từ hàm heuristic h của bảng số
    • ComparingValue: là giá trị dùng để so sánh các phần tử Matrix trong OpenList, là tổng của Score và StepCount (số nước đi từ trạng thái đầu tiên đến trạng thái hiện tại)
    • Size: Độ lớn cạnh của bảng số.
    • Length: Tổng số phần tử của bảng số
    • Parent: Lưu đối tượng cha, là trạng thái trước của trạng thái hiện tại
    • Direction: đối tượng kiểu MoveDirection, lưu hướng di chuyển để từ trạng thái trước đó tới trạng thái hiện tại
    • Clone(): phương thức này tạo ra một bản sao của đối tượng. Vì Matrix là một lớp có kiểu tham chiếu nên để tạo bản sao bạn không thể gán các biến như với các kiểu giá trị int, double,…
    • GetId(): Tạo ra id cho đối tượng, id dựa vào thứ tự sắp xếp các số trong mảng, dĩ nhiên với 2 mảng khác nhau thì id cũng khác nhau. Việc dùng Id sẽ giúp ta kiểm tra và tìm kiếm đối tượng dễ dàng hơn khi chúng ở trong một collection. (Bạn nên cẩn thận khi cho kích thước bảng quá lớn sẽ vượt ngoài phạm vi kiểu int của biến Id).
    • MakeMove(MoveDirection): thực hiện “di chuyển” (hoán vị) bảng số dựa vào hướng di chuyển được truyền vào
    • Shuffle(): Xáo trộn bảng số

    –       OpenList: Chứa các đối tượng Matrix (node) đã được duyệt tới, khi thêm một node vào danh sách. Ta sẽ chèn nó vào đúng vị trí sao cho OpenList luôn được sắp xếp từ nhỏ đến lớn.

    • idList: Danh sách cài đặt bằng HashSet chứa id của các phần tử được thêm vào, dùng để kiểm tra trước khi thêm xem trong OpenList có phần tử đó chưa. Việc lưu trữ dùng mã “băm” sẽ giúp việc tìm kiếm nhanh hơn so với các dạng collection khác.

    –       GameEngine: đối tượng quản lý chung các hoạt động của thuật toán, chứa danh sách OPEN và CLOSE. Danh sách “solution” để lưu lại đường đi tìm được từ trạng thái đầu tiên tới đích.

    • Solve(): phương thức chính đế giải bài toán.
    • Evaluate(): hàm lượng giá Heuristic tính giá trị của một bảng số.
    • GenMove(Matrix): Sử dụng phương thức CloneMove(Matrix, MoveDirection) sinh ra các nước đi tiếp theo từ node được truyền vào. Nếu node mới tạo ra đã tồn tại trong CLOSE thì kiểm tra và cập nhật nước đi ngắn hơn cho node.
    • TrackPath(): Tạo danh sách các nước đi từ trạng thái đầu tiên đến đích và lưu vào đối tượng solution.

    1.  Lớp Matrix:

    Trong lớp này thay vì sử dụng mảng hai chiều để lưu bảng số, tôi sử dụng mảng 1 chiều để so sánh. Tuy điều này có lợi về lưu trữ và giúp cho một vài đoạn code viết dễ dàng hơn nhưng nó cũng làm một số khác lại trở nên tốn chi phí hơn. Chính vì thế mà hiệu suất của chương trình với việc dùng mảng một chiều có thể coi như tương đương với mảng hai chiều. Tuy nhiên trong phần cuối, tôi sẽ chỉ ra một cách để khắc phục điểm này của mảng một chiều.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    internal void GetId()
    {
        this.Id = 0;
        int n = 1;
    Số lượt thích: 0 người
     
    Gửi ý kiến