Załóżmy, że mamy wyważony wykres G i znaleźliśmy najkrótszą ścieżkę między wierzchołkami u i v w G, używając algorytmu A * lub innego algorytmu o najkrótszej ścieżce. Teraz przypuśćmy, że podwoimy wszystkie grubości krawędzi w G. Czy zmieni się najkrótsza ścieżka?Najkrótsza ścieżka po podwojeniu grubości krawędzi
Mój argument jest następujący: najkrótsza ścieżka nie zmienia się. Nazwać oryginalnej ścieżki P i załóżmy, że istnieje drugi, inny od ścieżki P „U V, tak że po podwojenie grubości krawędzi P” jest krótsze niż P. Następnie,
weight(P') < weight(P)
po podwojeniu . Jednak dzieląc obie strony przez 2 widzimy, że P 'również musiało być krótsze przed podwojeniem, więc P nie była najkrótszą drogą do rozpoczęcia i mamy sprzeczność. Zatem P pozostaje najkrótszą ścieżką po podwojeniu obciążeń krawędzi.
Czy ktoś mógłby skrytykować to rozwiązanie? Czy to jest poprawne?
Myślę, że może to być nieco zawyżone ... Pomnożenie każdej krawędzi wagi przez dodatni stały współczynnik nie zmieni najkrótszej ścieżki - to jest poprawne (ponieważ mnożenie rozkłada się nad dodaniem). Jednak dodanie 1 do każdej krawędzi ścieżki, która jest również "transformacją liniową", spowoduje karanie tych ścieżek z większą liczbą segmentów w większym stopniu niż te z mniejszą liczbą segmentów, co często oznacza, że istnieje inna najkrótsza ścieżka ... – twalberg
@ twalberg Dodanie 1 do każdego ciężaru jest bardziej poprawnie opisane jako "afiniczne", ale zgadzam się, że sformułowanie tutaj pozostawia wiele do życzenia. –
@DavidEisenstat Hmmm ... Tak, wierzę, że masz rację ... minęło kilka ... lat ... odkąd ostatni raz byłem w pełni zorientowany w koncepcji algebry liniowej, więc słownictwo trochę się poślizgnęło. Ale jeśli rozróżnienie jest pomiędzy wielomianami liniowymi a wyższymi, wykładniczymi, transcendentalnymi itd., To rozważanie przekształceń afinicznych pod parasolem "liniowym" nie jest zbyt odległe ... – twalberg