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

Phương pháp tìm kiếm theo chiều sâu.

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

          Tìm kiếm sâu trong không gian bài toán được bắt đầu từ một nút rồi tiếp tục cho đến khi hoặc đến ngõ cụt hoặc đến đích. Tại mỗi nút có luật trong tài, chẳng hạn, “đi theo nút cực trái”, hướng dẫn việc tìm. Nếu không đi tiếp đựoc, gọi là đến ngõ cụt, hệ thống quay lại một mức trên đồ thị và tìm theo hướng khác, chẳng hạn, đến nút “sát nút cực trái”. Hành động này gọi là quay lui.

Thuật toán tìm kiếm theo chiều sâu được hình dung như việc khảo sát một cây bắt đầu từ gốc đi theo mọi cành có thể được, khi gặp cành cụt thì quay lại xét cành chưa đi qua.

- Ở bước tổng quát, giả sử đang xét đỉnh i, khi đó các đỉnh kề với i có các trường hợp:

+ Nếu tồn tại đỉnh j kề i chưa được xét thì xét đỉnh này (nó trở thành đỉnh đã xét) và bắt đầu từ đó tiếp tục quá trình tìm kiếm với đỉnh này..

+ Nếu với mọi đỉnh kề với i đều đã được xét thì i coi như duyệt xong và quay trở lại tìm kiếm từ đỉnh mà từ đó ta đi đến được i.

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 Goals

Output:

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

Method:

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

Procedure   DFS; (Depth First Search)

Begin

          Push (MO,n_o)

          DONG=null;

          While  MO <> null  do

                             begin

                                      n:=pop (MO);

                                      if nÎDICH then exit;

                                      push (DONG, n);

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

                                                Push (MO, m);

                             end;  

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

End;

Chú ý:Thủ tục Push(MO,n₀) thực hiện việc bổ sung n₀ vào stack MO

           Hàm Pop(MO) lấy phần tử đầu tiên trong Stack MO.

. Đánh giá độ phức tạp của thuật toán tìm kiếm sâu.

          Gải sử nghiệm của bài toán là đường đi có độ dài d, cây tìm kiếm có nhân tố nhánh là k. Có thể xãy ra nghiệm là đỉnh cuối cùng được xét ở mức d+1 theo luật trọng tài. Khi đó độ phức tạp thời gian của thuật toán tìm kiếm theo chiều sâu trong trường hợp xấu nhất là O(k^d).

          Để đánh giá độ phức tạp không gian của thuật toán tìm kiếm sâu ta có nhận xét ràng: Khi xét đỉnh j, ta chỉ cần lưu các đỉnh chưa được xét mà chúng là những đỉnh con của những đỉnh nằm trên đường đi từ đỉnh gốc đến j. Vì vậy chỉ cần lưu tối đa la k*d. Do đó độ phức tạp không gian của thuật toán là O(k*d).