|
|
Informované prohledávání prostoru řešení pomocí algoritmu A*
Kobr, Dan ; Berka, Petr (vedoucí práce) ; Ivánek, Jiří (oponent)
Diplomová práce se zabývá analýzou algoritmů informovaného prohledávání. Teoretická část práce nejprve uvádí přehled teorie a základních pojmů, které se vážou k tématu umělé inteligence. Jedná se o pojmy z oblasti diskrétní matematiky a teorie grafů, dále o oblast umělé inteligence a agentních systémů. Hlavním cílem teoretické části práce je poskytnout přehled algoritmů neinformovaného a informovaného prohledávání. Tato část charakterizuje algoritmy prohledávání do hloubky, prohledávání do šířky a jejich možné varianty. Z oblasti informovaného prohledávání jsou popsány algoritmy A* (A-Star), IDA* (Iterative Deepening A-Star) a SMA* (Simplified Memory bounded A-Star), v souvislosti s těmito algoritmy jsou zmíněny také vlastnosti heuristických funkcí a problematika relaxace problému. Uvedené algoritmy jsou podrobeny teoretické analýze časové a paměťové složitosti, která je východiskem pro praktickou část práce. Cílem praktické části je implementace softwarového nástroje pro analýzu výkonnosti algoritmů informovaného a neinformovaného prohledávání. Pro účely této analýzy je zvolena konkrétní úloha -- Lloydova patnáctka. Rozbor této úlohy z matematického a informatického hlediska tvoří úvodní část praktické části práce, následuje analýza možných variant implementace programu a návrh jeho jednotlivých komponent. Předmětem další části je popis základních rozhraní a tříd implementované aplikace, která je přílohou této práce. Poslední část analyzuje pomocí vyvinuté aplikace algoritmy informovaného a neinformovaného prohledávání představené v teoretické části práce, srovnává získané výsledky a vyhodnocuje je na základě teoretických předpokladů, uvedených v teoretické části.
|
host ::
RSS.