14
W algorytmie najkrótszej ścieżki Dijkstry i innych, zbadanie krawędzi, aby zobaczyć, czy zapewnia ona lepszą ścieżkę do węzła, jest określane jako relaksujące. Dlaczego nazywa się relaks?Dlaczego nazywamy to "Relaks" krawędzią?
Czy możesz wyjaśnić, w jaki sposób krawędzie basenu mogą być postrzegane jako ograniczenia? –
Pomyśl o wierzchołku z wieloma krawędziami. Kiedy zaczynasz, wiesz, że rozwiązanie musi uwzględniać wagę od pierwszej krawędzi, drugiej krawędzi i tak dalej. W efekcie, dla krawędzi a, b, c, d oraz e, zaczynasz mówić "najkrótsza ścieżka musi zawierać a, b, c, d, e". Wtedy eliminujesz e, a teraz wiesz, że musi zawierać tylko "a, b, c, d". Każdy krok jest * relaksacją *, ponieważ na każdym etapie usuwasz stan, który narzuca aktualne rozwiązanie. –
Sądzę, że to nie jest "wejście w to", ale "odejście"? –