Tôi cần tìm một đường đi ngắn nhất thông qua một đồ thị vô hướng có các nút là trọng số thực (dương và âm). Các trọng số này giống như các tài nguyên mà bạn có thể đạt được hoặc mất đi bằng cách nhập nút.Thuật toán/giải pháp đơn giản nhất cho một cặp đường đi ngắn nhất thông qua biểu đồ không có trọng số thực là gì?
Tổng chi phí (tổng tài nguyên) của đường dẫn không phải là rất quan trọng, nhưng nó phải lớn hơn 0 và độ dài phải là ngắn nhất có thể.
Ví dụ xem xét một đồ thị như sau:
A-start node; D-end node
A(+10)--B(0)--C(-5)
\ | /
\ |/
D(-5)--E(-5)--F(+10)
Con đường ngắn nhất sẽ là A-E-F-E-D
thuật toán Dijkstra một mình không làm như lừa, bởi vì nó không thể xử lý các giá trị âm. Vì vậy, tôi nghĩ về một vài giải pháp:
Đầu tiên sử dụng thuật toán Dijkstra để tính toán chiều dài của một đường đi ngắn nhất từ mỗi nút đến nút thoát, không cân nhắc trọng số. Điều này có thể được sử dụng như một số loại giá trị chẩn đoán như trong A *. Tôi không chắc chắn nếu giải pháp này có thể làm việc, và cũng rất tốn kém. Tôi cũng nghĩ về việc thực hiện thuật toán Floyd – Warshall, nhưng tôi không chắc chắn làm thế nào.
Một giải pháp khác là tính toán đường đi ngắn nhất với thuật toán Dijkstra không xem xét trọng số và sau khi tính toán tổng tài nguyên của đường dẫn nhỏ hơn 0, đi qua từng nút để tìm nút lân cận có thể tăng nhanh tổng tài nguyên, và thêm nó vào đường dẫn (nhiều lần nếu cần). Giải pháp này sẽ không hoạt động nếu có một nút có thể đủ để tăng tổng tài nguyên, nhưng xa hơn con đường ngắn nhất được tính toán.
Ví dụ:
A- start node; E- end node
A(+10)--B(-5)--C(+40)
\
D(-5)--E(-5)
Bạn có thể giúp tôi giải quyết vấn đề này?
EDIT: Nếu khi tính đường đi ngắn nhất, bạn đạt đến điểm tổng số tài nguyên bằng 0, đường dẫn đó không hợp lệ vì bạn không thể tiếp tục nếu không còn xăng nữa.
Trong ví dụ này, A-E-A-E-D có phải là giải pháp hợp lệ không? – mbeckish
Có giá trị. – foobars
Thoạt nhìn, có vẻ như có 2 cách để tăng tổng tài nguyên - 1) đi chệch khỏi đường đi ngắn nhất để tìm nút nguồn cao gần đó và 2) dao động giữa hai nút trên đường đi ngắn nhất với tổng tăng tài nguyên ròng. Sau đó, các trick là để tìm ra một heuristic để xác định tùy chọn để lựa chọn. – mbeckish