VuaTenMien.Com: Tìm đường đi ngắn nhất với Breadth First Search trong C#

Thứ Ba, 16 tháng 12, 2014

Tìm đường đi ngắn nhất với Breadth First Search trong C#

Tìm đường đi ngắn nhất với Breadth First Search trong C# - Source code Wumpus Game

Tìm đường đi ngắn nhất là một trong những bài toán được ứng dụng trong nhiều lĩnh vực. Và một thuật toán cơ bản và đơn giản nhất để làm điều này mà bạn có thể đã biết là Breadth First Search (BFS – Tìm kiếm theo chiều rộng). Cơ chế làm việc của thuật toán tương tự như vết dầu loang, tìm kiếm những điểm gần nhất trước. Bạn có thể thấy một vài game sử dụng bản đồ hay liên quan đến AI cũng có thể sử dụng thuật toán này. Một ví dụ bạn có thể áp dụng thuật toán này là n-puzzle mà tôi đã cài đặt bằng thuật toán A* để giải quyết.

Download sourcecode + demo (VC# 2010)
Pass giải nén: hoidapit.com.vn

Giới thiệu

Wumpus là một game điển hình được giải bằng cách sử dụng AI và logic. Tuy nhiên vì đây là chỉ là mình họa đơn giản cho thuật toán Breadth First Search nên ta không cần quan tâm tới phần các phần biểu diễn và suy luận logic trong chương trình.

Dựa vào mục đích trên, tôi sẽ thiệu vài nét cơ bản về game Wumpus. Đây là một game đơn giản có dạng bản đồ bao gồm các đối tượng Agent (nhân vật chính), Pit (hố), Wumpus (một loại quái vật) và Gold (rương vàng).

Mục đích của ví dụ này là tìm đường sao cho Agent đến được Gold và không đụng phải các Pit và Wumpus. Một điểm ta cần quan tâm nữa là Agent luôn xuất phát tại điểm (0,0).

Giải thuật tổng quát

Trong giải thuật này ta cần định nghĩa các thành phần sau:

Giải thuật được mô tả bằng mã giả như sau:

Begin
    Open := {start};
    Close := ø;
    While (Open <> ø) do
        begin
            n:= Dequeue(Open);
            if (n=goal) then Return True;
            Open := Open + G(n);
            Close := Close + {n};
        end;
    Return False;
End;

Ta thấy rằng G(n) dựa vào tập Close để kiểm tra các vị trí có cần được kiểm tra hay không. Nếu bạn cài đặt hai tập này bằng một collection thì tốc độ thực thi sẽ tương đối chậm vì phải thực hiện tìm kiếm phần tử trong danh sách.

Do ví dụ của ta có dạng bản đồ nên thay vì dùng collection, ta sẽ sử dụng mảng hai chiều để có thể truy xuất trực tiếp đến một phần tử dựa vào vị trí. Khi đó ta có thể kiểm tra thuộc tính của phần tử xem nó đã được duyệt chưa.

Các lớp cơ bản

Mỗi ô vuông đơn vị trong bản đồ được tôi sử dụng một đối tượng Square sau để biểu diễn. Giá trị của property State của Square cho ta biết chính xác ô đó chứa thứ gì. Thuộc tính Marked chỉ được dùng để đánh dấu làm nổi bật đường đi khi ta tìm thấy đường.

enum SquareState
{
    Wumpus,
    Pit,
    Gold,
}
struct Square
{
    public SquareState State { get; set; }
    public bool Marked { get; set; }
}

Phần vẽ bản đồ đơn giản là ta tạo một mảng Square rồi random đặt các trạng thái Wumpus, Pit, Gold. Sau cùng dùng sự kiện OnPaint() để hiển thị lên màn hình.

Lớp BreadthFirstSearch hiện thực đoạn mã giả ở phần trên bằng C#. Contructor của lớp này nhận một mảng 2 chiều Square để tạo nên mảng MyPoint. Các ô có giá trị là Wumpus hoặc Pit sẽ không được tạo và sẽ mang giá trị mặc định là null.

class BreathFirstSearch
{
    MyPoint[,] _cells;
    Queue open = new Queue();
    Point goal;
    public BreathFirstSearch(Square[,] data)
    {
        _cells = new MyPoint[data.GetLength(0), data.GetLength(1)];
        for (int i = 0; i < _cells.GetLength(0); i++)
        {
            for (int j = 0; j < _cells.GetLength(1); j++)
            {
                if (data[i, j].State == SquareState.Gold)
                    goal = new Point(i, j);
                if (data[i, j].State == SquareState.None ||
                    data[i, j].State == SquareState.Gold)
                    _cells[i, j] = new MyPoint(i, j);
            }
        }
        open.Enqueue(new MyPoint(0, 0));
    }
    public List FindPath()
    {
        while (open.Count > 0)
        {
            MyPoint p = open.Dequeue();
            if (p.ToPoint()==goal)
            {
                return GetSolution(p);
            }
            if (p != null)
            {
                GenMove(p);
            }
        }
        return null;
    }
    void AddToOpen(MyPoint point, MyPoint previous)
    {
        if (point != null && !point.Visited)
        {
            point.Visited = true;
            point.Previous = previous;
            open.Enqueue(point);
        }
    }
    List GetSolution(MyPoint p)
    {
        List list = new List();
        list.Add(p.ToPoint());
        while (p.Previous != null)
        {
            list.Add(p.Previous.ToPoint());
            p = p.Previous;
        }
        return list;
    }
    void GenMove(MyPoint p)
    {
        if (p.X < _cells.GetLength(0) - 1)
            AddToOpen(_cells[p.X + 1, p.Y], p);
        if (p.Y < _cells.GetLength(1) - 1)             AddToOpen(_cells[p.X, p.Y + 1], p);         if (p.X > 0)
            AddToOpen(_cells[p.X - 1, p.Y], p);
        if (p.Y > 0)
            AddToOpen(_cells[p.X, p.Y - 1], p);
    }
}

Lớp MyPoint được định nghĩa như sau:

class MyPoint
{
    public int X;
    public int Y;
    public bool Visited = false;
    public MyPoint Previous;
// [...]
}

Tôi sử dụng biến Previous để lưu vị trí của phần tử trước đó, như vậy khi tìm được đích, ta sẽ dựa vào giá trị này để lần ngược lại đường đi từ vị trí xuất phát đến đích. Bạn có thể thấy phương thức GetSolution() trong lớp BreadthFirstSearch thực hiện điều này như thế nào.

Phần kết

Đây là chỉ là một ví dụ đơn giản minh họa cho thuật toán Breadth First Search giúp bạn có thể dễ dàng cài đặt để ứng dụng trong các chương trình hoặc các game nhỏ. Sẽ là một thiếu sót nếu tôi chỉ trình bày về thuật toán tìm kiểm chiều rộng mà không nói về thuật toán tìm kiếm theo chiều sâu (Depth First Search – DFS). Trong bài viết tiếp theo bạn sẽ thấy một chương trình đơn giản mô phỏng trực quan thuật toán này bao gồm hiệu ứng quay lui (backtracking). Dựa vào đó bạn có thể so sánh được sự khác biệt giữa thuật toán BFS này và DFS.

VuaTenMien.Com