Bài viết sưu tầm

Giải thuật.

Input:

- Cây/Đồ thị G = (V,E) với đỉnh gốc là n₀ (trạng thái đầu)

     - Tập đích DICH.

Output:

- Một đường đi p từ n₀ đến một đỉnh n_* Î DICH.

Method:

- Sử dụng hai danh sách hoạt động theo nguyên tắc FIFO (queue) MO và DONG.

Procedure   BrFS; (Breadth First Search)

Begin

   Append(MO,no)

   DONG=null;

   While  MO <> null  do

                begin

                       n:= Take(MO);

                       if nÎ DICH then exit;

                       Append(DONG, n);

                       For  mÎ T(n) and mÏDONG+MO do

                             Append(MO, m);

                end;  

   Write (‘Không có lời giải’);

End;

Chú ý:

• Thủ tục Append(MO,n₀) bổ sung một phần tử vào queue MO.
• Hàm Take(MO) lấy một phần tử trong queue MO.
• Nếu G là cây thì không cần dùng danh sách DONG.

3.1.3 Đánh giá độ phức tạp của giải thuật tìm kiếm rộng.

Giả sử rằng, mỗi trạng thái khi được xét sẽ sinh ra k trạng thái kế tiếp. Khi đó ta gọi k là nhân tố nhánh. Nếu bài toán tìm được nghiệm theo phương pháp tìm kiếm rộng có độ sâu d, như vậy đỉnh đích sẽ nằm ở mức d+1, do đó số đỉnh cần xét lớn nhất là:

1 + k + k² + . . . + k^d.

Nghĩa là độ phức tạp thời gian của giải thuật là O(k^d). Độ phức tạp không gian cũng là O(k^d), vì tất cả các đỉnh của cây tìm kiếm ở mức d+1 đều phải lưu vào danh sách.

3.1.4 Ưu và nhược điểm của phương pháp tìm kiếm rộng.

3.1.4.1 Ư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.

3.1.4.2 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 toá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 quả 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ủ đề.