Khoảng cách Manhattan có thể được thừa nhận như thế nào?

Question

Không đúng khi đếm số lần di chuyển cho 1 ô có thể dẫn đến các ô xếp khác đến trạng thái mục tiêu của chúng? Và do đó đếm cho mỗi gạch có thể cung cấp cho chúng tôi một số nhiều hơn các động thái tối thiểu cần thiết để đạt được trạng thái mục tiêu?

Câu hỏi này nằm trong bối cảnh khoảng cách Manhattan cho 15 câu đố.

Đây là câu hỏi hay nói cách khác nhau:

Chúng ta có thể sử dụng Manhattan khoảng cách như một heuristic, chấp nhận cho N-Puzzle. Để thực hiện tìm kiếm A *, chúng ta cần một heuristic chấp nhận được. Liệu Manhattan có phải là một ứng cử viên? Nếu có, làm thế nào để bạn chống lại các đối số trên (3 câu đầu tiên trong câu hỏi)?

Định nghĩa: A* là một loại thuật toán tìm kiếm. Nó sử dụng một chức năng heuristic để xác định khoảng cách ước tính đến mục tiêu. Miễn là chức năng heuristic này không bao giờ đánh giá quá cao khoảng cách đến mục tiêu, thuật toán sẽ tìm ra con đường ngắn nhất, có lẽ nhanh hơn tìm kiếm rộng đầu tiên. Một phỏng đoán thỏa mãn điều kiện đó là được chấp nhận.

Answer 1

phỏng đoán có thể chấp nhận được không được đánh giá quá cao số lần di chuyển để giải quyết vấn đề này. Vì bạn chỉ có thể di chuyển các khối 1 tại một thời điểm và chỉ theo một trong 4 hướng, kịch bản tối ưu cho mỗi khối là nó có đường dẫn rõ ràng, không bị cản trở đến trạng thái mục tiêu của nó. Đây là một bằng chứng của 1.

Phần còn lại của các trạng thái cho một cặp khối là tối ưu phụ, có nghĩa là sẽ thực hiện nhiều bước hơn M.D để chặn đúng vị trí. Do đó, các heuristic không bao giờ quá ước tính và được chấp nhận.

Tôi sẽ xóa khi ai đó đăng phiên bản chính thức, chính xác này.

Answer 2

Bằng chứng chính thức: Theo định nghĩa của h, h (s ∗) = 0, nếu s ∗ là trạng thái mục tiêu. Giả sử chứng minh bằng mâu thuẫn rằng C ∗ < h (s0) đối với một số trạng thái ban đầu s0. Lưu ý rằng, vì mỗi hành động có thể di chuyển chỉ một ô, thực hiện một hành động có thể giảm nhiều nhất một lần. Vì mục tiêu có thể đạt được là trong các hành động C, chúng ta có h (s ∗) ≥ h (s0) - C ∗> 0, điều này đưa chúng ta đến một sự mâu thuẫn vì h (s ∗) phải bằng không. Vì vậy, chúng ta phải có h (s0) ≤ C ∗ forall s0, và h được chấp nhận. (Nguồn: Đại học California, Irvine)