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.