prikaz prve stranice dokumenta Usporedba odabranih algoritama za problem trgovačkog putnika
Rad nije dostupan
završni rad
Usporedba odabranih algoritama za problem trgovačkog putnika
Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2024. urn:nbn:hr:168:826280
Korotaj, Mislav
Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

Institucijski repozitorij: Repozitorij FER-a

Citirajte ovaj rad

Korotaj, M. (2024). Usporedba odabranih algoritama za problem trgovačkog putnika (Završni rad). Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:168:826280

Korotaj, Mislav. "Usporedba odabranih algoritama za problem trgovačkog putnika." Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2024. https://urn.nsk.hr/urn:nbn:hr:168:826280

Korotaj, Mislav. "Usporedba odabranih algoritama za problem trgovačkog putnika." Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2024. https://urn.nsk.hr/urn:nbn:hr:168:826280

Korotaj, M. (2024). 'Usporedba odabranih algoritama za problem trgovačkog putnika', Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, citirano: 30.11.2024., https://urn.nsk.hr/urn:nbn:hr:168:826280

Korotaj M. Usporedba odabranih algoritama za problem trgovačkog putnika [Završni rad]. Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva; 2024 [pristupljeno 30.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:826280

M. Korotaj, "Usporedba odabranih algoritama za problem trgovačkog putnika", Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, Zagreb, 2024. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:826280

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:168:826280
Podaci o radu
NaslovUsporedba odabranih algoritama za problem trgovačkog putnika
Naslov (engleski)Comparison of Algorithms for Solving Traveling Salesman Problem
AutorMislav Korotaj
MentorIlko Brnetić (mentor)
Član povjerenstvaIlko Brnetić (predsjednik povjerenstva)
Član povjerenstvaAndrea Aglić Aljinović (član povjerenstva)
Član povjerenstvaMate 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 obrane2024-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
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:168:826280
Studijski programNaziv: 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 resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaZatvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Javna napomena
Datum i vrijeme pohrane2024-10-12 21:07:21