NexTutor
Baza wiedzy/Zagadki/Problem komiwojażera
Matematykatrudny

Problem komiwojażera

Problem komiwojażera Siedem miast i najkrótsza trasa odwiedzająca każde raz i wracająca do startu; liczba możliwych tras rośnie silniowo. Problem komiwojażera — najkrótsza pętla start n miast → (n−1)!/2 tras 10 miast → 181 440 15 miast → ~43 mld 20 miast → > 10¹⁷ Trasę łatwo sprawdzić, ale najkrótszej nie da się znaleźć przez przeszukanie wszystkich — to problem NP-trudny.

Pytanie

Odwiedź wszystkie miasta raz i wróć — najkrótszą trasą. Czemu to takie trudne?

Najpierw spróbuj zgadnąć — dopiero potem odsłoń podpowiedź.

PodpowiedźPokaż

Policz, ile jest możliwych tras dla 20 miast.

Pokaż rozwiązanie

Liczba tras rośnie szybciej niż wykładniczo — dla wielu miast żaden komputer nie sprawdzi wszystkich.

Moment „aha”

Dla n miast jest rzędu (n−1)!/2 tras — dla 20 miast ponad 10¹⁷. Sztandarowy problem NP-trudny: trasę łatwo sprawdzić, ale najlepszą trudno znaleźć. Kluczowy dla logistyki i projektowania układów.

Powiązania

Matematyka przez wiekiścieżkaMaszyny licząceścieżka