prikaz prve stranice dokumenta Graf neuronske mreže za traženje Hamiltonovog puta
No public access
undergraduate thesis
Graf neuronske mreže za traženje Hamiltonovog puta
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2023. urn:nbn:hr:168:646268
Gaćina, Katarina
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Gaćina, K. (2023). Graf neuronske mreže za traženje Hamiltonovog puta (Undergraduate thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:646268

Gaćina, Katarina. "Graf neuronske mreže za traženje Hamiltonovog puta." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2023. https://urn.nsk.hr/urn:nbn:hr:168:646268

Gaćina, Katarina. "Graf neuronske mreže za traženje Hamiltonovog puta." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2023. https://urn.nsk.hr/urn:nbn:hr:168:646268

Gaćina, K. (2023). 'Graf neuronske mreže za traženje Hamiltonovog puta', Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 29 June 2024, https://urn.nsk.hr/urn:nbn:hr:168:646268

Gaćina K. Graf neuronske mreže za traženje Hamiltonovog puta [Undergraduate thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2023 [cited 2024 June 29] Available at: https://urn.nsk.hr/urn:nbn:hr:168:646268

K. Gaćina, "Graf neuronske mreže za traženje Hamiltonovog puta", Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2023. Available at: https://urn.nsk.hr/urn:nbn:hr:168:646268

Metadata
TitleGraf neuronske mreže za traženje Hamiltonovog puta
Title (english)Graph Neural Networks for Hamiltonian Pathfinding
AuthorKatarina Gaćina
MentorMile Šikić (mentor)
Committee memberMile Šikić (predsjednik povjerenstva)
Committee memberFilip Tomas (član povjerenstva)
Committee memberRafael Josip Penić (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2023-07-05, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Abstract
Pronalaženje puta koji posjećuje svaki vrh grafa točno jednom je problem iz teorije grafova poznat kao traženje Hamiltonovog puta. Traženje Hamiltonovog puta je NP-kompletan problem, što znači da je računski zahtjevan te bi stoga uporaba graf neuronskih mreža bila korisna. U ovom radu implementirano je šest različitih osnovnih graf neuronskih mreža kako bi se testirala njihova izvedba na problemu pronalaženja Hamiltonovog puta. Erdős-Rényi grafovi korišteni su za treniranje, validaciju i testiranje modela. Svaki model je testiran s različitim brojem slojeva, a najbolji od njih i s različitim početnim stopama učenja. Modeli su uspjeli naučiti kako pronaći Hamiltonov put, ali performanse opadaju s većim veličinama grafova.
Abstract (english)
Finding a route that visits every graph vertex precisely once is referred to as the graph theory problem known as Hamiltonian Pathfinding. Hamiltonian Pathfinding is an NP-complete problem, which means it is computationally expensive, and therefore the use of graph neural networks would be beneficial. In this paper, six different basic graph neural networks were implemented in order to test their performance on the Hamiltonian Pathfinding problem. Erdős-Rényi graphs were used for training, validation, and testing models. Each model was tested with a different number of layers, and the best model with two additional different starting learning rates. The models were able to learn how to find the Hamiltonian path, but performance drops with larger graph sizes.
Keywords
Keywords (english)
Languageenglish
URN:NBNurn:nbn:hr:168:646268
Study programmeTitle: 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 resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2023-10-11 08:52:24