Algorytm Bellmana-Forda

03.10.2010 - Damian Rusak
TrudnośćTrudność

Znajdowanie najkrótszej ścieżki w grafie ma wiele wariantów. Przyjrzyjmy się takiemu: statek kosmiczny podróżuje między galaktykami - niektóre podróże są kosztowne czasowo - wehikuł po prostu leci przez przestrzeń kosmiczną. Ale ma też czasem możliwość skorzystać z tuneli czasoprzestrzennych - nie dość, że zmienia położenie, to jeszcze cofa się w czasie. Jak wtedy znaleźć najszybszą drogę z jednej galaktyki do drugiej?

Wprowadzenie

Spójrzmy na ilustracje poniżej. Połączenia między galaktykami możemy symbolizować za pomocą grafu. Te, które wymagają dodatniego „nakładu czasu” są oznaczone liczbą dodatnią, tunele czasoprzestrzenne liczbą ujemną. Jak odnaleźć zatem najkrótszą drogę między startem i metą statku?

Spróbuj znaleźć najtańszą ścieżkę - jej koszt to 2. Należy przebyć kolejno krawędzie etykietowane przez 10, -9, 5, -4. 

Pierwsze obserwacje

Czy pamiętasz algorytm Dijkstry? Jeśli nie, zapraszam do zapoznania się z tym artykułem. Możemy szybko zauważyć, że podejście Dijkstry - docierać tam, gdzie obecnie można dostać się najmniejszym kosztem - jest nieskuteczne w tym przypadku. "Zachłanne" przejście najtańszymi krawędziami - za 2 a potem za 1 - doprowadziłoby nas do celu łącznie za 3. Tymczasem rozpoczęcie od niepozornej i odstraszającej krawędzi o koszcie 10 prowadzi do lepszego rozwiązania!

Więc - nie można zastosować tutaj Algorytmu Dijkstry i rozwiązania zachłanne (przynajmniej na pierwszy rzut oka) nie są dobrym pomysłem!

Okazuje się, że czasem warto ponieść większy koszt na początku podróży, aby później "odrobić" zaległości korzystając z krawędzi o ujemnych kosztach. Skorzystamy z tej obserwacji później.

Spójrz na poniższą ilustrację - niektóre wagi zostały zmienione, dodano też jedną krawędź. Czy można znaleźć tu najkrótszą ścieżkę? Jaki problem pojawia się w tej sytuacji? 

Na animacji obok można zauważyć rozwiązanie tej zagadki! Można osiągnąć dowolnie niski koszt podróży - jeżeli tylko wykorzysta się któryś z ujemnych cykli. Będziemy tak nazywać cykl, który ma w sumie ujemny koszt. Można uzyskać więc równie dobrze koszt $ -10^{9} $ jak i $ -10^{1000} $, nie da się ustalić najmniejszej możliwości.

Więc - Trzeba uważać na cykle ujemne - jeśli można znaleźć ścieżkę, która prowadzi od startu do celu przez ujemny cykl, należy to wykryć!


5
Twoja ocena: Brak Ocena: 5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com