Autor Wątek: Problem komiwojażera algorytm  (Przeczytany 1749 razy)

Offline Zarejestruj

  • Użytkownik

# 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.
« Ostatnia zmiana: Luty 14, 2016, 20:03:15 wysłana przez Zarejestruj »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Kos

  • Użytkownik
    • kos.gd

# Luty 14, 2016, 19:19:11

Offline koirat

  • Użytkownik

# 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.

Offline CheshireCat

  • Użytkownik

# 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.

Offline Zarejestruj

  • Użytkownik

# 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?

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

  • +3
# 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).