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

master's thesis

• Title (english): A heuristic solution for the problem of finding the longest chain in the Kaladont game
• Author: Leon Novački
• Mentor: Marko Đurasević (mentor)
• Committee member: Marko Đurasević (predsjednik povjerenstva)
• Committee member: Domagoj Jakobović (član povjerenstva)
• Committee member: Nikolina Frid (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-02-16, Croatia

Abstract

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.

Abstract (english)

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.

• Keywords: najdulji put u grafu; igra Kaladont; cjelobrojno linearno programiranje
• Keywords (english): longest path in a graph; Kaladont word game; Integer linear programming
• Language: croatian
• URN:NBN: urn:nbn:hr:168:202071
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2024-03-28 07:51:37