Traveling Salesman Problem Solving by Classic and Advanced Algorithms (CROSBI ID 362349)
Ocjenski rad | diplomski rad
Podaci o odgovornosti
Bajer, Dražen
Martinović, Goran
engleski
Traveling Salesman Problem Solving by Classic and Advanced Algorithms
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.
2-opt algorithm; elitist ant system algorithm; nearest neighbor algorithm; genetic algorithm; traveling salesman problem
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o izdanju
58
08.12.2010.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Osijek