Problem trgovačkog putnika

Problem trgovačkog putnika je problem diskretne ili kombinatorne optimizacije. Ovaj problem ilustruje klasu problema iz oblasti teorije računske složenosti koji su teški za rešavanje.

Postavka problema

Ako je dat određen broj gradova, cene putovanja od bilo kog grada do bilo kog grada, koja je najjeftinija ruta koja obilazi svaki grad tačno jednom, i vraća se u početni grad?

Ekvivalentan problem izražen u terminima teorije grafova bi glasio: Dat je kompletan težinski graf (čiji čvorovi predstavljaju gradove, grane predstavljaju puteve, a težine predstavljaju cenu putovanja, ili dužinu puta) - naći Hamiltonov ciklus najmanje težine.

Može se pokazati da zahtev da se vrati u početni grad ne menja računsku kompleksnost ovog problema.

Rešenje ovog problema je od velikog praktičnog značaja, ne samo u pitanju saobraćaja. Dobar primer u kome je bitno na efikasan način rešiti problem trgovačkog putnika bi mogla da bude organizacija teretne luke: Ako se u luci u svakom trenutku nalazi više hiljada kontejnera, naslaganih jedni na druge, i svakodnevno se stotine kontejnera iskrcavaju sa brodova, ili tovare na šlepere, koji je optimalan redosled kretanja kranova za utovar i istovar, i gde postaviti koji kontejner.

Računska kompleksnost

Najdirektnije rešenje bi bilo da se isprobaju sve permutacije, i da se vidi koja je najjeftinija (korišćenje metoda grube sile), ali kako je broj permutacija za n gradova n!, ovakvo rešenje vrlo brzo postaje nepraktično.

Korišćenjem tehnika dinamičkog programiranja, ovaj problem se može rešiti u vremenu ${\displaystyle O(2^{n})}$. Mada je ovo vreme eksponencijalno, ipak je mnogo jeftinije od ${\displaystyle O(n!)}$. Vidi Veliko O.

U slučaju da se radi o euklidskom^[1] problemu trgovačkog putnika, postoje razni vrlo brzi približni algoritmi, koji pronalaze puteve čija dužina je sigurno manja od dvostruke dužine najkraćeg mogućeg puta.