Giả sử chúng ta có đồ thị có chỉ số trọng số G và chúng tôi đã tìm thấy đường đi ngắn nhất giữa các đỉnh u và v trong G bằng cách sử dụng tìm kiếm A * hoặc bất kỳ thuật toán đường đi ngắn nhất nào khác. Bây giờ giả sử rằng chúng ta tăng gấp đôi tất cả các trọng số cạnh trong G. Con đường ngắn nhất có thay đổi không?Đường ngắn nhất sau trọng số cạnh gấp đôi
Đối số của tôi như sau: đường đi ngắn nhất không thay đổi. Gọi con đường P gốc và giả sử rằng có tồn tại một thứ hai, khác với con đường P 'từ u đến v sao cho sau khi tăng gấp đôi trọng lượng của các cạnh, P' là ngắn hơn so với P. Sau đó,
weight(P') < weight(P)
sau khi tăng gấp đôi . Tuy nhiên, chia cả hai bên cho 2 chúng ta thấy rằng P 'cũng phải ngắn hơn trước khi tăng gấp đôi, vì vậy P không phải là con đường ngắn nhất để bắt đầu và chúng ta có mâu thuẫn. Vì vậy, P vẫn là con đường ngắn nhất sau khi tăng gấp đôi trọng lượng cạnh.
Ai đó có thể phê bình giải pháp này? Nó có đúng không?
Tôi nghĩ rằng có thể hơi phóng đại ... Nhân mỗi trọng số cạnh bởi một yếu tố không đổi tích cực sẽ không thay đổi đường đi ngắn nhất - đó là chính xác (vì phép nhân phân phối trên bổ sung). Tuy nhiên, thêm 1 vào mọi cạnh đường dẫn, cũng là "chuyển đổi tuyến tính", sẽ phạt những đường dẫn có nhiều phân đoạn đến mức lớn hơn các đoạn có ít phân đoạn hơn, thường có nghĩa là có một con đường ngắn nhất khác ... – twalberg
@ twalberg Thêm 1 cho mỗi trọng lượng được mô tả chính xác hơn là "affine", nhưng tôi đồng ý rằng từ ngữ ở đây để lại thứ gì đó mong muốn. –
@DavidEisenstat Hmmm ... Vâng, tôi tin rằng bạn đã đúng ... nó đã được một vài .... năm ... kể từ khi tôi cuối cùng hoàn toàn thông thạo các khái niệm đại số tuyến tính, vì vậy từ vựng đã trượt một chút. Nhưng nếu sự khác biệt giữa các đa thức tuyến tính so với bậc cao hơn, hàm mũ, siêu việt và như vậy, xem xét biến đổi affine dưới cái ô của "tuyến tính" không phải là quá xa ... – twalberg