Ağırlıklı bir şekilde yönlendirilmiş bir grafiğe sahip olduğumuzu varsayalım ve A * araması veya herhangi bir başka en kısa yol algoritması kullanarak G'deki u ve v arasındaki köşeler arasındaki en kısa yolu bulduk. Şimdi tüm kenar ağırlıklarını G'de iki katına çıkardığımızı varsayalım. En kısa yol değişiyor mu?Kenar ağırlıkları iki katına çıkarıldıktan sonra en kısa yol
Benim bağımsız değişkenim şu şekildedir: en kısa yol , değiştirmiyor. özgün yolu P ara ve iki katına sonra sonra P. daha kısa olan
weight(P') < weight(P)
'v kenarlarının ağırlıkları katlama sonrası, P böyle için u', ikinci, farklı bir yol P var olduğunu varsayalım . Bununla birlikte, her iki tarafı da 2'ye bölerek, P 'nin iki katına çıkmadan önce daha kısa olduğunu görürüz, bu yüzden P en kısa yol değildi ve bir çelişki var. Böylece, P kenar ağırlıklarını ikiye katladıktan sonra en kısa yol kalır.
Birisi bu çözümü eleştirebilir mi? Doğru mu?
Biraz abartılı olabileceğini düşünüyorum ... Her bir kenar ağırlığını pozitif bir sabit faktörle çarpmak en kısa yolu değiştirmeyecektir - doğrudur (çünkü çarpma, ekleme üzerine dağıtılır). Ancak, aynı zamanda bir "doğrusal dönüşüm" olan her yol kenarına 1 eklenmesi, daha az segmente sahip olanlardan daha fazla segmente sahip olan bu yolları cezalandıracaktır, bu da genellikle farklı bir en kısa yol olduğu anlamına gelecektir ... – twalberg
@ twalberg Her bir ağırlığa 1 eklenmesi daha doğru olarak "affine" olarak tanımlanır, ancak burada yazılanların istenen bir şey bıraktığını kabul ediyorum. –
@DavidEisenstat Hmmm ... Evet, sanırım haklısın ... birkaç yıl geçti ... ... en son lineer cebir kavramlarında ... ... son derece iyi bildiğimden, kelime bilgisi biraz düştü. Ama eğer bu ayrım doğrusal ve yüksek dereceli polinomlar, üsteller, transandantaller ve "doğrusal" şemsiyenin altındaki affine dönüşümleri göz önüne alındığında, çok uzak değil. – twalberg