Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
AND/OR Search Spaces and the Semantic Width of Constraint Networks
verfasst von : Robert Mateescu, Rina Dechter
Erschienen in: Principles and Practice of Constraint Programming - CP 2005
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
The primary contribution of this paper consists in using the
AND/OR search
paradigm [1,2] to define the new concept of
semantic width
of a constraint network. The well known parameter
tree-width
is graph based, and cannot capture context sensitive information. This often results in a very loose upper bound on the actual complexity of the problem. A typical example is the compact result of a compilation schemes such as
ordered binary decision diagram
(OBDD), in spite of a large tree-width (and path-width). The semantic width is based on the notion of equivalent constraint networks. The idea is to capture the intrinsic hardness of a problem by the smallest width equivalent network.