Sự khác nhau giữa Greedy-Search và Uniform-Cost-Search là gì?

Question

Khi tìm kiếm trên cây, sự hiểu biết của tôi về tìm kiếm chi phí đồng nhất là cho nút A, có nút con B, C, D với chi phí liên quan (10, 5, 7), thuật toán của tôi sẽ chọn C, có chi phí thấp hơn. Sau khi mở rộng C, tôi thấy các nút E, F, G với chi phí (40, 50, 60). Nó sẽ chọn 40, vì nó có giá trị tối thiểu từ cả 3.

Bây giờ, không phải chỉ giống như thực hiện Tìm kiếm tham lam, nơi bạn luôn chọn những gì có vẻ là hành động tốt nhất?

Ngoài ra, khi xác định chi phí đi từ các nút nhất định đến các nút khác, chúng ta có nên xem xét toàn bộ chi phí từ đầu cây đến nút hiện tại hay chỉ chi phí từ nút n sang nút n '?

Cảm ơn

Answer 1

Không. Sự hiểu biết của bạn không hoàn toàn đúng.

Nút tiếp theo sẽ được truy cập trong trường hợp tìm kiếm chi phí đồng nhất sẽ là D, vì tổng chi phí thấp nhất từ ​​gốc (7, ngược với 40 + 5 = 45).

Tìm kiếm tham lam không sao lưu cây - nó chọn giá trị thấp nhất và cam kết với giá trị đó. Uniform-Cost sẽ chọn tổng chi phí thấp nhất từ ​​toàn bộ cây.

Answer 2

Trong tìm kiếm chi phí đồng nhất, bạn luôn xem xét tất cả các nút chưa được xem trước đây bạn đã thấy, không chỉ các nút được kết nối với nút mà bạn đã xem. Vì vậy, trong ví dụ của bạn, sau khi chọn C, bạn sẽ thấy rằng lượt truy cập G có tổng chi phí là 40 + 5 = 45, cao hơn chi phí bắt đầu lại từ gốc và truy cập D, có chi phí 7. Vì vậy, bạn sẽ truy cập D tiếp theo.

Answer 3

Sự khác biệt giữa chúng là Greedy chọn nút có giá trị phỏng đoán thấp nhất trong khi UCS chọn nút có chi phí hành động thấp nhất. Considere đồ thị dưới đây:

Nếu bạn chạy cả hai thuật toán, bạn sẽ nhận được:

• UCS

Chọn lựa tiêu biểu: S (chi phí 0), B (chi phí 1), A (chi phí 2), D (chi phí 3), C (chi phí 5), G (chi phí 7)

Trả lời: S-> A-> D-> G

• tham lam:

* giả như nó chọn A thay vì B; A và B có cùng một giá trị tìm tòi

Chọn lựa tiêu biểu: S, A (h = 3), C (h = 1), G (h = 0)

Trả lời: S> A-> C- > G

Vì vậy, điều quan trọng là phải phân biệt chi phí hành động để đến nút từ giá trị phỏng đoán, là thông tin được thêm vào nút dựa trên trải nghiệm của tôi về sự cố.