Problém seřazení osmi čtverečků
Úloha č. 2 pro cvičení k předmětu Vybrané kapitoly z umělé inteligence
Zadání: Implementujte v libovolném programovacímjazyce obě heuristiky zmíněné na přednášce pro uspořádání osmi čtverečků na ploše s devíti pozicemi (plocha 3><3), kde konečné pořadí čtverečků označených čísly je 1,2,3,4,5,6,7,8, přičemž volné políčko zůstane uprostřed (obrázek je v PDF souboru popisujícím informované hledání). Požadované heuristiky jsou manhattanská vzdálenost a chybné umístění.
Vygenerujte náhodně 5 počátečních pozic (rozmístění čtverečků) a pro každou počáteční pozici vyzkoušejte obě heuristiky. Na závěr spočítejte průměrnou efektivnost pro každou heuristiku (každá by měla mít 5 pokusů dle zadání). Srovnejte oba výsledky a určete, která z obou heuristik je účinnější. Účinnost vyjádřete v počtu kroků nutných k dosažení cílového stavu (jeden krok je jedno posunutí čtverečků). V každém případě uveďte závěr z poznatků získaných při řešení úlohy (tj. co vám z toho vyplynulo, zdali a jak se dá zvolený postup zobecnit, apod.).
Výsledek úlohy pošlete přes e-mail obdobně jako pro úlohu č. 1; subjekt e-mailu bude obsahovat text 8-CTVERECKU ajméno a příjmení autora řešení. Další podmínky odevzdání, včetně termínu a procentového ohodnocení, jsou stejné jako u úlohy č. 1.
Pozn.: V případě, kdy některá z heuristik ani po mnoha pokusech nebude schopna najít řešení, pokuste se neúspěch zdůvodnit (nezapomeňte, že jde "pouze" o heuristiku). K neúspěchu může někdy dojít, pak lze udělat další pokus s dalšími náhodnými počátečními pozicemi.