Heuristički algoritmi za problem trgovačkog putnika

završni rad

• Naslov (engleski): Heuristic algorithms for the traveling salesman problem
• Autor: Filip Perušić
• Mentor: Anamari Nakić (mentor)
• Član povjerenstva: Anamari Nakić (predsjednik povjerenstva)
• Član povjerenstva: Tea Arvaj (član povjerenstva)
• Član povjerenstva: Filip Martinović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2024-07-09, Hrvatska

Sažetak

Problem trgovačkog putnika poznat je izazov optimizacije u računalnim znanostima, koji traži najkraći put za posjet skupu gradova i povratak u početni grad bez ostavljanja neposjećenih gradova. Ovaj rad pruža implementaciju tri heuristička algoritma: pohlepni heuristički algoritam, genetski algoritam i algoritam najbližeg susjeda unutar aplikacije TSP Explorer. Aplikacija omogućava vizualizaciju i metrike performansi koje se koriste za analizu rezultata implementiranih algoritama. Heurističke metode, posebice genetski algoritam, nude učinkovita rješenja za manje slučajeve, dok algoritam najbližeg susjeda bolje djeluje na većim slučajevima zbog implementacije genetskog algoritma.

Sažetak (engleski)

The Traveling Salesman Problem is a well-known optimization challenge in computer science, seeking the shortest route to visit a set of cities and returning to the starting city leaving no city unvisited. This thesis provided an implementation of three heuristic algorithms, Greedy Heuristic, Genetic Algorithm and Nearest Neighbour Algorithm inside a TSP Explorer application. The application provided the visualization and performance metrics used for analyzing the results of the implemented algorithms. Heuristic methods, especially the Genetic Algorithm, offer effective solutions for smaller instances, while the Nearest Neighbour Algorithm performs better on larger instances due to the implementation of the Genetic Algorithm.

• Ključne riječi: Problem trgovačkog putnika; Teorija grafova; Heuristički algoritmi; Genetski algoritam; Algoritam najbližeg susjeda; Pohlepni heuristički algoritam; Algoritam grube sile
• Ključne riječi (engleski): Traveling Salesman Problem; graph theory; heuristic algorithms; Genetic Algorithm; Nearest Neighbour Algorithm; Greedy Heuristic Algorithm; Brute Force Algorithm
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:771260
• Studijski program: Naziv: Computing; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ. bacc. ing. comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2025-02-25 14:57:58