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
Explain Gray Code Ans. Gray Code 1.  Extremely useful code. Also termed as reflected code. 2.  All gray code is different from the preceding and succeeding codes thr

Hard Disk Technology: Figure of a computer hard disk drive           HDDs record data by magnetizing ferromagnetic material directionally, to represent

application of de moiver theorem in software engineering

#write a program to find the area under the curve y=f(x) between x =a and x=b integrate the area between a and b by c programming

Probelm : a) What is the purpose of "Jumps" in the 8051 Microcontroller? Describe three types of "Jumps". b) What is the purpose of a "call"? c) Differentiate between ROM

Differentiate between QA and testing. - Quality Assurance is more a stop thing, ensuring quality in the company and thus the product rather than just testing the product for so

A breakthrough in the AI intelligence the development of natural interfaces is a prerequisite to the optimal use of computers by human beings. It incorporates: a. Natural La

Electronic typewriter : An electronic typewriter has a 'memory' or 'electronic brain' which enables it to recall the whole document at a time and type it automatically at the pres

Explain difference of Circuit switching versus Packet switching. Within circuit switching an end-to-end path is to be establishing before any data can be sent. Previously a con

Q. How will these instructions perform? Let's assume that above machine instructions are stored in three consecutive memory locations 1, 2 and 3 and PC contains a value (1) tha