Tại sao hầu hết các thuật toán đồ thị không thích ứng dễ dàng với số âm?

Question

Các Algorithm Design Manual nói:

Hầu hết các thuật toán đồ thị không thích ứng quá dễ dàng để số âm. Thật vậy, các thuật toán đường dẫn ngắn nhất gặp rắc rối với các số âm, và chắc chắn không tạo ra đường dẫn dài nhất có thể bằng cách sử dụng kỹ thuật này.

Nhưng tại sao? Khi chúng tôi chỉ thêm một âm - trước trọng lượng ban đầu, tôi nghĩ hầu hết các vấn đề về đồ thị liên quan đến cân nặng đều có thể được xử lý như nhau, đúng không?

Answer 1

Bởi vì khi bạn đang xem xét chi phí tối thiểu hoặc tối đa của đường dẫn, bạn luôn xem xét tổng của tất cả các bước.

Và vì nhiều thuật toán này hoạt động cục bộ bằng cách chọn phương pháp tiếp cận tốt nhất từng bước (với bước độ lớn khác nhau), có trọng số âm sẽ tạo chu kỳ hoặc dương tính giả. Có một trọng số tiêu cực ngụ ý rằng chi phí của một con đường có thể giảm trong tương lai, đó là lý do tại sao nó tạo ra vấn đề: bạn không thể loại trừ đường dẫn khỏi danh sách đường dẫn tiềm năng ngay cả sau khi đạt đến một điểm bây giờ là đắt hơn khác vì bạn có thể tìm thấy các cạnh với trọng lượng tiêu cực mà thay đổi tình hình. Cũng giống như ví dụ: nếu bạn có hai nút được kết nối với nhau bằng hai cạnh trọng số 1 và -2, bạn có thể tạo chu trình giữa chúng để xác định đường đi với chi phí thấp tùy ý (thậm chí -∞).

Answer 2

Thật vậy, thuật toán tìm đường ngắn nhất gặp rắc rối với số âm,

Điều này đúng cho Dijkstra's Algorithm, nhưng không phải cho thuật toán tìm đường ngắn nhất nói chung. Các Bellman-Ford Algorithm có thể đối phó với trọng số cạnh tiêu cực, miễn là biểu đồ không chứa các chu kỳ âm. Tuy nhiên:

Bellman-Ford có thể phát hiện chu kỳ tiêu cực và báo cáo sự tồn tại của họ, nhưng nó không thể tạo ra một câu trả lời đúng nếu một chu kỳ tiêu cực là không ợc từ các nguồn.

Answer 3

Tôi sẽ thêm câu trả lời cho vấn đề đường đi ngắn nhất một cách cụ thể. Vấn đề chung với các cạnh tiêu cực được mô tả tốt trong Jack’s answer.

Xem xét biểu đồ G = (V, E) với các cạnh có chiều dài l(e) ≤ 0 cho mỗi cạnh e ∈ E. Con đường ngắn nhất trong G giống với đường dẫn dài nhất trong G' với l'(e) = - l(e) ≥ 0 ∀e ∈ E. Longest path problem được biết là NP-hard trong đồ thị chung. Mặc dù nó có thể được giải quyết trong thời gian tuyến tính trong DAG và các lớp biểu đồ khác.

Là cls answered, sự cố chỉ xảy ra với các chu kỳ âm và Bellman-Ford algorithm có thể đối phó với một số cạnh là âm. Nhưng thuật toán đường dẫn dài nhất phải đối phó với các chu kỳ trong biểu đồ và Bellman-Ford không thể đưa ra câu trả lời đúng trên các đồ thị có chu kỳ âm. Do đó thuật toán Bellman-Ford có thể được sử dụng để tính toán đường đi dài nhất chỉ trong biểu đồ không có chu kỳ tích cực. Đề cập, vì ý tưởng đó là obviously not uncommon.