Problem komiwojażera (TSP - ang. traveling salesman problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie.
Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość pomiędzy każdą parą miast.
Należy znaleźć najkrótszą trasę zaczynającą się np. z Warszawy, przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Warszawy.
Dzięki własnie szukałem tego rozwinięcia
OdpowiedzUsuńI mnie ten wpis bardzo się przydał:) Dzięki bardzo, powoli uczę się wszystkiego. Znalazłem też firmę https://ccrw.pl/unia-celna/ pomagającą przy eksporcie do Rosji, może i komuś też się przyda.
OdpowiedzUsuńCzekaj, a to "problem komiwojażera" to jest jakiś termin z logistyki? Nigdy wcześniej o tym nie słyszałam, ale z nazwy brzmi jakby chodziło o to, jak najlepiej zaplanować trasę czy coś? Próbuję to ogarnąć — czy to ma związek z dostawami i oszczędzaniem czasu? Natknęłam się ostatnio na stronę https://grafik.warszawa.pl, gdzie też jest coś o planowaniu, ale to raczej inne spektrum. Ciekawa jestem jak to się praktycznie wygląda!
OdpowiedzUsuń