Algorithm – Minh họa Depth First Search và Breadth First Search bằng GDI+

Tiếp tục bài viết trước (Tìm đường đi ngắn nhất với Breadth First Search) về thuật toán tìm kiếm trên không gian trạng thái. Ta biết rằng đây là vấn đề cơ bản và phổ biến nhất trong lĩnh vực trí tuệ nhân tạo. Hai thuật toán điển hình khi nói về kĩ thuật này là Depth First Search (DFS – Tìm kiếm chiều sâu) và Breadth First Search (BFS – Tìm kiếm chiều rộng). Từ hai thuật toán này, bạn có thể phát triển và biến đổi thành những thuật toán tìm kiếm không gian trạng thái khác tùy từng trường hợp.

Download sourcecode+demo(VC# 2010)

Quy ước màu sắc trong chương trình

– Xanh lục: bắt đầu

– Hồng: kết thúc

– Trắng: chưa duyệt

– Lam nhạt: chờ được duyệt (đã cho vào stack/queue)

– Xám nhạt: đã duyệt

– Xám đậm: quay lui

– Vàng: đường đi từ điểm bắt đầu đến kết thúc

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

Cả hai giải thuật BFS và DFT đều có chung một giải thuật tổng quát và cần định nghĩa các thành phần sau:

Open Danh sách chứa các vị trí chờ được xét
Close Danh sách chứa các vị trí đã xét.
start Vị trí bắt đầu
goal Vị trí kết thúc
n vị trí đang xét.
G(n) Tập các vị trí có thể đến từ vị trí n.

Mã giả:

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

Vậy điểm khác biệt giữa BFS và DFS là gì? Bạn thấy trong bài trước tôi sử dụng Queue cho tập Open, theo cơ chế FIFO như thế những phần tử được thêm vào trước sẽ được duyệt trước. Vậy để thay đổi cơ chế này, ta chỉ cần sử dụng một cấu trúc dữ liệu khác. Một cấu trúc dữ liệu mà sẽ xét các vị trí mới nhất trước. Bạn có thể biết ngay rằng tôi đang muốn nói tới Stack. Vâng, Stack và Queue là cặp bài trùng thường đi đôi với nhau cũng như khi nói về BFS ta thường liên tưởng đến DFS.

Tiếp tục, để cài đặt hai thuật toán này vậy ta phải tạo ra cả Stack và Queue. Như thế khá bất tiện khi bạn muốn chuyển đổi từ kiểu tìm kiếm này sang kiểu kia. Giải pháp mà ta chọn lựa là tạo một collection kếthợp cả Stack và Queue. Dĩ nhiên không cần có đầy đủ chức năng của cả hai, ta chỉ tạo những phương thức cần thiết.

Stack + Queue = Quack ?

Không có ngụ ý gì ngoài việc kết hợp “Stack” và “Queue” để tạo ra “Quack”. Bạn có thể thấy rằng từ này không rõ nghĩa trong trường hợp này nên ta sẽ đặt thêm Collection vào phía sau. Như vậy ta có một collection kết hợp của Stack và Queue tên là QuackCollection.

Trong lớp này ta sẽ dùng thuộc tính IsQueue để xác định xem nó sẽ là Stack hay Queue. Điểm khác biệt chỉnh giữa Stack và Queue là Stack sẽ lấy phần tử ở đầu còn Queue thì lấy ở cuối.

Phương thức Get() trong lớp này có công dụng như Pop() của Stack và Dequeue() của Queue:

public class QuackCollection<T>
{
    private IList<T> _list;

    public bool IsQueue { get; set; }

    public QuackCollection() : this(true) { }

    /// <summary>
    /// </summary>
    /// <param name="isQueue">true</param>
    public QuackCollection(bool isQueue)
    {
        this.IsQueue = isQueue;
        _list = new List<T>();
    }

    public void Add(T item)
    {
        _list.Add(item);
    }
    public T Get()
    {
        int index=0;
        if(!this.IsQueue)
            index=_list.Count - 1;

        T item = _list[index];
        _list.RemoveAt(index);
        return item;
    }
    public bool IsEmpty
    {
        get { return _list.Count == 0; }
    }
    public void Clear()
    {
        _list.Clear();
    }
}

Cài đặt thuật toán

Trước tiên ta cần tạo lớp Cell đại diện cho một ô trên bản đồ

public enum CellState
{
	UnKnown,
	Queued,
	Visited,
	Barricade,
	Highlight,
	BackTracking,
}

public class Cell
{
	public Cell Previous { get; set; }
	public int Row { get; set; }
	public int Col { get; set; }
	public CellState State { get; set; }
	public int NumOfWays { get; set; }

	public Cell(int row, int col)
		: this(row, col, CellState.UnKnown)
	{ }
	public Cell(int row,int col, CellState state)
	{
		this.Row = row;
		this.Col = col;
		this.State = state;
	}
}

Thuộc tính NumOfWays của lớp Cell để lưu trữ số đường đi chưa được duyệt từ Cell hiện tại. Giá trị tối đa của thuộc tính này là 4 tương ứng với 4 hướng {Left, Right, Up, Down}. Thuộc tính này trong được dùng trong quá trình backtracking của DFS.

Các phương thức tìm đường đi BFS và DFS:

void GetPath(Cell cell)
{
	while (cell.Previous != null)
	{
		_data[cell.Row, cell.Col].State = CellState.Highlight;
		cell = cell.Previous;
	}
}
public void PerformStep()
{
	Cell p = Get();
	if (p == null)
	{
		timer1.Stop();
		MessageBox.Show("Cannot find the goal. Please click the Reset button.");
		return;
	}
	if (p.Row == _endPos.X && p.Col == _endPos.Y)
	{
		GetPath(p);
		timer1.Stop();
		_isFound = true;
	}
	else
		GenerateMove(p.Row, p.Col);

	Invalidate();
}
Cell Get()
{
	if (!_stackQueue.IsEmpty)
	{
		Cell cell = _stackQueue.Get();

		if (cell.Previous != null && cell.State != CellState.Visited)
			cell.Previous.NumOfWays--;

		cell.State = CellState.Visited;

		return cell;
	}
	return null;
}

bool Add(Cell previous, int row, int col)
{
	if (row < 0 || col < 0 || row >= _rows || col >= _columns)
		return false;

	if (!_isBackTracking)
	{
		if (_data[row, col].State != CellState.UnKnown)
			return false;

		_data[row, col].Previous = previous;
	}
	_stackQueue.Add(_data[row, col]);
	if (!_isBackTracking)
		_data[row, col].State = CellState.Queued;

	return true;
}
void GenerateMove(int row, int col)
{
	if (_isBackTracking)
		_data[_current.X, _current.Y].State = CellState.BackTracking;
	else
		_data[_current.X, _current.Y].State = CellState.Visited;

	_current.X = row;
	_current.Y = col;

	if (!IsDepthFirstSearch)
	{
		if (_isBackTracking && _data[row, col].NumOfWays > 0)
		{
			_isBackTracking = false;
			return;
		}

		if (_isBackTracking)
		{
			Cell pre = _data[row, col].Previous;
			if (pre == null)
				return;
			Add(_data[row, col], pre.Row, pre.Col);
			return;
		}
	}
	int count = 0;
	if (Add(_data[row, col], row - 1, col)) count++;
	if (Add(_data[row, col], row + 1, col)) count++;
	if (Add(_data[row, col], row, col - 1)) count++;
	if (Add(_data[row, col], row, col + 1)) count++;

	_data[row, col].NumOfWays = count;

	if (count == 0)
	{
		if (!IsDepthFirstSearch)
			_isBackTracking = true;
		Cell pre = _data[row, col].Previous;
		if (pre == null)
			return;
		Add(_data[row, col], pre.Row, pre.Col);
	}

}

Hiệu ứng Backtracking trong DFS

Nguyên tắc để thực hiện hiệu ứng backtracking như bạn thấy trong đoạn mã trên gồm có những điểm chính sau:

  • B1: Khi vị trí hiện tại không còn đường đi sẽ chuyển sang trạng thái backtracking.
  • B2: Chuyển đến vị trí trước vị trí hiện tại (dựa vào thuộc tính Previous của Cell).
  • B3: Nếu vị trí hiện tại còn không còn đường đi (NumOfWays = 0) quay lại B2, ngược lại chuyển sang B4.
  • B4: Hủy bỏ trạng thái backtracking.

https://yinyangit.wordpress.com

Advertisements

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s