[Dede18]

Cześć, czy mógłby ktoś podrzucić jakieś wskazówki dotyczące znalezienia najkrótszej drogi, z punktu A, do punktu B, ale pomiędzy wieloma punktami (jadąc z punktu A, do punktu B, musi dojechać również do innych punktów, lub prościej - odwiedzić określone punkty, najkrótszą drogą)? Czytałem na temat algorytmu Dijkstry, ale on nie rozwiązuje tego problemu.
Dziękuję.

#programowanie #naukaprogramowania #cpp

[Masterczulki]

@Dede18: http://www.wykop.pl/link/1837156/problem-komiwojazera/#comment-19521342 tu coś masz

[Dede18]

@adhoc: Ale to wtedy będzie rozwiązanie siłowe, które na większą skalę się nie sprawdzi.

[japer]

@Dede18: Algorytm Floyda-Warshalla?

[offensive_gk]

@Dede18: Cykl Eulera?

[ponton]

@Dede18: Nie da się tego (znaleźć najkrótszą trasę, żeby odwiedzić wszystkie punkty) zrobić na obecny stan wiedzy świata lepiej niż siłowo. To jest problem NP-zupełny.

[Dede18]

@ponton: Więc może wiesz na czym opierają się różne nawigacje, gdzie wybieramy punkt A, i B oraz pośrednie? Rozumiem że to nie jest najlepsza droga, ale w pewnym stopniu optymalna.

[ponton]

@Dede18: Tam się po prostu ustala kolejność tych punktów pośrednich i oblicza się najkrótszą odległość między kolejnymi parami. Np. jak ustawisz kolejność Warszawa -> Poznań -> Łódź -> Berlin, to najpierw pojedziesz do Poznania, potem cofniesz się do Łodzi, a z niej dopiero do Berlina, mimo że szybciej byłoby najpierw przez Łódź, a dopiero potem Poznań. Znalezienie tej optymalnej kolejności punktów pośrednich jest możliwe tylko brute forcem.

[leoha]

Więc może wiesz na czym opierają się różne nawigacje, gdzie wybieramy punkt A, i B oraz pośrednie? Rozumiem że to nie jest najlepsza droga, ale w pewnym stopniu optymalna

@Dede18: Po pierwsze nie ma czegoś takiego jak w pewnym stopniu optymalna, albo jest optymalna albo nie jest (optymalna == najlepsza). A nawigacje stosują przeróżne heurystyki żeby znaleźć drogę bliską optymalnej w rozsądnym czasie. Mnóstwo prac naukowych istnieje na temat stosowania heurystyk

[leoha]

Więc może wiesz na czym opierają się różne nawigacje, gdzie wybieramy punkt A, i B oraz pośrednie?

@Dede18: https://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks

[Dede18]

@leoha: Raczej się przyjrzę bliżej algorytmowi genetycznemu, żeby rozwiązać ten problem (Chyba że istnieją inne, a również stosunkowo proste algorytmy?). Dzięki!

[wnocy]

@Dede18: genetyczny sobie radzi, ale powyżej X punktów już jest nieopłacalny. Z tego co pamiętam. Ile będziesz miał tych punktów pośrednich?

[Dede18]

@wnocy: Różnie, chciałbym żeby sobie radził i z większymi ilościami - kilkaset?

[wnocy]

@Dede18: zerknę w moje wyniki, bo kiedyś się w to bawiłem, ale obawiam się, że może to być za dużo i lepiej skorzystać z heurystyk

[Dede18]

@wnocy: Im więcej będę miał punktów pośrednich, tym mniej bliską optymalnej drogę bym wymagał.

[wnocy]

@Dede18: mój różowy poleca symulowane wyżarzanie i jestem skłonny jej przyznać rację. Zaraz Ci powiem jak to w genetycznych mi wychodziło.

[wnocy]

@Dede18 : ok, ja badałem dla 21 miast i wykonywało się to dłuugo. W zależności od operatorów krzyżowania i dobranych innych parametrów (liczebność populacji, procent nowych potomków, itd) po ok 300 generacjach wynik już znacząco się nie poprawiał.
Czystych genetycznych więc nie polecam.

[Anlak]

@Dede18: możesz spróbować algorytmem mrówkowym, implementacja jest bardzo prosta.
Tu znajdziesz problemy na których możesz testować algorytm http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

[Dede18]

@wnocy: Wyżarzanie wygląda skomplikowanie...
@Anlak: Poczytam.

[Dede18]

@Anlak: @wnocy: Czy jestem w stanie jakąkolwiek metodą zejść do czasu kilku-kilkunastu minut przy kilkuset punktach? Oczywiście zakładam duży margines błędu wyniku końcowego, ale jak wspomniałem, to nie jest aż tak istotne przy dużej ilości.