Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Expected-Case Analysis for Delayed Filtering
verfasst von : Irit Katriel
Erschienen in: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
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
One way to address the tradeoff between the efficiency and the effectiveness of filtering algorithms for global constraints is as follows: Instead of compromising on the level of consistency, compromise on the frequency at which arc consistency is enforced during the search. In this paper, a method is suggested to determine a reasonable filtering frequency for a given constraint.
For dense instances of
AllDifferent
and its generalization, the
Global Cardinality Constraint
, let
n
and
m
be, respectively, the number of nodes and edges in the variable-value graph. Under the assumption that propagation is random (i.e., each edge removed from the variable-value graph is selected at random), it is shown that recomputing arc consistency only after Θ(
m
/
n
) edges were removed results in a speedup while, in the expected sense, filtering effectiveness is comparable to that of enforcing arc consistency at each search step.