Giải thuật tìm kiếm theo chiều sâu

1. Kỹ thuật tìm kiếm sâu 
Tìm kiếm sâu trong không gian bài toán được bắt đầu từ một nút rồi tiếp tục cho đến khi hoặc đến ngõ cụt hoặc đến đích. Tại mỗi nút có luật trong tài, chẳng hạn, “đi theo nút cực trái”, hướng dẫn việc tìm. Nếu không đi tiếp được, gọi là đến ngõ cụt, hệ thống quay lại một mức trên đồ thị và tìm theo hướng khác, chẳng hạn, đến nút “sát nút cực trái”. Hành động này gọi là quay lui.
Thuật toán tìm kiếm theo chiều sâu được hình dung như việc khảo sát một cây bắt đầu từ gốc đi theo mọi cành có thể được, khi gặp cành cụt thì quay lại xét cành chưa đi qua.
- Ở bước tổng quát, giả sử đang xét đỉnh i, khi đó các đỉnh kề với i có các trường hợp:
  + Nếu tồn tại đỉnh j kề i chưa được xét thì xét đỉnh này (nó trở thành đỉnh đã xét) và bắt đầu từ đó tiếp tục quá trình tìm kiếm với đỉnh này..
  + Nếu với mọi đỉnh kề với i đều đã được xét thì i coi như duyệt xong và quay trở lại tìm kiếm từ đỉnh mà từ đó ta đi đến được i.

2. Giải thuật
Input:
Cây/Đồ thị G = (V,E) với đỉnh gốc là n0 (trạng thái đầu)
    Tập đích Goals
Output:
Một đường đi p từ n0 đến một đỉnh n* in Goals
Method:
Sử dụng hai danh sách hoạt động theo nguyên tắc LIFO (Stack)  OPENLIST và CLOSELIST

            openList.Push(n0);
            while (!openList.IsEmpty())
            {
                node = openList.Pop();
                if (node.Equals(n*))
                {
                    result = true;
                    break;
                }

                closeList.Push(node);
                for (n in Tn(Node))
                {
                    if (!openList.InList(n) && !closeList.InList(n))
                    {
                        openList.Push(n);
                BeforeOfNode(n, node);////node trước của n là node trong quá trình tìm đường đến đích
                    }
                }
            }

            if (result)
            {
                DisplayResult();
            }
            else
            {
                NotFound();
            }
3. Ví dụ

Cho đồ thị như hình vẽ

Đỉnh xuất phát là (1), đỉnh đích là (11)

Các bước chi tiết thực hiện giải thuật

 

 Kết quả đường đi là:

4. Ưu và nhược điểm của phương pháp tìm kiếm sâu
Ưu điểm:
- Nếu bài toán có lời giải, phương pháp tìm kiếm sâu bảo đảm tìm ra lời giải.
- Kỹ thuật tìm kiếm sâu tập trung vào đích, con người cảm thấy hài lòng khi các câu hỏi tập trung vào vấn đề chính.
- Do cách tìm của kỹ thuật này, nếu lời giải ở rất sâu, kỹ thuật tìm sâu sẽ tiết kiệm thời gian.
Nhược điểm:
- Tìm sâu khai thác không gian bài toán để tìm lời giải theo thuật toán đơn giản một cách cứng nhắc. Trong quá trình tìm nó không có thông tin nào hổ trợ để phát hiện lời giải. Nếu chọn nút ban đầu không thích hợp có thể không dẫn đến đích của bài toán.
- Không phù hợp với không gian bài toán lớn, kỹ thuật tìm kiếm sâu có thể không đến lời giải trong khoảng thời gian vừa phải.

Mã nguồn tham khảo tại đây