Trong tìm kiếm theo chiều sâu, bạn bắt đầu tại một số nút trong biểu đồ và liên tục khám phá sâu hơn vào biểu đồ trong khi bạn có thể tìm thấy các nút mới mà bạn chưa đạt đến (hoặc cho đến khi tìm thấy giải pháp). Bất cứ lúc nào DFS chạy ra khỏi di chuyển, nó quay trở lại điểm mới nhất, nơi nó có thể đưa ra một lựa chọn khác, sau đó khám phá ra từ đó. Đây có thể là một vấn đề nghiêm trọng nếu biểu đồ của bạn cực kỳ lớn và chỉ có một giải pháp, vì bạn có thể kết thúc khám phá toàn bộ biểu đồ dọc theo một đường dẫn DFS chỉ để tìm giải pháp sau khi xem từng nút. Tồi tệ hơn, nếu biểu đồ là vô hạn (có lẽ đồ thị của bạn bao gồm tất cả các số, ví dụ), tìm kiếm có thể không chấm dứt. Hơn nữa, khi bạn tìm thấy nút bạn đang tìm kiếm, bạn có thể không có đường dẫn tối ưu cho nó (bạn có thể đã lặp lại tất cả đồ thị tìm giải pháp mặc dù nó nằm ngay bên cạnh nút bắt đầu!)
Một giải pháp tiềm năng cho vấn đề này là giới hạn độ sâu của bất kỳ đường dẫn nào do DFS thực hiện. Ví dụ, chúng ta có thể thực hiện tìm kiếm DFS, nhưng dừng tìm kiếm nếu chúng ta có một chiều dài lớn hơn 5. Điều này đảm bảo rằng chúng ta không bao giờ khám phá bất kỳ nút nào có khoảng cách lớn hơn năm từ nút bắt đầu, có nghĩa là chúng ta không bao giờ khám phá ra vô hạn hoặc (trừ khi đồ thị cực kỳ dày đặc), chúng tôi không tìm kiếm toàn bộ biểu đồ. Tuy nhiên, điều này có nghĩa là chúng tôi có thể không tìm thấy nút mà chúng tôi đang tìm kiếm vì chúng tôi không nhất thiết phải khám phá toàn bộ biểu đồ.
Ý tưởng đằng sau việc làm sâu lặp lại là sử dụng phương pháp thứ hai này nhưng để tiếp tục tăng chiều sâu ở mỗi cấp. Nói cách khác, chúng ta có thể thử khám phá bằng cách sử dụng tất cả các đường dẫn có chiều dài một, sau đó tất cả các đường dẫn có chiều dài hai, sau đó là chiều dài ba, v.v. cho đến khi chúng ta tìm thấy nút đang được đề cập đến. Điều này có nghĩa rằng chúng ta không bao giờ kết thúc khám phá dọc theo các đường dẫn chết vô hạn, vì chiều dài của mỗi đường dẫn bị giới hạn bởi một số chiều dài ở mỗi bước. Nó cũng có nghĩa là chúng ta tìm đường dẫn ngắn nhất có thể đến nút đích, vì nếu chúng ta không tìm thấy nút ở độ sâu d nhưng đã tìm thấy nó ở độ sâu d + 1, không thể có đường dẫn dài d (hoặc chúng ta đã có thể lấy nó), do đó, đường dẫn của chiều dài d + 1 thực sự là tối ưu.
Lý do điều này khác với DFS là nó không bao giờ chạy vào trường hợp phải mất một đường dẫn rất dài và mạch quanh biểu đồ mà không bao giờ chấm dứt. Độ dài của đường dẫn luôn bị giới hạn, vì vậy chúng tôi không bao giờ kết thúc việc khám phá các nhánh không cần thiết.
Lý do điều này khác với BFS là trong BFS, bạn phải giữ tất cả các nút rìa trong bộ nhớ cùng một lúc. Điều này có bộ nhớ O (b d), trong đó b là hệ số phân nhánh. So sánh điều này với việc sử dụng bộ nhớ O (d) từ làm sâu lặp lại (để giữ trạng thái cho mỗi nút d trong đường dẫn hiện tại). Tất nhiên, BFS không bao giờ khám phá cùng một đường dẫn nhiều lần, trong khi làm sâu lặp lại có thể khám phá bất kỳ đường dẫn nào nhiều lần vì nó làm tăng giới hạn độ sâu.Tuy nhiên, tiệm cận hai có cùng thời gian chạy. BFS kết thúc bằng O (b d) các bước sau khi xem xét tất cả các nút O (b d) ở khoảng cách d. Độ sâu lặp đi lặp lại sử dụng O (b d) thời gian cho mỗi cấp độ, tổng lên tới tổng thể O (b d), nhưng với một hệ số không đổi cao hơn.
Nói tóm lại:
- DFS không được bảo đảm để tìm một con đường tối ưu; lặp lại sâu sắc là.
- DFS có thể khám phá toàn bộ biểu đồ trước khi tìm nút đích; làm sâu lặp đi lặp lại chỉ thực hiện điều này nếu khoảng cách giữa nút bắt đầu và nút kết thúc là mức tối đa trong biểu đồ.
- BFS và làm sâu lặp lại cả hai chạy trong O (b d), nhưng làm sâu lặp lại có hệ số cố định cao hơn.
- BFS sử dụng bộ nhớ O (b d), trong khi làm sâu lặp lại chỉ sử dụng O (d).
Hope this helps!
Trong tìm kiếm theo chiều sâu, bạn khám phá từng chi nhánh bạn nhập hoàn toàn trước khi quay lại từ nó và chuyển sang bước tiếp theo. Trong việc làm sâu lặp đi lặp lại, bạn không đi sâu dưới độ sâu hiện tại, và do đó không khám phá từng chi nhánh bạn truy cập hoàn toàn trước khi quay lại. – HelloGoodbye