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
Cảm nhận của cư dân mạng Nhật Bản về Conan movie 26: Tàu Ngầm Sắt Đen
Cảm nhận của cư dân mạng Nhật Bản về Conan movie 26: Tàu Ngầm Sắt Đen
Movie đợt này Ran đóng vai trò rất tích cực đó. Không còn ngáng chân đội thám tử nhí, đã thế còn giúp được cho Conan nữa, bao ngầu
FOMO - yếu tố khiến các Nhà đầu tư thua lỗ trên thị trường
FOMO - yếu tố khiến các Nhà đầu tư thua lỗ trên thị trường
Hãy tưởng tượng hôm nay là tối thứ 6 và bạn có 1 deadline cần hoàn thành ngay trong tối nay.
Giới thiệu Chloe Aubert: True Hero - Tensei Slime
Giới thiệu Chloe Aubert: True Hero - Tensei Slime
Chloe Aubert là một trong những đứa trẻ của Dị giới mà chúng ta gặp từ đầu trong anime nhưng sự thật đằng sau nhân vật của cô ấy là gì
Hướng dẫn sử dụng Bulldog – con ghẻ dòng rifle
Hướng dẫn sử dụng Bulldog – con ghẻ dòng rifle
Trước sự thống trị của Phantom và Vandal, người chơi dường như đã quên mất Valorant vẫn còn tồn tại một khẩu rifle khác: Bulldog