Na stronie używamy cookies. Korzystanie z witryny oznacza zgodę na ich wykorzystywanie. Szczegóły znajdziesz w Regulaminie.
ZAMKNIJ X

Problem komiwojażera - strona 2

Ostatnio komentowane
ok
julian • 2020-01-29 19:08:19
ciul
ciul • 2020-01-29 12:16:47
Całkiem przydatne! ...
Anna Maria-Wesołowska • 2020-01-25 16:25:01
Rodzina (na szczęście) nie jest przystankiem lecz pierwszą naturalną grupą społeczn...
Władysław • 2020-01-25 07:50:20
W ostatnich latach na naszym rynku prasowym pojawiło się wiele kolorowych, pięknie wyda...
Władysław • 2020-01-25 07:46:55
Autor:
Drukuj
Drukuj
Rozmiar
AAA

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.

Polecamy również:

Komentarze (0)
4 + 3 =