Problem komiwojażera - strona 2

się w podróż poślubną).

Problem ten jest także przykładem obrazującym trudności stojące przed matematyką oraz ograniczoność możliwości obliczeniowych komputerów. Oto bowiem dla pięciu miast mamy 24 możliwe trasy do przeanalizowania, natomiast dla - przykładowo - trzynastu miast liczba tras wynosi aż 3,1 \cdot10^9. Zadania tego nie rozwiąże dziś żaden komputer w czasie krótszym niż wiek. A przecież 13 miast (lub 13 przystanków autobusowych w średnim mieście, jak ktoś woli) to niezbyt dużo.

Problemy tego typu - tzn. takie, których rozwiązania nie da się znaleźć w tzw. czasie wielomianowym - nazywamy NP (niedeterministycznie wielomianowymi, z ang. nondeterministic polynomial) - innymi słowy, złożoność takiego problemu rośnie szybciej niż dowolny wielomian.

Komentarze (0)
Wynik działania 2 + 2 =
Ostatnio komentowane
Pozdro
Kks • 2020-09-30 20:38:18
elo elo
eloelo • 2020-09-30 17:38:43
fajne
siema • 2020-09-30 17:25:21
ukvhgj n
bvjhn • 2020-09-30 16:14:26
1
B • 2020-09-30 14:36:33