Tìm kiếm Heuristic và A*

Tìm kiếm heuristic sử dụng ước tính chi phí còn lại đến mục tiêu, cụ thể cho từng vấn đề, để hướng dẫn việc khám phá các trạng thái nào trước tiên; A* là thuật toán chuẩn của phương pháp này, mở rộng các trạng thái theo thứ tự tổng chi phí đã đi được và chi phí ước tính còn lại.

Definition

Tìm kiếm heuristic là tìm kiếm có thông tin, sắp xếp biên bằng cách sử dụng một hàm đánh giá kết hợp chi phí đã biết từ điểm bắt đầu với ước tính heuristic về chi phí còn lại; A* sử dụng f(n) = g(n) + h(n) và tối ưu khi h là chấp nhận được.

Scope

Chủ đề này bao gồm các chiến lược tìm kiếm có thông tin (heuristic), tập trung vào tìm kiếm tốt nhất đầu tiên và thuật toán A*, bao gồm thiết kế và các thuộc tính của hàm heuristic (tính chấp nhận được, tính nhất quán/đơn điệu), các đảm bảo về tính tối ưu và hiệu quả mà các thuộc tính này mang lại, và các biến thể giới hạn bộ nhớ như A* lặp sâu dần (IDA*). Nó đề cập đến cách các heuristic được xây dựng (các bài toán được nới lỏng, cơ sở dữ liệu mẫu) và cách chúng đánh đổi độ chính xác với tính toán. Việc học các heuristic từ dữ liệu thuộc về phân ngành học máy.

Core questions

• Điều gì làm cho một heuristic chấp nhận được, và tại sao tính chấp nhận được đảm bảo tính tối ưu của A*?
• Tính nhất quán (đơn điệu) củng cố các đảm bảo và ngăn chặn việc mở rộng lại nút như thế nào?
• Các heuristic tốt được thiết kế như thế nào, ví dụ từ các phiên bản được nới lỏng của bài toán?
• Các biến thể giới hạn bộ nhớ như IDA* duy trì tính tối ưu với không gian hạn chế như thế nào?

Key concepts

• hàm đánh giá f = g + h
• heuristic chấp nhận được
• heuristic nhất quán (đơn điệu)
• tìm kiếm tốt nhất đầu tiên tham lam
• tìm kiếm A*
• A* lặp sâu dần (IDA*)
• ưu thế heuristic
• bài toán được nới lỏng và cơ sở dữ liệu mẫu

Key theories

Tính tối ưu của A* dưới các heuristic chấp nhận được

Khi heuristic h không bao giờ đánh giá quá cao chi phí thực sự còn lại, A* mở rộng các nút bằng cách tăng f = g + h và được đảm bảo trả về một đường đi có chi phí thấp nhất; trong số các thuật toán sử dụng cùng thông tin heuristic, A* có hiệu quả tối ưu.

Thiết kế heuristic thông qua nới lỏng

Các heuristic chấp nhận được có thể được suy ra một cách có hệ thống bằng cách giải một phiên bản được nới lỏng của bài toán (một phiên bản có ít hạn chế hơn về hành động), vì chi phí chính xác của một bài toán dễ hơn là một cận dưới cho bài toán gốc; các heuristic ưu thế (có nhiều thông tin hơn) mở rộng ít nút hơn.

Tìm kiếm heuristic giới hạn bộ nhớ

A* lặp sâu dần thực hiện các tìm kiếm theo chiều sâu liên tiếp được giới hạn bởi một ngưỡng chi phí f tăng dần, đạt được tính tối ưu giống A* với bộ nhớ tuyến tính theo độ sâu của giải pháp.

Clinical relevance

Tìm kiếm heuristic cung cấp năng lượng cho việc tìm đường trong bản đồ và trò chơi, lập kế hoạch chuyển động trong robot học, và các công cụ tìm kiếm bên trong các bộ lập kế hoạch tự động và giải câu đố; nghệ thuật thực tiễn của thiết kế heuristic trực tiếp quyết định liệu các bài toán lớn có thể giải được trong thời gian chấp nhận được hay không.

History

Thuật toán A* được giới thiệu bởi Hart, Nilsson, và Raphael (1968), mang lại cho tìm kiếm heuristic một cơ sở tối ưu hóa chính thức. Chuyên khảo Heuristics năm 1984 của Pearl đã cung cấp cách xử lý lý thuyết dứt khoát, và IDA* năm 1985 của Korf đã giải quyết chi phí bộ nhớ của A*. Những kết quả này vẫn là tài liệu cốt lõi trong giáo dục AI.

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

Heuristic chấp nhận được là gì?

Một heuristic được chấp nhận nếu nó không bao giờ đánh giá quá cao chi phí thực sự để đạt được mục tiêu từ bất kỳ trạng thái nào. Tính chấp nhận được là điều kiện mà theo đó A* được đảm bảo tìm ra một giải pháp tối ưu (chi phí thấp nhất).

Sự khác biệt giữa tìm kiếm tốt nhất đầu tiên tham lam và A* là gì?

Tìm kiếm tốt nhất đầu tiên tham lam mở rộng trạng thái dường như gần mục tiêu nhất chỉ dựa trên heuristic (h), điều này nhanh nhưng có thể không tối ưu. A* thêm chi phí thực tế đã phát sinh cho đến nay (g), mở rộng theo f = g + h, điều này duy trì tính tối ưu khi heuristic được chấp nhận.