2005 | OriginalPaper | Buchkapitel
Probabilistic Arc Consistency
verfasst von : Deepak Mehta, M. R. C. van Dongen
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 two most popular algorithms for solving Constraint Satisfaction Problems are Forward Checking (
fc
) [1] and Maintaining Arc Consistency (
mac
) [2] M
ac
maintains full arc consistency while
fc
maintains a limited form of arc consistency during search. There is no single champion algorithm:
mac
is more efficient on sparse problems which are tightly constrained but
fc
has an increasing advantage as problems become dense and constraints loose. Ideally a good search algorithm should find the right balance —for any problem— between visiting fewer nodes in the search tree and reducing the work that is required to establish local consistency. In order to do so, we maintain
probabilistic arc consistency
during search. The idea is to assume that a support exists and skip the process of seeking a support if the probability of having some support for a value is at least equal to some, carefully chosen, stipulated threshold.
Arc consistency involves revisions of domains, which require support checks to remove unsupported values. In many revisions,
some
or
all
values find some support. If we can predict the existence of a support then a considerable amount of work can be saved. In order to do so, we propose the notions of a
Probabilistic Support Condition
(
psc
) and
Probabilistic Revision Condition
(
prc
). If
psc
holds then the probability of having some support for a value is at least equal to the threshold and the process of seeking a support is skipped. If
prc
holds then for each value the probability of having some support is at least equal to the threshold and the corresponding revision is skipped.