Original title:
Neúplné vyhledávací algoritmy
Translated title:
Incomplete Search Techniques
Authors:
Lehotský, Jakub ; Barták, Roman (advisor) ; Surynek, Pavel (referee) Document type: Master’s theses
Year:
2011
Language:
eng Abstract:
[eng][cze] Title:Incomplete Search Techniques Author: Jakub Lehotský Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Doc. RNDr. Roman Barták, Ph.D. Supervisor's email address: bartak@ktiml.mff.cuni.cz Abstract:The constraint satisfaction problems is set of discrete combinatorial problems which address to solve many of the real life problems. They are commonly solved by inference and search algorithms. In most cases the complete search algorithm can find a solution to a problem, but in many cases, search space is too large to be explored completely. In these case the limitation of search space is necessary in a way which gives us some way to still find a solution without having to search whole search space. Discrepancy-based search algorithms limit the search space by limiting the number where search decisions go against the heuristic in given search. Incomplete algorithms don't guarantee finding a solution. Many incomplete algorithms have any-time property useful in optimization problems, where algorithm provides some solution at any time even if it is not an optimal one. Keywords: CSP, incomplete search, discrepancy search 1Ná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
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/31470