Home » Lập trình » [Thuật toán] Thuật toán tìm kiếm theo chiều rộng

[Thuật toán] Thuật toán tìm kiếm theo chiều rộng

Nên tham khảo trước Khái quát về các thuật toán tìm kiếm

Thuật toán tìm kiếm theo chiều rộng:

Thuật toán tìm kiếm theo chiều rộng (Breadth First Search) là một trong ba thuật toán tìm kiếm mù (tìm kiếm không có thông tin).

Ý tưởng về thuật toán tìm kiếm theo chiều rộng: Tại một đỉnh bất kì, ta phát triển tất cả các đỉnh kế với nó. (Điều này khác về thuật toán tìm kiếm theo chiều sâu).

 

Thuật toán:

Thuật toán tìm kiếm theo chiều rộng sử dụng:

  • Danh sách open để lưu các đỉnh đã được sinh ra và chờ được phát triển.
  • Danh sách close để lưu các đỉnh đã phát triển.
  • Biến father để lưu lại cha của mỗi đỉnh trên đường đi, father(v) = u nếu cha của đỉnh v là u; dựa vào father ta sẽ tìm ra đường đi từ đỉnh đầu đến đỉnh kết thúc.

Phía dưới là đoạn mã giả của thuật toán tìm kiếm theo chiều rộng.

int Breadth_First_Search {

Khởi tạo danh sách open chỉ chứa trạng thái ban đầu;

Khởi tạo danh sách close rỗng;

while(true) { // lặp vô hạn

if (open rỗng) return 0; //tìm kiếm thất bại

Chọn và loại trạng thái u ở đầu danh sách open;

Thêm u vào danh sách close;

for (mỗi trạng thái v kề u){

if (v không có trong close và open){

father(v) =u;

if (v là trạng thái kết thúc) return 1; //tìm kiếm thành công

Thêm v vào cuối danh sách open;

}

}

}

Đánh giá:

Trạng thái sinh ra trước sẽ được phát triển trước, do đó danh sách open được xử lý như hàng đợi (queue).
Thuật toán sẽ tìm được đường đi với chi phí nhỏ nhất nếu hàm tính chi phí chuyển từ trạng thái nàyđến trạng thái khác là hằng số dương. Nếu hàm tính chi phí có giá trị dương thay đổi ta có thể dùng danh sách open như hàng đợi với độ ưu tiên theo hàm tính chi phí.

 Độ phức tạp: 

Thuật toán tìm kiếm theo chiều rộng làm tiêu tốn khá nhiều thời gian và không gian bộ nhớ.

Gọi b là hệ số nhánh (số nhánh tối đa của một đỉnh bất kì). 

Gọi d là chiều cao của đường đi đáp án. 

Khi đó, độ phức tạp về thời gian và không gian bộ nhớ tăng theo cấp số mũ. (cực kì lớn) 

  • Thời gian: bd
  • Không gian bộ nhớ: bd
Độ sâu d Thời gian Không gian
4 11 giây 1 MB
6 18 giây 11 MB
8 31 giờ 11 GB
10 128 ngày 1 TB
12 35 năm 111 TB
14 3500 năm 11 111 TB

 

 

Share
Share
Free WordPress Themes - Download High-quality Templates