Tìm kiếm theo lựa chọn tốt nhất
Bách khoa toàn thư mở Wikipedia
| Thuật toán tìm kiếm trên đồ thị |
|---|
Tìm kiếm
|
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 độ sâu 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 f(n). 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 Dijkstra và giả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.
[sửa] Xem thêm
- Beam search
[sửa] Tham khảo
- ▲ Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
- ▲ 2,0 2,1 Russell, S.J., & Norvig, P. Artificial Intelligence: A Modern Approach. 2nd edition. Pearson Education, Inc, 2003. pp. 94 and 95 (note 3).
