Heuristički algoritmi za problem trgovačkog putnika

undergraduate thesis

• Title (english): Heuristic algorithms for the traveling salesman problem
• Author: Filip Perušić
• Mentor: Anamari Nakić (mentor)
• Committee member: Anamari Nakić (predsjednik povjerenstva)
• Committee member: Tea Arvaj (član povjerenstva)
• Committee member: Filip Martinović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-07-09, Croatia

Abstract

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... More 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. Less

Abstract (english)

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... More 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. Less

• Keywords: Problem trgovačkog putnika; Teorija grafova; Heuristički algoritmi; Genetski algoritam; Algoritam najbližeg susjeda; Pohlepni heuristički algoritam; Algoritam grube sile
• Keywords (english): Traveling Salesman Problem; graph theory; heuristic algorithms; Genetic Algorithm; Nearest Neighbour Algorithm; Greedy Heuristic Algorithm; Brute Force Algorithm
• Language: english
• URN:NBN: urn:nbn:hr:168:771260
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2025-02-25 14:57:58