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 about FAT - Inode? Today modern PC comprises total capacity of nearly 40GB for storage of program and data Due to this huge capacity in place of having just one oper

Hypothesis ... since the Hebrew language is a Numerical language meaning that each letter in their alphabet has a numerical value. I believe, that the Hebrew-language based on a r

How does bus arbitration typically work? i.  A bus master waiting to use the bus asserts by  the bus request. ii.  A bus master cannot be the bus until it's request is grant

Vector Processing with Pipelining Because in vector processing vector instructions execute the similar computation on various data operands repeatedly, vector processing is the

Q. Illustrate Memory Read operation? Memory unit receives the address from a register known as the memory address register designated by MAR. Data is transferred to another re

The goal of this question is to create a program that takes as input two images that are related by a homography, and which "warps" the second image (piscine2.bmp) to align with th

Determine about the Locator Devices Mouse  A mouse is small hand-held box used to position the screen cursor. Wheels or rollers on the bottom of the mouse can be used to r

The only way to respond effectively to a design project is to first understand the topic well yourself. To do this you need to research the topic and ask yourself a series of quest


How to calculate the flowchart