[Sudet]

Mirkówny i Mirki z #sudetprogramuje i #programowanie. Może też #gamedev będzie zainteresowany ( ͡° ͜ʖ ͡°).

Po wczorajszych sortowaniach naszła mnie chęć na porównanie algorytmów przeszukiwania grafów A* i Dijkstra. Zapraszam do oglądania i komentowania LINK DO PORÓWNANIA.

Wystarczy na jednej z plansz wybrać dwa punkty (początkowy i końcowy), a obydwa algorytmy zaczną działać i znajdą optymalną ścieżkę między dwoma punktami. ( ͡º ͜ʖ͡º)

Oczywiście zapraszam do śledzenia tagu #sudetprogramuje jeżeli chcecie więcej :D.

Pozdrawiam i życzę miłego dnia.

[p.....o]

@Sudet: lux, co tu sie rozpisywać :D

[Sudet]

@psemcio: dziękuję. A może jakieś propozycje na kolejne algo?

[KorelacjaProkrastynacji]

@Sudet: Korzystasz z tablic dwuwymiarowych? Polecam grafy i algoytmy pokroju komiwojażera :x

[Sudet]

@KorelacjaProkrastynacji:

Korzystasz z tablic dwuwymiarowych?

Tak bo inaczej nie wyobrażam sobie rysowania siatki izometrycznej :), a poza tym tak dużo łatwiej jest prezentować wszystko :).

Polecam grafy i algoytmy pokroju komiwojażera

No to te dwa algorytmy to podstawowe algorytmy grafowe ( ͡º ͜ʖ͡º), a problem komiwojażera nie jest algorytmem, tylko problemem w matematyce ( ͡º ͜ʖ͡º).

[KorelacjaProkrastynacji]

@Sudet: Jednakże można to przełożyć na algorytmy :D W ogóle teraz mi uświadomiłeś że to grafy. Sporo rzeczy po studiach zapomniałem już :C

[Sudet]

@KorelacjaProkrastynacji: Pisałem prace Inżynierską z przybliżania optymalnego rozwiązania w problemie komiwojażera i nie wyobrażam sobie jak to przełożyć na algorytm ;). Jedyne co mi wpada do głowy to heurystyki typu algorytm mrówkowy (ant algorithm), albo algorytm genetyczny. Jednak w dalszym ciągu to nie są algorytmy a tylko heurystyki, bo nie dają przewidywalnego (optymalnego) wyniku i nie da się określić ich złożoności.

[asunez]

@Sudet: Bazując na Twojej symulacji ciężko mi znaleźć przypadek, w którym Dijkstra byłby skuteczniejszy od A* - czy to tak może być, czy istnieją sytuacje, w których jednak Dijkstra "wygrywa"?

[Sudet]

@asunez: Nie istnieją :). Przynajmniej nie powinny istnieć. A* jest specjalnym przypadkiem Dijkstry, w którym wybieramy następny ruch na podstawie heurystyki, która określa odległość od celu. A Dijkstra nie używając takiej heurystyki można powiedzieć że porusza się w ciemno i musi sprawdzić dużo więcej możliwości.

[asunez]

@Sudet: Ok, dzięki za wyjaśnienie - niby cośtam o tych grafach miałem, ale jak widać nic w głowie nie zostało :p A za same symulacje propsy, więcej takich ( ͡° ͜ʖ ͡°)

[Sudet]

@asunez: A* nie jest zazwyczaj uczony na studiach w Polsce (a szkoda, bo to powszechnie używany algorytm na przykład w grach), także nie ma się czego wstydzić :D.

[ZajebistyMamSzaliczek]

@asunez: @Sudet: Chcialbym zauwazyc, ze Dijkstra mimo tego, ze wymaga przeszukania wszystkich wierzcholkow w grafie to zwraca optymalne rozwiazanie. Algorytm A* nie wymaga przeszukania wszystkich wierzcholkow ale tez nie gwarantuje optymalnego rozwiazania.

[Sudet]

@ZajebistyMamSzaliczek: Plus dla Ciebie mirku. Masz rację ;), aczkolwiek Dijkstra nie wymaga przeglądania wszystkich możliwych wierzchołków w celu znalezienia ścieżki ;).

[ZajebistyMamSzaliczek]

@ZajebistyMamSzaliczek:
To tak odnosnie hipotezy, ze nie powinny istniec sytuacje w ktorych Dijkstra wygrywa. Na pewno istnieja.

[ZajebistyMamSzaliczek]

@Sudet: Nie zgadzam sie z tym, ze nie wymaga przegladania wszystkich wierzcholkow.

2. Utwórz kolejkę priorytetową Q wszystkich wierzchołków grafu. Priorytetem kolejki jest aktualnie wyliczona odległość od wierzchołka źródłowego s.

3. Dopóki kolejka nie jest pusta:

(..)

[Sudet]

@ZajebistyMamSzaliczek: Ten fragment który zacytowałeś wcale nie wskazuje na odwiedzenie wszystkich wierzchołków do znalezienia ścieżki. Na mojej prezentacji algorytmów wszystkie odwiedzone wierzchołki są pokolorowane (gradient czerwono/zielony). Łatwo zauważyć, że nie wszystkie wierzchołki są odwiedzane.

Przy grafie w którym każda krawędź ma taką samą wagę Dijkstra nie ma prawa wygrać ;).

[voidvoid]

@ZajebistyMamSzaliczek: Algorytm Dijkstry znajduje odległości od źródła do wszystkich pozostałych wierzchołków w grafie. Tutaj mamy zaprezentowany zmodyfikowaną wersję, która kończy działanie w momencie dojścia do wierzchołka docelowego, tak więc nie potrzeba przeszukiwać ich wszystkich.

[ZajebistyMamSzaliczek]

@voidvoid: No wiec mowimy o zmodyfikowanym algorytmie Dijkstry ; )

@Sudet: Ok, zatem wklejam calosc.

Dijkstra(G,w,s):

dla każdego wierzchołka v w V[G] wykonaj

d[v] := nieskończoność

poprzednik[v] := niezdefiniowane

d[s] := 0

Q := V

dopóki Q niepuste wykonaj

u := Zdejmij_Min(Q)

dla każdego wierzchołka v – sąsiada u wykonaj

jeżeli d[v] > d[u] + w(u, v) to

d[v] := d[u] + w(u, v)

poprzednik[v] := u

Dodaj(Q, v)

+

[Sudet]

@ZajebistyMamSzaliczek: you got me :D. Zwracam honor. (chociaż dalej upieram się, że pod względem szybkości A* zawsze wygra :D )

Tak nawiasem mówiąc to nie jest zmodyfikowana wersja ;). Dijkstra jest algorytmem przeszukiwania grafu i szukanie najkrótszej ścieżki jest przykładem przeszukiwania grafu. Nie ma sensu przeszukiwać dalej kiedy zaleźliśmy już rozwiązanie ;). To tylko kwestia interpretacji algorytmu.

[ZajebistyMamSzaliczek]

@Sudet: Nie powiedzialbym ze to kwestia interpretacji. Jesli dobrze rozumiem, poprostu dodajesz sobie taki warunek, ze jesli znalazles juz sciezke o dlugosci N, to ustalasz limit przeszukiwania N, powyzej ktorego nie ma sensu juz szukac sciezki (bo kazda nastepna bedzie gorsza od jednej juz znalezionej). W klasycznym algorytmie nie masz takiego zalozenia i nie moze go byc jesli dopuszczamy krawedzie o wadze ujemnej. W tym wypadku akurat kazda krawedz ma wage

[Sudet]

Wiem, czepiam sie ; ). Ale jesli chodzi o nauki scisle to lubie jak wszystko faktycznie jest scisle. Zwlaszcza jesli chodzi o hipotezy "na pewno X, bo u mnie za kazdym razem bylo X" ( ͡° ͜ʖ ͡°)

@ZajebistyMamSzaliczek: Dziękuję Ci, za to, że się czepiasz ;), dzięki takiemu podejściu ja też się uczę. Jasne to co napisałeś o algorytmie to rzeczywiście klasyczny Dijkstra powinien zbudować statyczną