Đầy đủ của tìm kiếm theo chiều sâu

Question

tôi trích dẫn từ Artificial Intelligence: A Modern Approach:

Các thuộc tính của tìm kiếm theo chiều sâu phụ thuộc mạnh mẽ vào việc phiên bản đồ tìm kiếm hoặc cây tìm kiếm được sử dụng. Phiên bản tìm kiếm đồ thị, tránh các trạng thái lặp lại và đường dẫn dư thừa, được hoàn thành trong các không gian trạng thái hữu hạn bởi vì nó sẽ mở rộng tất cả các nút. Ngược lại, phiên bản tìm kiếm cây là không phải là hoàn thành [...]. Tìm kiếm cây có độ sâu đầu tiên có thể được sửa đổi mà không tốn thêm chi phí bộ nhớ nào để nó kiểm tra các trạng thái mới so với các trạng thái trên đường dẫn từ gốc tới nút hiện tại; điều này tránh các vòng vô hạn trong không gian trạng thái hữu hạn nhưng không tránh sự gia tăng của các đường thừa.

Tôi không hiểu làm thế nào để tìm kiếm đồ thị hoàn thành và tìm kiếm theo cây không phải là cây, là một biểu đồ cụ thể.

Bên cạnh đó, tôi không nhận được rõ ràng sự khác biệt giữa "vòng lặp vô hạn" và "con đường dư thừa" ...

tháng một ai đó giải thích điều này với tôi?

ps. Đối với những người có cuốn sách đó là trang 86 (ấn bản thứ 3).

Answer 1

Tìm kiếm cây có độ sâu đầu tiên có thể bị kẹt trong một vòng lặp vô hạn, đó là lý do tại sao nó không "hoàn thành". Tìm kiếm đồ thị theo dõi các nút mà nó đã tìm kiếm, vì vậy nó có thể tránh được sau các vòng vô hạn.

"Đường dẫn dự phòng" là các đường dẫn khác nhau dẫn từ cùng một nút bắt đầu đến cùng một nút kết thúc. Tìm kiếm đồ thị vẫn sẽ khám phá tất cả các đường dẫn dư thừa này, nhưng khi nó đạt đến một nút mà nó đã truy cập trước đó, nó sẽ không đi xa hơn nữa, nhưng sẽ sao lưu và tìm kiếm nhiều đường dẫn mà nó chưa thử.

Điều này khác với "vòng lặp vô hạn" là đường dẫn dẫn từ nút quay lại chính nó.

Đáp lại bình luận của bạn, nhìn vào các báo mà bạn vừa đăng tải:

Depth-first tree search can be modified at no extra memory cost so that it checks new states against those on the path from the root to the current node.

Vì vậy, trong khi tìm kiếm cây sâu-đầu tiên thực hiện theo dõi các đường đi từ gốc đến nút hiện tại, để tránh các vòng lặp vô hạn, nó cần thực hiện tìm kiếm tuyến tính trên đường dẫn đó mỗi khi nó truy cập một nút mới. Nếu bạn đã viết một triển khai thực hiện tìm kiếm cây theo chiều sâu mà không thực hiện kiểm tra đó, nó có thể đi vào một vòng lặp vô hạn.

Bạn nói đúng, những gì sách nói về "sự gia tăng của các đường dẫn dư thừa" không liên quan đến tính đầy đủ. Nó chỉ là chỉ ra một sự khác biệt giữa đồ thị và tìm kiếm cây. Vì tìm kiếm cây chỉ theo dõi đường dẫn hiện tại , nó có thể chạy trên cùng một đường dẫn nhiều lần trong cùng một tìm kiếm (ngay cả khi thực hiện kiểm tra tôi vừa đề cập).

Nói nút gốc của bạn có 2 nhánh. Mỗi nhánh trong số đó dẫn đến cùng một nút đơn, có một đường dẫn dài dẫn ra từ nó. Tìm kiếm cây sẽ đi theo con đường dài đó hai lần, một lần cho mỗi nhánh trong 2 nhánh dẫn đến nó. Đó là những gì tác giả đang chỉ ra.