20.500.12556/RUL-179430 Problem igre poplavljanja barv Flood fill game problem V diplomskem delu obravnavamo problem poplavljanja barv, v literaturi znan kot igra Flood-It, pri kateri je cilj z minimalnim številom potez prebarvati mrežo kvadratkov v enotno barvo. Problem formalno definiramo na diskretni mreži in ga posplošimo na poljubno povezane grafe. V teoretičnem delu podamo dokaz NP-težkosti problema s pomočjo polinomske prevedbe iz problema najkrajšega skupnega nadniza (SCS). Za iskanje optimalnih rešitev problem prevedemo v obliko logične izpolnljivosti (SAT) v konjunktivno normalno obliko (CNF). Z uporabo sodobnih SAT-reševalnikov analiziramo meje rešljivosti problemov in ugotavljamo, da so eksaktne metode učinkovite predvsem pri manjših in srednje velikih primerkih. Z regresijsko analizo na generiranih grafih identificiramo ključne topološke metrike, kot sta povprečna dolžina poti in število barv, ki močno korelirata z zahtevnostjo problema. Zaradi eksponentne časovne zahtevnosti eksaktnih metod v zadnjem delu razvijemo in ovrednotimo več hevrističnih algoritmov. Rezultati kažejo, da globalna hevristika, ki minimizira vsoto razdalj do neobiskanih vozlišč, dosega rezultate, ki so blizu teoretičnim optimalnim vrednostim tudi na velikih mrežah dimenzij do$300 x 300. In this thesis, we address the flood-fill problem, known in the literature as the game Flood-It, where the objective is to unify the color of a grid of squares in the minimum number of moves. The problem is formally defined on a discrete grid and generalized to arbitrary connected graphs. In the theoretical section, we present a proof of the problem’s NP-hardness via a polynomial reduction from the Shortest Common Supersequence (SCS) problem. To find optimal solutions, we transform the problem into a Boolean Sat isfiability (SAT) problem in Conjunctive Normal Form (CNF). Using state of-the-art SAT solvers, we analyze the limits of solvability and find that exact methods are effective primarily for small and medium-sized instances. Through regression analysis on generated graphs, we identify key topolog ical metrics, such as average path length and the number of colors, which correlate strongly with the problem’s complexity. Due to the exponential time complexity of exact methods, the final part of the thesis involves the development and evaluation of several heuristic algorithms. The results indicate that a global heuristic, which minimizes the sum of distances to unvisited nodes, achieves results close to theoretical optimal values even on large grids with dimensions up to 300 × 300. poplavljanje barv NP-polni problemi SAT hevristike flood fill NP-complete problems SAT heuristics true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2026-02-13 11:40:02 2026-02-13 11:40:10 2026-03-03 06:04:00 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 38122 270184451 Kralj_Matej_-_Problem_igre_poplavljanja_barv.pdf Kralj_Matej_-_Problem_igre_poplavljanja_barv.pdf 1 4D2534DE58E0AD80CF4FC6B8A71DF51E 20bf88f994aa92eb340673f022263a973d4b35398e63fc32914e6f261a945191 332cd475-08c8-11f1-a1ba-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=227935 Fakulteta za računalništvo in informatiko 0 0 0