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

Tìm kiẾm sâu dẦn

Kỹ thuật tìm kiếm sâu dần.

    Kỹ thuật tìm kiếm sâu dần là thực hiện việc tìm kiếm với độ sâu ở mức giới hạn d nào đó. Nếu không tìm ra nghiệm ta tăng độ sâu lên d+1 và lại tìm kiếm theo độ sâu tới mức d+1. Quá trình trên được lặp lại với d lần lượt là 1, 2,...đến độ sâu max nào đó. 

Kỹ thuật tìm kiếm sâu dần thường được thực hiện khi cây tìm kiếm chứa nhánh vô hạn, và nếu sử dụng tìm kiếm theo độ sâu ta có thể mắc kẹt ở một nhánh nào đó (thuật toán không dừng) và không tìm ra nghiệm.

Giải thuật.

    Thuật toán tìm kiếm sâu dần sử dụng thuật toán tìm kiếm sâu hạn chế như thủ tục con. Đó là thủ tục tìm kiếm theo chiều sâu nhưng chỉ tới độ sâu d nào đó rồi quay lên.

Thủ tục tìm kiếm sâu hạn chế (depth_limitedsearch)

Procedure Depth_limited_search(d);                      {d là tham số độ sâu}

      Begin

                  Push (MO,n_o);

                  Depth(n₀)=0;                         {hàm depth ghi lại độ sâu mỗi đỉnh}

                  DONG=null;

      While  MO <> null  do

                              begin

                                          n:=pop (MO);

                                          if nÎDICH then exit;

                                          push (DONG, n);

                                          if depth(n)<=d then

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

                                                        begin           

Push (MO, m);

depth(m)=depth(n)+1;

                                                         end;

                              end;   

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

      End

Thuật toán tìm kiếm sâu dần (Depth_deepening_search)sẽ sử dụng thủ tục tìm kiếm sâu hạn chế như thủ tục con:

Procedure Depth_deepening_search;

Begin

      For d:=0 to max do

                  Depth_limited_search(d);

      If thành công then exit;                  

End;

Nhận xét.

-                    Luôn tìm ra nghiệm (nếu bài toán có nghiệm), miễn là chọn max đủ lớn (giống như tìm kiếm theo chiều rộng)

-                    Có độ phức tạp thời gian là O(k^d) (giống tìm kiếm rộng)

-                    Có độ phức tạp không gian là O(k*d) (giống tìm kiếm sâu)                 

Giải thuật tìm kiếm sâu dần thương áp dụng cho các bài toán có không gian trạng thái lớn và độ sâu của nghiệm không biết trước