Điểm của thuật toán IDA * so với A *

Question

Tôi không hiểu cách IDA* tiết kiệm dung lượng bộ nhớ. Từ cách tôi hiểu IDA* là A* với độ sâu lặp lại.

Sự khác biệt giữa dung lượng bộ nhớ A* sử dụng so với IDA* là gì.

Không phải lần lặp cuối cùng của IDA* hoạt động chính xác như A* và sử dụng cùng một lượng bộ nhớ. Khi tôi theo dõi IDA* Tôi nhận ra rằng nó cũng phải nhớ một hàng đợi ưu tiên của các nút nằm dưới ngưỡng f(n).

Tôi hiểu rằng tìm kiếm đầu tiên Độ sâu ID giúp chiều sâu tìm kiếm đầu tiên bằng cách cho phép nó thực hiện chiều rộng đầu tiên như tìm kiếm trong khi không phải nhớ mọi nút. Nhưng tôi nghĩ rằng A* đã hoạt động như chiều sâu đầu tiên như trong nó bỏ qua một số cây con trên đường đi. Làm thế nào để làm sâu sắc hơn làm cho nó sử dụng ít bộ nhớ hơn?

Một câu hỏi khác là tìm kiếm đầu tiên Độ sâu với độ sâu lặp lại cho phép bạn tìm đường đi ngắn nhất bằng cách làm cho nó hoạt động theo chiều rộng đầu tiên như thế nào. Nhưng A* đã trả lại đường đi ngắn nhất tối ưu (cho rằng heuristic được chấp nhận). Làm thế nào để làm sâu sắc lặp đi lặp lại giúp nó. Tôi cảm thấy giống như lần lặp cuối cùng của IDA * giống hệt với A*.

Answer 1

Trong IDA*, không giống như A*, bạn không cần phải giữ một tập hợp các nút dự kiến ​​mà bạn định ghé thăm, do đó, mức tiêu thụ bộ nhớ của bạn chỉ dành riêng cho các biến địa phương của hàm đệ quy.

Mặc dù thuật toán này là thấp hơn về tiêu thụ bộ nhớ, nó có lỗ hổng riêng của mình:

Không giống như A *, IDA * không sử dụng lập trình năng động và do đó thường kết thúc lên khám phá các nút tương tự nhiều lần. (IDA* In Wiki)

Chức năng heuristic, vẫn cần phải được chỉ định cho trường hợp của bạn để không quét toàn bộ đồ thị, tuy nhiên bộ nhớ của quét cần thiết trong từng khoảnh khắc chỉ là con đường mà bạn đang quét mà không hạch xung quanh nó.

Đây là một bản demo của bộ nhớ cần thiết trong mỗi thuật toán:

Trong thuật toán A* tất cả các nút và các nút xung quanh của họ cần phải được đưa vào "nhu cầu truy cập "danh sách trong khi ở số IDA* bạn sẽ nhận được các nút tiếp theo" lười biếng "khi bạn đạt đến nút xem trước của nó, do đó bạn không cần phải bao gồm nó trong một tập hợp thêm.

Như đã đề cập trong các ý kiến, IDA* is basically just IDDFS with heuristics: