Home » Lập trình » [Thuật toán] 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 sâu

Nên tham khảo trước Thuật toán tìm kiếm theo chiều rộng.

Thuật toán tìm kiếm theo chiều sâu:

Thuật toán tìm kiếm theo chiều sâu (Depth First Search -DFS)  tương tự như thuật toán tìm kiếm theo bề rộng, chỉ có một điều khác là trong thuật toán tìm kiếm theo bề rộng (Breath First Search-BFS)  đó là cơ chế lưu trữ phần tử trong danh sách open. Để cài đặt tìm kiếm theo chiều rộng, ta dùng cấu trúc dữ liệu stack – dữ liệu cho và lấy ra ở cùng một đầu.
Do đó,  trong thuật toán tìm kiếm theo chiều sâu thì tại mỗi bước, trạng thái được chọn để phát triển là trạng thái được sinh ra sau cùng trong số các trạng thái chờ phát triển.

Xem lại Tìm kiếm theo bề rộng (Breath First Search-DFS)

Thuật toán: 

int Depth_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ô tập

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 đầu danh sách open; // điểm khác biệt duy nhất của DFS so với BFS

}

}

}

Nhn xét:

Trạng thái sinh ra sau sẽ được phát triển trước, do đó danh sách open được xử lý như  ngăn xếp (stack). ( khác với BFS là dùng hàng đợi (queue) ) .

Nếu bài toán có nghiệm và không gian trạng thái hữu hạn, thì thuật toán tìm kiếm theo độ sâu sẽ tìm ra nghiệm.

Nếu không gian trạng thái vô hạn thì có thể không tìm ra nghiệm, vì nếu đi theo một nhánh vô hạn mà nghiệm không nằm trên nhánh đó thì thuật toán sẽ không dừng. Do đó không nên áp dụng tìm kiếm theo độ sâu cho bài toán có cây tìm kiếm chứa nhánh vô hạn.

Độ phức tạp:

Thuật toán tìm kiếm theo chiều sâu làm tiêu tốn khá nhiều thời gian  tương tự như BFS nhưng tiết kiệm hơn 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à bộ nhớ lần lượt là:

  • Độ phức tạp: bd (tương tự như BFS)
  • Không gian bộ nhớ: bd
Share
Share
Free WordPress Themes - Download High-quality Templates