Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Complexity Analysis of Heuristic CSP Search Algorithms
verfasst von : Igor Razgon
Erschienen in: Recent Advances in Constraints
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
CSP search algorithms are exponential in the worst-case. A trivial upper bound on the time complexity of CSP search algorithms is
O
*
(
d
n
), where
n
and
d
are the number of variables and the maximal domain size of the underlying CSP, respectively.
In this paper we show that a combination of heuristic methods of constraint solving can reduce the time complexity. In particular, we prove that the FC-CBJ algorithm combined with the fail-first variable ordering heuristic (FF) achieves time complexity of
O
*
((
d
– 1)
n
), where
n
and
d
are the number of variables and the maximal domain size of the given CSP, respectively. Furthermore, we show that the combination is essential because neither FC-CBJ alone nor FC with FF achieve the above complexity. The proposed results are interesting because they establish connection between theoretical and practical approaches to CSP research.