Tìm kiếm theo lựa chọn tốt nhất

Tìm kiếm theo lựa chọn tốt nhất (tiếng Anh: Best-first search) là một thuật toán tìm kiếm tối ưu hóa tìm kiếm theo chiều rộng bằng cách mở rộng nút hứa hẹn nhất được chọn theo một quy tắc nào đó.

Judea Pearl mô tả tìm kiếm theo lựa chọn tốt nhất là việc ước lượng mức độ hứa hẹn của nút n theo một "hàm đánh giá heuristic . Hàm này nói chung có thể phụ thuộc vào mô tả của n, mô tả về điểm đích, thông tin thu thập được bởi quá trình tìm kiếm cho tới thời điểm đó, và quan trọng nhất là phụ thuộc vào mọi tri thức bổ sung về miền xác định của bài toán."[1] Nhiều tác giả đã sử dụng nghĩa tổng quát này của thuật ngữ, trong đó có Russell & Norvig.[2]

Các tác giả khác đã sử dụng tìm kiếm theo lựa chọn tốt nhất để chỉ cụ thể đến quá trình tìm kiếm sử dụng một cách đánh giá heuristic ước lượng khoảng cách từ điểm cuối của một đường đi tới một điểm đích, từ đó các đường đi được phán đoán là gần đích hơn sẽ được mở rộng trước. Russell & Norvig gọi loại tìm kiếm cụ thể này là tìm kiếm ăn tham theo lựa chọn tốt nhất.[2]

Để có được hiệu quả về thời gian chạy cho việc chọn ra ứng cử viên tốt nhất cho việc mở rộng, người ta thường dùng một hàng đợi ưu tiên để cài đặt cấu trúc dữ liệu lưu trữ các lựa chọn hiện hành.

Ví dụ về các thuật toán tìm kiếm theo lựa chọn tốt nhất là thuật toán Dijkstragiải thuật tìm kiếm A*. Các thuật toán tìm kiếm theo lựa chọn tốt nhất thường được sử dụng để tìm đường trong quá trình tìm kiếm tổ hợp.

Tham khảo

[sửa | sửa mã nguồn]
  1. ^ Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
  2. ^ a b Russell, S.J., & Norvig, P.  Artificial Intelligence: A Modern Approach. 2nd edition. Pearson Education, Inc, 2003. pp. 94 and 95 (note 3).

Liên kết ngoài

[sửa | sửa mã nguồn]
Chúng tôi bán
Bài viết liên quan
Giới thiệu TV Series Jupiter's Legacy
Giới thiệu TV Series Jupiter's Legacy
Jupiter's Legacy là một loạt phim truyền hình trực tuyến về siêu anh hùng của Mỹ do Steven S. DeKnight phát triển
Tổng quan về vị trí Event Planner trong một sự kiện
Tổng quan về vị trí Event Planner trong một sự kiện
Event Planner là một vị trí không thể thiếu để một sự kiện có thể được tổ chức suôn sẻ và diễn ra thành công
Evil Does Not Exist: ở nơi đâu cái ác không tồn tại?
Evil Does Not Exist: ở nơi đâu cái ác không tồn tại?
Lòng tốt có tồn tại, tình yêu có tồn tại, lòng vị tha có tồn tại, nhưng cái ác lại không tồn tại.
Sung Il-Hwan: Thợ Săn Hạng S Huyền Thoại và Hành Trình Bảo Vệ Gia Đình
Sung Il-Hwan: Thợ Săn Hạng S Huyền Thoại và Hành Trình Bảo Vệ Gia Đình
Sung Il-Hwan (성일환) là một Thợ săn hạng S người Hàn Quốc và là cha của Jinwoo và Jinah