Naslov
Rješavanje problema trgovačkog putnika klasičnim i naprednim algoritmima
(Traveling Salesman Problem Solving by Classic and Advanced Algorithms)

Autori
Bajer, Dražen

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, diplomski

Fakultet
Elektrotehnički fakultet

Mjesto
Osijek

Datum
08.12

Godina
2010

Stranica
58

Mentor
Martinović, Goran

Ključne riječi
2-opt algoritam; algoritam elitističkog mravljeg sustava; algoritam najbližeg susjeda; genetski algoritam; problem trgovačkog putnika
(2-opt algorithm; elitist ant system algorithm; nearest neighbor algorithm; genetic algorithm; traveling salesman problem)

Sažetak
Problem trgovačkog putnika je vrlo poznat i proučavan problem kombinatorne optimizacije. Od početka njegovog proučavanja do danas, za njegovo rješavanje primjenjivani su mnogi algoritmi, s različitim uspjehom. U ovom diplomskom radu su predstavljena četiri popularna približna algoritma ili heuristike koji se mogu koristiti za rješavanje problema trgovačkog putnika. Algoritam najbližeg susjeda i 2-opt algoritam mogu se svrstati u klasične algoritme, dok se genetski algoritam i algoritam elitističkog mravljeg sustava, kao i njihove inačice s ugrađenom lokalnom pretragom, mogu svrstati u napredne algoritme ili metaheuristike. Prikazani su načini rada navedenih algoritama, te programsko rješenje u koje su ugrađeni, razvijeno u svrhu njihove analize. Analizom su prikazane dobre i loše strane algoritama, odnosno njihova učinkovitost pri rješavanju problema trgovačkog putnika na temelju dobivenih rješenja i vremena izvođenja. Uz, u radu provedena unaprjeđenja nekih od navedenih algoritama, dane su smjernice za moguća daljnja unaprjeđenja u konkretnom, ali i u općem slučaju.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA