Usporedba odabranih algoritama za problem trgovačkog putnika

završni rad

• Naslov (engleski): Comparison of Algorithms for Solving Traveling Salesman Problem
• Autor: Mislav Korotaj
• Mentor: Ilko Brnetić (mentor)
• Član povjerenstva: Ilko Brnetić (predsjednik povjerenstva)
• Član povjerenstva: Andrea Aglić Aljinović (član povjerenstva)
• Član povjerenstva: Mate Puljiz (č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-06-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Problem trgovačkog putnika jedan je od najpoznatijih problema iz područja kombinatoričke optimizacije. U ovom problemu, trgovački putnik mora obići sve gradove točno jednom i vratiti se u početni grad pri čemu se traži minimalna duljina puta.
Iako se na prvi pogled čini jednostavnim za manji broj gradova (ili općenito vrhova u grafu), složenost mu eksponencijalno raste s povećanjem broja gradova, što ga čini izrazito teškim za rješavanje
U ovom radu proučeni su razni algoritmi za rješavanje simetričnog problema trgovačkog putnika koji pokušavaju zaobići potrebu pretrage svih mogućih Hamiltonovskih ciklusa: iscrpna pretraga s gornjom granicom, branch and bound, dinamičko programiranje i algoritam najbližeg susjeda. Napravljena je analiza vremenske i prostorne složenosti tih algoritama. U praktičnom dijelu razvijeno je programsko rješenje koje implementira sve proučene algoritme. Na kraju su rezultati analizirani, uzete su statistike i doneseni zaključci.

Sažetak (engleski)

The traveling salesman problem (TSP) is one of the most well-known problems in the field of combinatorial optimization. In this problem, a traveling salesman must visit all cities exactly once and return to the starting city, seeking the shortest possible route.
Although it may seem straightforward for a small number of cities (or generally vertices in a graph) at first glance, its complexity grows exponentially with the increase in the number of cities, making it extremely difficult to solve.
This paper examines various algorithms for solving the symmetric traveling salesman problem that attempt to circumvent the need to search through all possible Hamiltonian cycles: exhaustive search with an upper bound, branch and bound, dynamic programming, and the nearest neighbor algorithm. An analysis of the time and space complexity of these algorithms was conducted. In the practical part, a software solution was developed to implement all the studied algorithms. Finally, the results were analyzed, statistics were collected, and conclusions were drawn.

• Ključne riječi: simetrični problem trgovačkog putnika; iscrpna pretraga; branch and bound; dinamičko programiranje; Held-Karp algoritam; algoritam najbližeg susjeda
• Ključne riječi (engleski): traveling salesman problem; exhaustive search; branch and bound; dynamic programming; Held-Karp algorithm; nearest neighbor algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:826280
• Studijski program: Naziv: Računarstvo; 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: 2024-10-12 21:07:21