|
|
Incomplete Search Techniques
Lehotský, Jakub ; Barták, Roman (vedoucí práce) ; Surynek, Pavel (oponent)
Název práce: Neúplné vyhledávací algoritmy Autor: Jakub Lehotský Katedra: Katedra teoretické informatiky a matematické logiky Vedoucí diplomové práce: Doc. RNDr. Roman Barták, Ph.D. e-mail vedoucího: bartak@ktiml.mff.cuni.cz Abstrakt:Problémy s omezujícími podmínkami jsou množinou diskrétních optimalizačních problémů, které řeší mnoho problémů ze skutečného života. Jsou řešeny inferenčními a vyhledávacími algoritmy. Ve většině případů úplné vyhledávací algoritmy dokážou najít řešení, existují ale problémy, kterých zložitost je příliš vysoká na to, aby byl prostor řešení prozkoumán kompletně. V týchto případech musíme zavést omezení, které ořežou velikost stavového prostoru pro vyhledávání. Algoritmy založené na diskrepancích omezují počet případů, kde se algoritmus rozhodne proti dané heuristice. Neúplné vyhledávací algoritmy negarantují nalezení řešení. Mnoho vyhledávacích algoritmů má vlastnost any-time, která nám poskytuje nějaké řešení optimalizačního problému v libovlný časový okamih, i když řešení ještě není optimální. Klíčová slova: CSP, neúplné vyhledávání, vyhledávání s diskrep- ancemi 1
|
host ::
RSS.