# Foundations of Constraint Processing

Yüklə 256 Kb.
 tarix 28.06.2018 ölçüsü 256 Kb. #52237

• ## Context

• Finite domains
• Binary constraints

• Chapter 6 of Tsang’s book (web accessible)

• Dual viewpoint heuristics for binary Constraint Satisfaction Problems [Geelen, ECAI 92]
• In my experience the most powerful, but also the most costly (require lots of constraint checks)

• ## Problem:

• How to guess whether a path is correct?

• choose the ordering that reduces the branching factor, the enemy of search..

• ## In general:

• Cheap and effective
• Suitable for both static and dynamic ordering

• ## Do while there are nodes left in the graph

• Set k  (k+1)
• Do While there are nodes not connected to more than k others
• Remove such nodes from the graph, along with any edges connected to them

• ## Is there an ordering of a given bandwidth k?

• O(nk+1), i.e. polynomial

• ## How

• Static variable, value ordering
• Dynamic variable (static value)
• Dynamic variable, dynamic value (dynamic vvp)
• ## When

• Finding one solution
• Finding all solutions

• ## Static

• Sort all variables, at pre-processing
• Based on:
• Initial domain (for LD, ddr, etc.)
• All neighbors of a variable (for deg, ddr, etc.)
• ## Dynamic

• Select one variable, during search
• Based on:
• Current domain (for LD, ddr, etc.)
• All un-instantiated neighbors of a variable (for deg, ddr, etc.)
• Exploit the domino effect.
• When the domain of any future variable has a single value, instantiate this variable first.

• ## The benefits (if any) and implications of 2-way branching versus k-way branching are not fully studied yet

Kataloq: ~choueiry

Yüklə 256 Kb.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2023
rəhbərliyinə müraciət

Ana səhifə