Warsztat.GD

Programowanie => Językoznawstwo => C++ => Wątek zaczęty przez: Zarejestruj w Luty 14, 2016, 18:11:54

Tytuł: Problem komiwojażera algorytm
Wiadomość wysłana przez: Zarejestruj w Luty 14, 2016, 18:11:54
Czy ktoś może wie jakim algorytmem najprościej zaimplementować problem komiwojażera? Codziennie od października mówiłem sobie, że jutro już się za to wezme, a właśnie sie dowiedziałem że dzisiaj był ostatni dzień na oddanie tego a nie mam nawet dokumentacji do tego. Jestem cały zdenerwowany, nie wiem czy uda mi się przekonać nauczyciela żeby pozwolił to oddać w następnym terminie.
Tytuł: Odp: Problem komiwojażera algorytm
Wiadomość wysłana przez: Kos w Luty 14, 2016, 19:19:11
(https://imgs.xkcd.com/comics/travelling_salesman_problem.png) (https://xkcd.com/399/)
Tytuł: Odp: Problem komiwojażera algorytm
Wiadomość wysłana przez: koirat w Luty 14, 2016, 20:12:53
Czy ktoś może wie jakim algorytmem najprościej zaimplementować problem komiwojażera?
Najprościej to brute-force-em. Jednak domyślam się iż nauczycielowi chodzi o zastosowanie jakiegoś algorytmu ewolucyjnego.
Tytuł: Odp: Problem komiwojażera algorytm
Wiadomość wysłana przez: CheshireCat w Luty 14, 2016, 20:21:23
Algorytm mrówkowy (Ant Colony Optimization) całkiem nieźle sobie radzi z TSP.

Ale najprościej zaimplementować jest faktycznie brute-force, tylko nie licz na wynik w rozsądnym czasie dla dużych grafów.
Tytuł: Odp: Problem komiwojażera algorytm
Wiadomość wysłana przez: Zarejestruj w Luty 14, 2016, 21:00:01
Ma w tym być jakaś inteligencja więc brute force raczej nie. A algorytm mrówkowy będzie łatwiejszy do zaimplementowania niż Dijkstry?
Tytuł: Odp: Problem komiwojażera algorytm
Wiadomość wysłana przez: Krzysiek K. w Luty 14, 2016, 22:20:47
Ale najprościej zaimplementować jest faktycznie brute-force, tylko nie licz na wynik w rozsądnym czasie dla dużych grafów.
Jeśli ma być prosto, działać w rozsądnym czasie i dawać rozsądne wyniki, to polecam oprzeć się na minimalnym drzewie rozpinającym. Znajdujesz minimalne drzewo rozpinające dla grafu połączeń i odwiedzasz wierzchołki w kolejności depth-first. W efekcie masz fajny czas i gwarancję że wynikowa droga nie będzie dłuższa niż dwukrotność drogi optymalnej (jeżeli dobrze pamiętam).