Learning cluster-based structure to solve constraint satisfaction problems

Autor:	Susan L. Epstein, Xingjian Li
Rok vydání:	2010
Předmět:	Constraint learning business.industry Applied Mathematics Brute-force search Min-conflicts algorithm Artificial Intelligence Search algorithm Beam search Guided Local Search Artificial intelligence business Local search (constraint satisfaction) Constraint satisfaction problem Mathematics
Zdroj:	Annals of Mathematics and Artificial Intelligence. 60:91-117
ISSN:	1573-7470 1012-2443
Popis:	The hybrid search algorithm for constraint satisfaction problems described here first uses local search to detect crucial substructures and then applies that knowledge to solve the problem. This paper shows the difficulties encountered by traditional and state-of-the-art learning heuristics when these substructures are overlooked. It introduces a new algorithm, Foretell, to detect dense and tight substructures called clusters with local search. It also develops two ways to use clusters during global search: one supports variable-ordering heuristics and the other makes inferences adapted to them. Together they improve performance on both benchmark and real-world problems.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::0d6a401679ddc1f40ea304dec25a2dc0 https://doi.org/10.1007/s10472-010-9212-z Zobrazit plný text záznamu Full text from SpringerLink