A * Jump Point Search - cách cắt tỉa thực sự hoạt động như thế nào?

Question

Tôi đã xem qua số Jump Point Search và có vẻ như rất ngọt đối với tôi. Tuy nhiên, tôi không chắc chắn về cách thức quy tắc tỉa cành của họ thực sự hiệu quả. Cụ thể hơn, trong hình 1, nó nói rằng

chúng tôi ngay lập tức có thể prune tất cả các nước láng giềng xám như những có thể đạt được một cách tối ưu từ cha mẹ của x mà không bao giờ đi qua nút x

Tuy nhiên, điều này dường như phần nào ở tỷ lệ cược. Trong hình ảnh thứ hai, nút 5 có thể đạt được bằng cách đầu tiên đi qua nút 7 và bỏ qua x hoàn toàn thông qua một đường đối xứng - nghĩa là, 6 -> x -> 5 dường như đối xứng với 6 -> 7 -> 5. Điều này sẽ giống như cách mà nút 3 có thể đạt được mà không phải qua x trong hình ảnh đầu tiên. Như vậy, tôi không hiểu làm thế nào hai hình ảnh này không hoàn toàn tương đương, và không chỉ xoay các phiên bản của nhau.

Thứ hai, tôi muốn hiểu cách thuật toán này có thể được tổng quát hóa thành khối lượng tìm kiếm ba chiều.

Answer 1

Tôi hiểu điều này là về các ưu tiên. Để liệt kê từng đường không đối xứng, bạn phải liệt kê tất cả các nút - nhưng nó thực sự không quan trọng bạn chọn đường nào, bởi vì chúng đối xứng. Vì vậy, các tác giả đã quyết định đi với đường chéo đầu tiên - đó là, bất kỳ chuyển động đường chéo nào cũng luôn xuất hiện trước bất kỳ chuyển động thẳng nào trong một đường đi. Đó là lý do tại sao thẳng có nhiều nút bị cắt tỉa - bởi vì nó phải xảy ra sau khi tất cả các đường chéo đã được tính toán.

Answer 2

Hình ảnh thứ hai được hiển thị không chính xác. Nếu bạn lướt qua văn bản đi kèm: "Trong cả hai trường hợp, chúng tôi có thể ngay lập tức cắt tỉa tất cả các hàng xóm màu xám vì chúng có thể đạt được tối ưu từ cha mẹ của x mà không bao giờ đi qua nút x".

Nhấn mạnh vào 'cả hai trường hợp'.

Về mặt áp dụng khái niệm cho không gian 3 chiều (hoặc heck, thậm chí là không gian n chiều), thuật toán này không khác với A * ở chỗ nó đơn giản là một mạng lưới các nút và kết nối. Chiều hướng hoàn toàn tùy theo quyết định của bạn.

Answer 3

Vâng, JPS là ngọt ngào nhưng giới hạn bản đồ với các ràng buộc cụ thể: đồ

1. phải đại diện cho một mạng lưới.
2. Tất cả các ô có thể truy cập trong lưới phải có cùng chi phí truyền tải.
3. Tác nhân di chuyển phải có 8 hướng di chuyển có thể có: 4 hướng chính và 4 đường chéo.

Chìa khóa để các thuật toán là những trở ngại cho phép một số giả định quan trọng:

1. Các tuyến đường hình học ngắn nhất giữa hai điểm (trong trường hợp không vật cản) cũng là con đường một chi phí thấp nhất.
2. Đường dẫn ít tốn kém nhất giữa hai điểm (không có vật cản) không cần nhiều hơn một hướng thay đổi.

Những giả định cho phép các thuật toán để bỏ qua tùy chọn con đường đối xứng và hoạt động như sau:

1. Khi đi du lịch trong một hướng chính bạn chỉ cần phải xem xét một sự thay đổi về phương hướng khi một chướng ngại vật gặp phải trong một trong những các vị trí được minh họa trong các giấy tờ. Những điểm mà thay đổi hướng được xem là "Điểm nhảy".
2. Khi di chuyển theo đường chéo, bạn chỉ cần xem xét thay đổi hướng khi một điểm nhảy có thể được "nhìn thấy" theo một trong hai hướng chính "hướng về phía trước", một lần nữa như minh họa trong các giấy tờ.