Tôi có khả năng tính toán tuyến đường tốt nhất giữa điểm xuất phát và điểm đến bằng A *. Ngay bây giờ, tôi bao gồm các điểm giữa điểm bắt đầu và điểm kết thúc của mình bằng cách áp dụng A * cho các cặp trong tất cả các hoán vị của các điểm của tôi.Thêm điểm tham chiếu vào A * tìm kiếm đồ thị
Ví dụ:
Tôi muốn đi từ điểm 1 đến điểm 4. Ngoài ra, tôi muốn đi qua điểm 2 và 3.
tôi tính toán hoán vị của (1, 2, 3, 4):
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
sau đó, đối với mỗi hoán vị, tôi tính toán A * đường từ người đầu tiên thứ hai, sau đó thêm nó vào con đường từ thứ hai đến thứ ba, sau đó thứ ba đến thứ tư.
Khi tôi tính toán này cho mỗi hoán vị, tôi sắp xếp các tuyến đường theo khoảng cách và trả về giá trị ngắn nhất.
Rõ ràng, hoạt động này, nhưng bao gồm rất nhiều tính và hoàn toàn sụp đổ khi tôi có 6 waypoints (hoán vị của 8 mặt hàng là 40.320 :-))
Có cách nào tốt hơn để làm điều này?
Tại sao bạn bao gồm các đường dẫn không bắt đầu ở 1 và kết thúc ở mức 4? Và, nếu bạn có lý do chính đáng để làm như vậy, nếu địa hình của bạn là một trong những hướng đi về phía trước, một hướng có cùng chi phí khi đi ngược, bạn không phải tính toán đường dẫn ngược (1234 và 4321) –
Bạn chỉ cần để hoán đổi các điểm bạn phải vượt qua. Trong trường hợp của bạn, bạn chỉ cần thử '1 -> 2 -> 3 -> 4' và' 1 -> 3 -> 2 -> 4'. – IVlad