6

In the Constraint Propagation in CSP, it is often stated that pre-processing can solve the whole problem, so no search is required at all. And the key idea is local consistency. What does this actually mean?

nbro
  • 39,006
  • 12
  • 98
  • 176
Lexi
  • 109
  • 7
  • 1
    Have a look at [https://en.wikipedia.org/wiki/Local_consistency](https://en.wikipedia.org/wiki/Local_consistency). – nbro May 02 '19 at 13:03
  • I think the consistency propagation method only works for 2-SAT problems, no? – PeaBrane Sep 06 '22 at 05:28

1 Answers1

0

If we can do some reduction in the search space using CSP (constraint propagation) we can drastically reduce the search space or sometimes completely avoid the need for a search by directly reaching the solutions (for e.g. with variables having their domains reduced to size one). It could also happen that we come to a point when a variable domain size becomes zero, in that case no solution exists, given the constraints, so no need for a search.

Constraint propagation basically involves the concept of enforcing local consistency (this is done by enforcing node-consistency, arc-consistency, path-consistency and also global constraints using Alldiif or Atmost).

The terms: nodes, arc, path, etc. basically reflects a CSP problem represented as a graph with nodes as the variables and the arcs/edges as constraints. The process is simply to remove values from the domains of the variables that are inconsistent. Algorithms such as AC-3, PC-2, etc. precisely are for these purposes.

MuneshSingh
  • 11
  • 3