Heurističko rješenje za problem pronalaska najduljeg lanca u igri Kaladont

diplomski rad

• Naslov (engleski): A heuristic solution for the problem of finding the longest chain in the Kaladont game
• Autor: Leon Novački
• Mentor: Marko Đurasević (mentor)
• Član povjerenstva: Marko Đurasević (predsjednik povjerenstva)
• Član povjerenstva: Domagoj Jakobović (član povjerenstva)
• Član povjerenstva: Nikolina Frid (č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-02-16, Hrvatska

Sažetak

Ovaj rad istražuje problem pronalaska najduljeg lanca riječi u igri Kaladont i uspore-
đuje ga s problemom pronalaska najduljeg puta u grafu. Opisuje se motivacija za prona-
laženje najduljeg puta u grafu te se objašnjava kako se cjelobrojnim linearnim programi-
ranjem može riješiti taj problem. Na skupu podataka je pronađen najdulji mogući lanac
i rješenje je uspoređeno s drugim najboljim rješenjima. Rezultati također pokazuju da je
postignuto optimalno rješenje.

Sažetak (engleski)

This work investigates the problem of finding the longest word chain in the word
game Kaladont and draws parallels with finding the longest path in a graph. It ex-
plains the motivation behind finding the longest path in a graph and explains how it
can be solved using integer linear programming. On a given dataset, the longest possible
chain is identified, and the solution is compared to other best-performing solutions and
is shown to be the optimal solution.

• Ključne riječi: najdulji put u grafu; igra Kaladont; cjelobrojno linearno programiranje
• Ključne riječi (engleski): longest path in a graph; Kaladont word game; Integer linear programming
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:202071
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2024-03-28 07:51:37