Heuristic

Heuristic h(n) ước lượng chi phí từ n đến đích. Nó giúp ưu tiên hướng tìm kiếm có triển vọng. Một ước lượng admissible không vượt chi phí tối ưu thực sự còn lại. Consistent còn thỏa $h(n)\le c(n,n^{\prime })+h(n^{\prime })$ trên mỗi cạnh.

Lĩnh vực: Giải thuật & cấu trúc dữ liệu

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Bài giảng dùng khái niệm này

• Tìm kiếm kinh nghiệm: Greedy & A*Tri thức & Tìm kiếm

Giải thích kỹ thuật

Điều kiện tối ưu của A.* Với h(goal)=0, admissible yêu cầu h không vượt chi phí tối ưu còn lại. Consistent yêu cầu $h(n)\le c(n,n^{\prime })+h(n^{\prime })$ cho mỗi cạnh. Consistency giúp f không giảm dọc đường đi và cho phép đóng thuận lợi hơn trong search.

Nếu chỉ có admissibility, một số cách cài đặt search phải cho phép mở lại để giữ bảo đảm tối ưu. Một heuristic nhanh nhưng ước lượng quá cao có thể làm mất bảo đảm đó.

Ví dụ

Khoảng cách đường chim bay không vượt độ dài đường bộ nếu mọi chi phí là độ dài không âm.

Khi nào cần dùng?

Phân biệt tìm kiếm mù với Greedy và A*. Đọc điều kiện tối ưu.

Câu hỏi ôn lại

Heuristic 8 có admissible nếu chi phí tối ưu còn lại là 5 không?

Xem đáp án

Không, vì 8 đã ước lượng quá cao.

Thuật ngữ liên quan

• Trạng thái
• Hàng đợi ưu tiên
• Đồ thị
• Độ phức tạp