Baze sablona za resavanje 15 puzle

[NikolaNemes]

Clanovi tima: Nikola Nemeš sw7-2016 grupa 1 Asistent: Aleksandar Lukić Problem koji se rešava: U pitanju je klasičan problem pretrage. Cilj je pronaći sve korake koji nas od početnog stanja dovode do ciljnog. U ovom slucaju ciljno stanje je ono u kojem se u prvoj poziciji se nalazi prazan prostor, dok preostale pozicije trebaju da budu popunjene pločicama sortiranim po veličini. Cilj ovog projekta je pronaći/implementirati sto bolju heuristiku. Algoritam br. 1: Trenutno najbolja heuristicka funkcija za resavanje ovog problema (i njemu sličnih) su aditivne baze šablona. Razlog zašto jednostavnije heuristike kao menhetn razdaljina ovde nisu dovoljne, je zato što one ignorišu kompleksnost kretanja pločica. Na primer, u slučaju da su sve pločice na dobrim pozicijama sem pločica br. 1 i br. 2, menhetn razdaljina bi vraćala vrednost 2. U slučaju da su ove dve pločice smaknute za jedno mesto, to bi bilo tačno, ali ukoliko su invertovane (ide 2 pa 1) broj koraka do rešenja postaje znatno veći. Glavna ideja aditivnih baza šablona je da one uračunavaju ta dodatna ograničenja pri kretanju pločica. Način na koji ovo postižemo je tako što apstrahujemo prostor pretrage. Radi primera možemo uzeti da posmatramo ponovo pločice br. 1 i br. 2 . Kada posmatramo ove pločice, možemo sve ostale da zanemarujemo. Cilj nam je da za sve moguce kombinacije pozicija ovih pločica pronađemo broj koraka do optimalnog rešenja. Ovo se postiže tako što uradimo pretragu po širini počevši od rešenog stanja i za svaku moguću kombinaciju pločica br. 1 i br. 2 zapišemo koliko su udaljene od rešenja. Kada prođemo kroz sve mogućnosti, dobijamo tabelu koja za ove dve pločice daje udaljenost od optimalnog rešenja za sve njihove moguće pozicije. Aditivne baze šablona funkcionišu tako što ovaj princip primenimo na više disjunktnih skupova pločica. Što su ovi skupovi veći, to je heuristika bliža stvarnoj udaljenosti trenutnog stanja od ciljnog. Glavni problem zašto skupove ne možemo tako lako povećavati je sve veće zauzeće memorije. U ovom našem primeru, tabela bi bila veličine 16 * 15 = 240. Trenutno najbolja kombinacija skupova za rešavanje ove puzle je podela 7-8. Ovo znači da jedan skup sadrži prvih 7 pločica, dok drugi sadrži preostalih 8. Ove dve tabele sadrže 58 miliona i 518 miliona članova respektivno. Samo računanje ovih tabela traje nekoliko sati, ali uz njih moguće je rešiti najteže instance ove puzle (dubina 80) za manje od jedne sekunde. Ovakve tabele se mogu koristiti za rešavanje sličnih puzli kao što su rubikova kocka i tower of hanoi. Više o ovom algoritmu može se pročitati u naučnom radu tvoraca algoritma: https://www.aaai.org/Papers/JAIR/Vol22/JAIR-2209.pdf Algoritam br. 2:: Pošto tabele u prethodno navedenom algoritmu zauzimaju mnogo prostora u memoriji, probaćemo da ih zamenimo sa neuronskim mrežama. Svaku tabelu će zameniti jedna neuronska mreža. Metrika za merenje performansi: Kao glavnu metriku za merenje performansi posmatraćemo broj razvijenih čvorova. Pošto neuronska mreža najverovatnije neće generisati dopustivu heuristiku, kao dodatnu metriku možemo posmatrati i optimalnost rešenja. Validacija rešenja: Proveravaće se dopustivost heuristike (u slučaju tabela) i porediće se rezultati ovog trenutnog rada sa rezultatima prethodnih već objavljenih rešenja. Takođe ćemo uporediti rezultate dobijene od heuristike sa tabelom sa rezultatima dobijenim pomoću neuronskih mreža.

[lukic-aleksandar]

Tema odobrena. Ostavi link ka GitHub repozitorijumu projekta. Srećan rad.

[NikolaNemes]

Link od repozitorijuma projekta: https://github.com/NikolaNemes/Pattern-databases