Primárním cílem tohoto projektu je navrhnout a implementovat efektivní řešení problému Puzzle8. To zahrnuje vytvoření algoritmu, který najde nejkratší možnou cestu k vyřešení puzzle z jakéhokoli počátečního stavu a zároveň poskytne uživatelsky přívětivé rozhraní pro vizualizaci kroků k řešení.

K řešení problému Puzzle8 jsem využil vyhledávací algoritmus A* (A-hvězdička), populární a efektivní algoritmus pro hledání cesty v informatice. A* kombinuje silné stránky prohledávání do šířky a do hloubky pomocí prioritní fronty pro zkoumání nejslibnějších stavů jako první.

Algoritmus hodnotí každý možný stav puzzle pomocí následující nákladové funkce:

f(n) = g(n) + h(n)

• g(n) jsou náklady na dosažení aktuálního stavu.
• h(n) je heuristický odhad nákladů na dosažení cílového stavu.

Jako heuristickou funkci jsem zvolil Manhattanskou vzdálenost, která měří celkový počet tahů, které každá dlaždice potřebuje k dosažení své cílové pozice. Tato heuristika je jak přípustná, tak konzistentní, což zajišťuje optimální řešení.

GUI bylo vytvořeno pomocí SvelteKit a TypeScript pro poskytnutí responzivního a interaktivního uživatelského zážitku. Uživatelé mohou zadávat konfigurace puzzle a sledovat, jak algoritmus A* řeší puzzle krok za krokem.

Projekt úspěšně splňuje svůj cíl efektivním řešením problému Puzzle8 a poskytováním jasné vizualizace procesu řešení. Algoritmus A* konzistentně nachází optimální řešení a GUI založené na SvelteKit nabízí plynulý a intuitivní uživatelský zážitek. Tento projekt demonstruje praktickou aplikaci vyhledávacích algoritmů při řešení složitých problémů a zdůrazňuje důležitost heuristických funkcí při optimalizaci efektivity vyhledávání.