| Meno: | Lukáš
|
|---|
| Priezvisko: | Ivan
|
|---|
| Názov: | Predpovedanie času riešenia pre ťažké logické úlohy
|
|---|
| Vedúci: | RNDr. Michal Forišek, PhD.
|
|---|
| Rok: | 2019
|
|---|
| Blok: | INF
|
|---|
| Kľúčové slová: | analýza stavového grafu, predpovedanie času, Rush Hour, významné vlastnosti, strojové učenie, zber dát
|
|---|
| Abstrakt: | Cieľom práce je skúmanie spôsobu, akým ľudia riešia konkrétne výpočtovo ťažké logické
úlohy a analýza ako syntaktické vlastnosti inštancií problémov ovplyvňujú obtiažnosť
danej inštancie. Riešenie problematiky má základ v analýze stavového grafu
vytvoreného z konkrétnych inštancií problému. V práci sa zaoberáme logickou úlohou
Rush Hour patriacou do množiny PSPACE-úplných problémov, pre ktorú sme vytvorili
webový portál na zber reálnych dát z riešenia úloh ľudským riešiteľom. Na účely
analýzy stavových grafov sme vytvorili program na vykresľovanie a manipuláciu 3D
grafov stavového priestoru. Zahŕňa aj grafy stavového priestoru vážené dátami z portálu,
návštevami a časom pobytu riešiteľov v grafových prvkoch. Na predpovedanie
času riešenia sme dáta z portálu spolu s externými dátami ďalej analyzovali pomocou
modelov strojového učenia. Pre zjednodušenie predikcie obtiažnosti sme vybrali
len niektoré vlastnosti stavového priestoru. Metódou prehľadávania mriežky sme získali
najlepšie modely a následne sme urobili extrakciu najvýznamnejších vlastností
pomocou metódy rekurzívneho eliminovania vlastností. Výsledkom práce je prediktor
obtiažnosti Rush Hour a identifikované významné vlastnosti, čo je možné v praxi použiť
na automatické generovanie primerane obtiažnych inštancií problému.
|
|---|