Arc consistency, Computer Engineering

Arc Consistency:

There have been many advances in how constraint solvers search for solutions (remember this means an assignment of a value to each variable in such a way thatno constraint is broken). We look first at a pre-processing step which can greatly improve efficiency by pruning the search space, namely arc-consistency. Following this, we'll look at two search methods, backtracking and forward checking which keep assigning values to variables until a solution is found. Finally, we'll look at some heuristics for improving the efficiency of the solver, namely how to order the choosing of the variables, and how to order the assigning of the values to variables. 

The pre-processing routine for bianry constraints known as  arc-consistency involves calling a pair (xi, xj) an arc and noting that this is an ordered pair, i.e., it is not the same as (xj, xi). Each arc is associated with a single constraint Cij, which constrains variables xi  and xj. We say that the arc (xi, xj) is  consistent  if, for all values a in Di, there is a value b in Dj  such that the assignment xi=a and xj=b satisfies constraint Cij. Note that (xi, xj) being consistent doesn't necessarily mean that (xj,xi) is also consistent. To use this in a pre-processing way, we take every pair of variables and make it arc-consistent. That is, we take each pair (xi,xj) and remove variables from Di  which make it inconsistent, until it becomes consistent. This effectively removes values from the domain of variables, hence prunes the search space and makes it likely that the solver will succeed (or fail to find a solution) more quickly.

Posted Date: 1/11/2013 7:35:43 AM | Location : United States







Related Discussions:- Arc consistency, Assignment Help, Ask Question on Arc consistency, Get Answer, Expert's Help, Arc consistency Discussions

Write discussion on Arc consistency
Your posts are moderated
Related Questions
Q. Explain Random-access Semiconductor Memories Q. What is Basic memory cell? Explain Two Dimension Memory Organization with diagram.

Main problems with evaluation functions: Superlatively, evaluation functions should be quick calculates. Wherever is chance they take a long time to estimate, so after then le

A computer system provides protection using the Bell-LaPadula policy. How would a virus spread if A) the virus were placed on the system at system low (the compartment that all o

Computer Memories Computer memories are either external or internal. Internal memories are either RAM (random access memory) or ROM (read only memory). External memories can t

Define the term- Analysis The analysis involves some or all of the following stages: Fact finding - this is usually done in four ways. Understanding the current syst

How can you provide an alternating color scheme in a Repeater control?  AlternatingItemTemplate Like the ItemTemplate element, but rendered for every otherrow (alternating item

Illustrate the Full form of OOA OOA views the world as objects consist of data structures and events that trigger operations and behaviours, for object behaviour changes. The b

Handlers Classification In 1977, Wolfgang Handler suggested a complex notation for representing the pipelining and parallelism of computers. Handler's categorization addresses

Objects, messages, class, inheritance and polymorphism are the major concepts of object orientation.

What is Organizational Structure? A business organization may be structured in many dissimilar ways, depending upon the environment within which it handles.  There is always