Cách triển khai thuật toán AO *?

Question

Tôi đã nhận thấy rằng một số cấu trúc dữ liệu được sử dụng khi chúng tôi triển khai các thuật toán tìm kiếm. Ví dụ: Ví dụ, chúng tôi sử dụng hàng đợi để triển khai BFS, ngăn xếp để triển khai DFS và min-heap để triển khai thuật toán A *. Trong những trường hợp này, chúng tôi không cần phải xây dựng cây tìm kiếm một cách rõ ràng.

Nhưng tôi không thể tìm thấy cấu trúc dữ liệu đơn giản để mô phỏng quá trình tìm kiếm của thuật toán AO *. Tôi muốn biết nếu xây dựng cây tìm kiếm một cách rõ ràng là cách duy nhất để thực hiện thuật toán AO *? Ai có thể cung cấp cho tôi một thực hiện hiệu quả? Tôi thực sự đánh giá cao sự giúp đỡ của bạn.

Answer 1

Tuyên bố từ chối trách nhiệm: Tôi chưa triển khai AO *, do đó tôi có thể sai.

Triển khai AO * không được khác với A *. Bạn sử dụng một đống nhưng thay vì chỉ có một nút duy nhất, mỗi thành viên phải là một vectơ của các nút (một hoặc nhiều nút). Ở một mức độ nào đó, nó phụ thuộc vào các quy tắc (và - hoặc) được đưa ra cho bạn như thế nào, nhưng việc điền vào heap sẽ rất dễ dàng. Vì vậy, câu trả lời cho câu hỏi đầu tiên là không, không cần phải xây dựng cây một cách rõ ràng như trong ý nghĩa bạn không làm như vậy cho A *. Hãy nhớ một heap thực sự là một đại diện của một cây tìm kiếm, do đó, người ta có thể tranh luận bạn đang thực sự xây dựng cây khi bạn đi qua nó. Về số

Ai có thể cung cấp cho tôi triển khai hiệu quả không?

bạn cần hiển thị một số nỗ lực bằng cách cung cấp ít nhất một số mã giả hoặc thậm chí tốt hơn một đoạn mã hiển thị cách bạn đã tấn công vấn đề. Sau đó, chúng tôi có thể đưa ra các gợi ý về cách tăng hiệu quả bằng cách cải thiện cấu trúc dữ liệu.