Giải thuật tìm kiếm theo chiều rộng

1. Kỹ thuật tìm kiếm rộng
Kỹ thuật tìm kiếm rông là tìm kiếm trên tất cả các nút của một mức trong không gian bài toán trước khi chuyển sang các nút của mức tiếp theo.
Kỹ thuật tìm kiếm rộng bắt đầu từ mức thứ nhất của không gian bài toán, theo hướng dẫn của luật trọng tài, chẳng hạn “đi từ trái sang phải”. Nếu không thấy lời giải tại mức này, nó chuyển xuống mức sau để tiếp tục … đến khi định vị được lời giải nếu có.
 
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:
Để thực hiện giải thuật này ta sử dụng hai danh sách hoạt động theo nguyên tắc FIFO (queue)  OPENLIST và CLOSELIST


            bool result = false;

            openList.Append(n0);


            while (!openList.IsEmpty())
            {
                node = openList.Take();

                if (node.Equals(n*))//là node đích
                {
                    result = true;
                    break;
                }

                closeList.Append(node);
                for (n in Tn(Node))
                {
                    if (!openList.InList(n) && !closeList.InList(n))
                    {
                        openList.Append(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 rộng
Ưu điểm
- Kỹ thuật tìm kiếm rộng là kỹ thuật vét cạn không gian trạng thái bài toán vì vậy sẽ tìm được lời giải nếu có.
- Đường đi tìm được đi qua ít đỉnh nhất.
Nhược điểm
- Tìm kiếm lời giải theo thuật toán đã định trước, do vậy tìm kiếm một cách máy móc; khi không có thông tin hổ trợ cho quá trình tìm kiếm, không nhận ra ngay lời giải.
- Không phù hợp với không gian bài oán kích thước lớn. Đối với loại bài toán này, phương pháp tìm rộng đối mặt với các nhu cầu:
  + Cần nhiều bộ nhớ theo số nút cần lưu trữ.
  + Cần nhiều công sức xử lý các nút, nhất là khi các nhánh cây dài, số nút tăng. 
  + Dễ thực hiện các thao tác không thích hợp, thừa, đưa đến việc tăng đáng kể số nút phải xử lý.
- Không hiệu qủa nếu lời giải ở sâu. Phương pháp này không phù hợp cho trường hợp có nhiều đường dẫn đến kết quả nhưng đều sâu.
- Giao tiếp với người dùng không thân thiện. Do duyệt qua tất cả các nút, việc tìm kiếm không tập trung vào một chủ đề. 

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