6
Tôi đang nghiên cứu tìm kiếm chi nhánh và ràng buộc và tốt nhất đầu tiên cho công việc luận án của mình nhưng đã tìm thấy rất nhiều mâu thuẫn trên web về hai khái niệm này. Đầu tiên tôi nghĩ chi nhánh và ràng buộc chỉ tỉa cành nhánh kết thúc với giải pháp chi phí cao (sử dụng heuristic) và không ưu tiên tìm kiếm (làm một DFS đơn giản hoặc BFS trên phần còn lại của cây sau khi cắt tỉa). Tuy nhiên, sau này tôi tìm thấy nhiều tài nguyên nói rằng BB cũng xếp hạng các trạng thái và xem xét các nút có xếp hạng cao hơn đầu tiên (một tìm kiếm được ưu tiên). Nếu nó là như vậy, sự khác biệt chính xác giữa BB và tìm kiếm tốt nhất là gì?Sự khác biệt giữa tìm kiếm chi nhánh và giới hạn và tìm kiếm tốt nhất đầu tiên
Điều tôi hiểu là: tìm kiếm đầu tiên chỉ xem xét chi phí đạt trạng thái (tức là tổng chi phí từ trạng thái gốc đến trạng thái đó) để xếp hạng , nhưng BB sử dụng chi phí tối thiểu ước tính của việc có các giải pháp hoàn chỉnh thông qua trạng thái đó. Tôi có đúng không? – Barpa
Không, Đầu tiên tốt nhất cố gắng chọn nút tiếp theo để xử lý bằng cách sử dụng ước tính chi phí toàn cầu và không chỉ chi phí hiện tại. Hãy xem xét một vấn đề chuyển hướng mà bạn có thể sử dụng Dijkstra để tạo ra các cây con đường ngắn nhất. Chỉ nhìn vào chi phí để đạt được trạng thái hiện tại là chính xác những gì Dijkstra làm bằng cách chọn nút có khoảng cách dự kiến thấp nhất để giải quyết tiếp theo. Bằng cách áp dụng Best First cho nó, bạn sẽ nhận được A * như trong A *, bạn luôn chọn nút có ước tính tổng chi phí thấp nhất. – Origin
Xin lỗi, nhưng bây giờ tôi thấy bối rối hơn. Bạn nói tốt nhất đầu tiên chọn nút tiếp theo bằng cách sử dụng ước tính chi phí toàn cầu. Không phải là ước tính chi phí toàn cầu giống như chi nhánh bị ràng buộc toàn cầu (thấp hơn hoặc cao hơn) và sử dụng bị ràng buộc để so sánh với trạng thái hiện tại bị ràng buộc? – Barpa