Tổng quan
Greedy Best-First Search lao về đích bằng cách luôn mở rộng nút trông gần nhất chỉ theo heuristic. Bỏ qua quãng đường đã đi, nó xếp hạng các ứng viên hoàn toàn theo chi phí ước lượng h tới đích.
Điều này khiến nó nhanh và thường tìm được lộ trình sớm, nhưng vì không bao giờ cân nhắc chi phí thực đã đi, đường nó trả về có thể xa mức ngắn nhất.
Tìm kiếm tham lam tốt nhất hoạt động thế nào?
- Ước lượng khoảng cách heuristic h từ nút xuất phát tới đích.
- Từ hàng đợi ưu tiên chỉ xếp theo h, mở rộng nút trông gần đích nhất.
- Thêm các hàng xóm chưa thăm của nó vào hàng đợi kèm ước lượng heuristic của chúng.
- Lặp lại đến khi tới đích, lần theo các liên kết cha để dựng lại lộ trình.
Khi nào nên dùng?
- Khi tốc độ quan trọng hơn tính tối ưu và một đường đi đủ tốt là chấp nhận được.
- Bản đồ mở lớn nơi một heuristic mạnh gần như chỉ thẳng về đích.
- Chuyển sang A* bất cứ khi nào đường trả về bắt buộc phải là ngắn nhất.
Phân tích độ phức tạp
Greedy Best-First Search có cùng trường hợp xấu nhất O((V + E) log V) của các tìm kiếm dựa trên heap, và với heuristic mạnh nó có thể nhanh hơn nhiều trong thực tế. Nhưng nó chỉ xét h và bỏ qua chi phí g đã trả, nên không tối ưu — vật cản có thể dụ nó vào một đường vòng dài mà nó không bao giờ sửa lại.
Câu hỏi thường gặp
Greedy Best-First khác A* thế nào?
A* xếp hạng nút theo f = g + h, cân bằng chi phí thực đã đi với ước lượng; tìm kiếm greedy chỉ dùng h. Bỏ đi g khiến greedy nhanh hơn nhưng đánh mất bảo đảm đường đi ngắn nhất.
Greedy Best-First Search có bao giờ tối ưu không?
Chỉ trong các trường hợp đặc biệt — ví dụ một lưới không vật cản nơi heuristic khớp chính xác khoảng cách thực. Nói chung nó có thể trả về đường dài hơn, đó là cái giá của việc bỏ qua chi phí đã đi.