Problem trgovačkog putnika

Izvor: Wikipedia
Salesman.PNG

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[uredi - уреди]

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[uredi - уреди]

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 O(2^n). Mada je ovo vreme eksponencijalno, ipak je mnogo jeftinije od 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.

Reference[uredi - уреди]

  1. Euklidski problem trgovačkog putnika je onaj kod koga između gradova važi nejednakost trougla - drugim rečima, između svaka dva grada najkraći mogući put je upravo direktan put (put A-B-V ne može biti kraći od puta A-V).


Spoljašnje veze[uredi - уреди]