Problem komiwojażera
zagadnienie optymalizacyjne / Z Wikipedii, wolnej encyclopedia
Drogi AI, mówmy krótko, odpowiadając po prostu na te kluczowe pytania:
Czy możesz wymienić najważniejsze fakty i statystyki dotyczące Problem komiwojażera?
Podsumuj ten artykuł dla 10-latka
Problem komiwojażera (ang. travelling salesman problem, TSP) – zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym[1][2].
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ść / cena podróży / czas podróży pomiędzy każdą parą miast. Celem jest znalezienie najkrótszej / najtańszej / najszybszej drogi łączącej wszystkie miasta, zaczynającej się i kończącej się w określonym punkcie[1][2].
Symetryczny problem komiwojażera (STSP) polega na tym, że dla dowolnych miast A i B odległość z A do B jest taka sama jak z B do A. W asymetrycznym problemie komiwojażera (ATSP) odległości te mogą być różne.
Główną trudnością problemu jest duża liczba danych do analizy. W przypadku symetrycznego problemu komiwojażera dla n miast liczba kombinacji wynosi [3], tak więc dla 20 miast uzyskujemy wynik
Rozwinięciem problemu komiwojażera jest problem marszrutyzacji.
Przykładowe algorytmy znajdujące przybliżone rozwiązania problemu komiwojażera to algorytm najbliższego sąsiada i algorytm Christofidesa.