Bằng chứng về độ tối ưu của thuật toán A * khi chẩn đoán luôn đánh giá thấp

Question

Tôi hiểu tại sao thuật toán A * luôn mang lại đường đi tối ưu nhất cho trạng thái mục tiêu khi heuristic luôn đánh giá thấp, nhưng tôi không thể tạo ra bằng chứng chính thức cho nó.

Theo tôi hiểu, đối với mỗi con đường được coi là đi sâu hơn và sâu hơn, độ chính xác của f(n) tăng cho đến khi trạng thái mục tiêu, ở đó chính xác 100%. Ngoài ra, không có đường dẫn không chính xác bị bỏ qua, vì ước tính nhỏ hơn chi phí thực tế; do đó dẫn đến con đường tối ưu. Nhưng làm thế nào tôi nên tạo ra một bằng chứng cho nó?

Answer 1

Ý tưởng chính của bằng chứng là khi A * tìm thấy đường dẫn, nó có một đường dẫn có ước tính thấp hơn ước tính của bất kỳ đường dẫn nào khác có thể. Vì các ước tính là lạc quan, các đường dẫn khác có thể được bỏ qua một cách an toàn.

Ngoài ra, A * là chỉ tối ưu nếu hai điều kiện được đáp ứng:

1. Các heuristic là chấp nhận, vì nó sẽ không bao giờ đánh giá quá cao chi phí.

2. Các heuristic là đơn điệu, nghĩa là, nếu h (n _i) < h (n _{i + 1}), sau đó chi phí thực tế (n _i) < gian thực chi phí (n _{i + 1}).

---

Bạn có thể chứng minh tối ưu là đúng bằng cách giả sử ngược lại, và mở rộng ảnh hưởng.

Giả sử rằng đường dẫn được cung cấp bởi A * là không phải là tối ưu với một heuristic được chấp nhận và đơn điệu, và suy nghĩ về điều đó có nghĩa là gì (bạn sẽ sớm thấy mình gặp mâu thuẫn), và do đó, giả định ban đầu được giảm xuống vô lý.

Từ đó bạn có thể kết luận rằng giả định ban đầu của bạn là sai, tức là, A * là tối ưu với các điều kiện trên. Q.

Answer 2

Hãy xem bước cuối cùng, bước hoàn thành đường dẫn tối ưu.

Tại sao phải A * chọn đường dẫn đó? Hoặc, đặt một cách khác, tại sao phải A * tránh chọn một con đường phụ tối ưu để đạt được mục tiêu?

Gợi ý: đây là lý do heuristic cần phải được chấp nhận . Lưu ý rằng nó là ok để chọn một con đường tối ưu phụ, miễn là nó không hoàn thành đường dẫn (tại sao?).

Điều đó sẽ cung cấp cho bạn một số ý tưởng về cách thức thời trang bằng chứng.