prikaz prve stranice dokumenta Heuristički algoritmi za geometrijski problem trgovačkog putnika
Rad nije dostupan
završni rad
Heuristički algoritmi za geometrijski problem trgovačkog putnika
Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2019. urn:nbn:hr:168:998359
Mihalj, Petar
Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

Institucijski repozitorij: Repozitorij FER-a

Citirajte ovaj rad

Mihalj, P. (2019). Heuristički algoritmi za geometrijski 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:998359

Mihalj, Petar. "Heuristički algoritmi za geometrijski problem trgovačkog putnika." Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2019. https://urn.nsk.hr/urn:nbn:hr:168:998359

Mihalj, Petar. "Heuristički algoritmi za geometrijski problem trgovačkog putnika." Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2019. https://urn.nsk.hr/urn:nbn:hr:168:998359

Mihalj, P. (2019). 'Heuristički algoritmi za geometrijski problem trgovačkog putnika', Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, citirano: 27.12.2024., https://urn.nsk.hr/urn:nbn:hr:168:998359

Mihalj P. Heuristički algoritmi za geometrijski problem trgovačkog putnika [Završni rad]. Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva; 2019 [pristupljeno 27.12.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:998359

P. Mihalj, "Heuristički algoritmi za geometrijski problem trgovačkog putnika", Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, Zagreb, 2019. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:998359

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:168:998359
Podaci o radu
NaslovHeuristički algoritmi za geometrijski problem trgovačkog putnika
Naslov (engleski)Heuristic Algorithms for Geometric Traveling Salesman Problem
AutorPetar Mihalj
MentorMario Osvin Pavčević (mentor)
Član povjerenstvaMario Osvin Pavčević (predsjednik povjerenstva)
Član povjerenstvaMario Krnić (član povjerenstva)
Član povjerenstvaDomagoj Kovačević (č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 obrane2019-07-12, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		TEHNIČKE ZNANOSTI
Računarstvo
Sažetak
Problem trgovačkog putnika (TSP) poznati je problem kombinatorne optimizacije koji se bavi određivanjem hamiltonovskog ciklusa najmanje težine u danom grafu. Istražujemo heurističke algoritme za posebnu vrstu ovog problema - geometrijski TSP (GTSP). GTSP je poseban slučaj TSP-a koji zahtijeva da vrhovima odgovaraju točke euklidskog prostora i da težine bridova odgovaraju udaljenostima između točaka. Implementirali smo i egzaktne i heurističke algoritme, zajedno sa potrebnim strukturama podataka. Nakon procjene performansi heurističkih algoritama na uniformnim skupovima podataka, testirali smo ih na grafovima iz TSPLIB baze grafova. Heuristički algoritmi dali su relativno dobre rezultate za neke primjene, i implementirani sa prikladnim strukturama podataka, pokazali iznimnu brzinu izvođenja.
Sažetak (engleski)
Travelling salesman problem (TSP) is a well known combinatorial optimisation problem concerned with finding a Hamiltonian cycle with minimum weight in a given graph. We discuss heuristic algorithms for a specific type of this problem - geometric TSP (GTSP). GTSP is a specific case of TSP that requires vertices to be assigned points in Euclidean space and edge weights to be equal to Euclidean distances between points. We have implemented both exact and heuristic algorithms, along with required data structures. After evaluating the performance of heuristic algorithms on uniform datasets, we have tested algorithms on graphs in TSPLIB graph library. Heuristic algorithms have given relatively good results for some applications, and have shown exceptional runtime speed when implemented using appropriate data structures.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:168:998359
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 pohrane2020-01-07 20:22:15