Problem komiwojażera
Czyli ciekawy problem matematyczny, z którym na co dzień borykają się np. największe firmy kurierskie.
P.....k z- #
- #
- #
- #
- #
- #
- 157
Czyli ciekawy problem matematyczny, z którym na co dzień borykają się np. największe firmy kurierskie.
P.....k z
Komentarze (157)
najnowsze
Swego czasu napisałem bibliotekę do jednego z open-source-owych systemów do optymalizacji kombinatorycznej, która służy do znajdywania "Cyklu Hamiltona", o najniższym koszcie, w grafie (bo do tego sprowadza się problem komiwojażera). Załączam link do biblioteki i przykładu z Polskimi miastami :)
http://eclipseclp.org/doc/bips/lib_public/cycle/index.html
Bo o prawdziwym życiu, nie z książki, nic nie wiedzą !
Dodam tylko, że nie jest to żadna droga szutrowa, tylko normalna asfalt po
Komentarz usunięty przez moderatora
http://pokazywarka.pl/lrx232/
Komentarz usunięty przez moderatora
Komentarz usunięty przez moderatora
@Dakkar:
Po pierwsze, skłamałam :P Nie był to D-Wave One tylko Orion, 16-qubitowy prototyp D-Wave One. Po drugie, wiem, na czym polega problem xd Wiem, że nie jest to problem nierozwiązany, tylko po prostu trudny i czasochłonny. Po trzecie, skłamałam również mówiąc, że rozwiązanie problemu zostało zaprezentowane xd Podczas prezentacji zostało wspomniane, że tego typu problemy będą mogły być w przyszłości szybko rozwiązywane przez komputery kwantowe. Nie zaprezentowano jednak
To jest zapewne najprostszy algorytm jaki do tej pory wymyślono do problemu komiwojażera.
Poza nim dosyć proste są algorytmy genetyczne, które w skrócie polegają na tym, że losowanych jest x ścieżek i później te ścieżki mieszają się ze sobą aż do momentu kiedy coraz trudniej jest znaleźć lepsze rozwiązanie.
http://pl.wikipedia.org/wiki/Algorytm_genetyczny
Dosyć dobrym sposobem na stopowanie takiego algorytmu jest używanie pochodnej:
http://pl.wikipedia.org/wiki/Pochodna
Pochodna - zapewne znana wielu osobom jako nieprzydatna rzecz uprzykrzająca
Algorytm Dijkstry nie rozwiązuje problemu komiwojażera. Służy on do wyliczenia najkrótszej drogi do danego wierzchołka, ale nie do wyznaczenia najkrótszej ścieżki w grafie, która przechodzi przez wszystkie wierzchołki.