Tên gọi khác: Tìm kiếm Chi phí Đồng nhất
• Một cách tiếp cận BFS đơn giản về mặt khái niệm khi có chi phí chuyển đổi
• Dùng hàng đợi ưu tiên
Một hàng đợi ưu tiên là một cấu trúc dữ liệu trong đó ta có thể thêm và lấy các cặp (thing, value) với các toán tử sau:
•Init-PriQueue(PQ) khởi tạo PQ rỗng.
•Insert-PriQueue(PQ, thing, value) thêm (thing, value) vào hàng đợi.
•Pop-least(PQ) trả về cặp (thing, value) với giá trị thấp nhất, và loại bỏ nó khỏi hàng đợi.
Hàng đợi Ưu tiên có thể được cài đặt theo một cách sao cho chi phí của các toán tử thêm và lấy là
•Chi phí rất thấp (dù không tuyệt đối, nhưng vô cùng hấp dẫn!)
• O(log(số mục trong hàng đợi ưu tiên))
Tìm kiếm Chi phí Đồng nhất (UCS)
• Một cách tiếp cận BFS đơn giản về mặt khái niệm khi có chi phí chuyển đổi
• Dùng hàng đợi ưu tiên PQ = Tập trạng thái đã được mở hay đang đợi mở
• Độ ưu tiên của trạng thái s = g(s) = chi phí đến s dùng đường đi cho bởi con trỏ quay lui.
• Một cách tiếp cận BFS đơn giản về mặt khái niệm khi có chi phí chuyển đổi
• Dùng hàng đợi ưu tiên
Một hàng đợi ưu tiên là một cấu trúc dữ liệu trong đó ta có thể thêm và lấy các cặp (thing, value) với các toán tử sau:
•Init-PriQueue(PQ) khởi tạo PQ rỗng.
•Insert-PriQueue(PQ, thing, value) thêm (thing, value) vào hàng đợi.
•Pop-least(PQ) trả về cặp (thing, value) với giá trị thấp nhất, và loại bỏ nó khỏi hàng đợi.
•Chi phí rất thấp (dù không tuyệt đối, nhưng vô cùng hấp dẫn!)
• O(log(số mục trong hàng đợi ưu tiên))
• Một cách tiếp cận BFS đơn giản về mặt khái niệm khi có chi phí chuyển đổi
• Dùng hàng đợi ưu tiên PQ = Tập trạng thái đã được mở hay đang đợi mở
• Độ ưu tiên của trạng thái s = g(s) = chi phí đến s dùng đường đi cho bởi con trỏ quay lui.
Chương trình mô phỏng thuật toán UCS chạy đồ họa tại: Demo UCS
0 nhận xét:
Đăng nhận xét