Thuật toán Dijkstra với Chebyshev Khoảng cách

Question

Tôi đã sử dụng Thuật toán Dijkstra để tìm đường đi ngắn nhất trong API Đồ thị được đưa ra bởi Thuật toán Đại học Princeton Phần 2, và tôi đã tìm ra cách tìm đường với Chebyshev Distance.

Mặc dù Chebyshev có thể di chuyển sang bất kỳ bên nào của nút với chi phí chỉ 1, không ảnh hưởng đến Tổng chi phí, nhưng theo biểu đồ, vòng tròn màu đỏ, tại sao đường tìm kiếm di chuyển ngoằn ngoèo di chuyển thẳng?

Điều tương tự sẽ lặp lại nếu tôi sử dụng thuật toán A *?

Answer 1

Nếu bạn muốn ưu tiên "đường thẳng" bạn nên tham gia sự chỉ đạo của bước trước vào tài khoản. Một cách có thể là tạo một biểu đồ G'(V', E') trong đó V' bao gồm tất cả các cặp hàng xóm của đỉnh. Ví dụ, đỉnh v = (v_prev, v_cur) sẽ xác định một đỉnh trong đường dẫn trong đó v_cur là đỉnh cuối cùng của đường dẫn và v_prev là đỉnh trước đó. Sau đó, trên bước "cập nhật khoảng cách" của thuật toán đường đi ngắn nhất, bạn có thể chọn khoảng cách tốt nhất với hướng tốt nhất (không thay đổi).

Ngoài ra, chúng tôi có thể thêm thuộc tính bổ sung vào khoảng cách bằng với số lượng thay đổi hướng và tìm khoảng cách tối thiểu với số lượng thay đổi hướng tối thiểu.

Answer 2

Không nên nói thẳng, theo Dijkstra hoặc A *, như bạn nói nó không ảnh hưởng đến tổng chi phí. Tôi sẽ giả sử, bằng cách này, rằng bạn muốn ngăn chặn vô dụng zig-zagging nói riêng, và không có sở thích đặc biệt nói chung cho một động thái mà đi theo cùng một hướng như di chuyển trước đó.

Dijkstra và A * không có tính năng không thích hợp cho "đường dẫn kỳ lạ", chúng chỉ quan tâm một cách rõ ràng về chi phí, có nghĩa là chúng cũng quan tâm đến cách bạn xử lý chi phí bằng nhau. Có một vài điều bạn có thể làm về điều đó:

1. Sử dụng liên kết để làm cho chúng thích di chuyển thẳng bất cứ khi nào hai nút có chi phí bằng nhau (G hoặc F, tùy thuộc vào việc bạn đang làm Dijkstra hay A *). Điều này cho phép một số rắc rối xung quanh chướng ngại vật vì hai lựa chọn cuối cùng dẫn đến đường dẫn bằng nhau không nhất thiết phải có cùng điểm F, vì vậy chúng có thể không bị ràng buộc. Nó sẽ không bao giờ cung cấp cho bạn một con đường phụ tối ưu mặc dù.
2. Hơi tăng chi phí đường chéo của bạn, nó không phải là một toàn bộ rất nhiều, nói 10 cho thẳng và 11 cho đường chéo. Điều này sẽ chỉ tránh bất kỳ di chuyển đường chéo nào không phải là lối tắt. Nhưng rõ ràng: nếu điều đó không khớp với chi phí thực tế, giờ đây bạn có thể tìm thấy đường dẫn phụ tối ưu. Sự khác biệt chi phí càng lớn, càng có nhiều điều sẽ xảy ra. Trong thực tế nó tương đối hiếm, và con đường phải đủ dài (tích lũy đủ chi phí-sự khác biệt mà nó trở thành giá trị một di chuyển toàn bộ thêm) trước khi nó xảy ra.