Giải thuật A* với bộ nhớ hữu hạn?

Công nghệ thông tin

Cho một bài toán với bộ nhớ giới hạn, các trạng thái quá lớn để có thể đưa vào bộ nhớ. Mình sẽ sử dụng A* với 1 admissible heuristic để search cho đến khi đầy bộ nhớ. Tại thời điểm đó, mình sẽ chọn một điểm N gần nhất với đích.

Sau đó mình sẽ chọn N làm gốc của search tree mới.

Hỏi: Cách làm này có còn tối ưu không? Vì sao?

Từ khóa:

công nghệ thông tin

Không hiểu rõ mô tả cách làm ở câu hỏi lắm. Nhưng A* về cơ bản implement như sau:

Dùng Priority Heap để lưu trữ chi phí (ước lượng) của việc đi qua các node. Dùng Heap để tăng performance thôi, vì mình luôn cần lấy node có chi phí tốt nhất ra, và bỏ đi những node có chi phí cao nhất (khi Heap bị đầy).
Khởi tạo từ node nguồn.
Lấy node có chi phí tốt nhất nhất từ Heap, giả xử là A, update các node láng riềng của nó vào Heap, giả sử là các Bi, với chi phí tính của Bi tính bằng: chi phí đi đến A + chi phí từ A đến Bi + chi phí ước lượng từ Bi đến đích.
Nếu Heap đầy thì bỏ đi những node có chi phí cao nhất.

Trả lời

Đỗ Mạnh Dũng

Không hiểu rõ mô tả cách làm ở câu hỏi lắm. Nhưng A* về cơ bản implement như sau:

Dùng Priority Heap để lưu trữ chi phí (ước lượng) của việc đi qua các node. Dùng Heap để tăng performance thôi, vì mình luôn cần lấy node có chi phí tốt nhất ra, và bỏ đi những node có chi phí cao nhất (khi Heap bị đầy).
Khởi tạo từ node nguồn.
Lấy node có chi phí tốt nhất nhất từ Heap, giả xử là A, update các node láng riềng của nó vào Heap, giả sử là các Bi, với chi phí tính của Bi tính bằng: chi phí đi đến A + chi phí từ A đến Bi + chi phí ước lượng từ Bi đến đích.
Nếu Heap đầy thì bỏ đi những node có chi phí cao nhất.