Arc consistency, Computer Engineering

Assignment Help:

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.


Related Discussions:- Arc consistency

What is assembly language, What is assembly language? Assembly languag...

What is assembly language? Assembly language : It is a family of low-level language for microprocessors, programming computers, microcontrollers etc. All are implement a symbo

Define processor clock, Define processor clock. Processor clock is expl...

Define processor clock. Processor clock is explained as the time periods in which all operations and data transfer within the processor take place.

#microprocessor, Program to transfer 10 byte of data from DMS to EMS using ...

Program to transfer 10 byte of data from DMS to EMS using 8086 instructions

Factor causing parallel overheads, Performance metrics aren't able to attai...

Performance metrics aren't able to attain a linear curve in comparison to increase in number of processors in parallel computer. The main reason for above situation is presence of

C LANGUAGE PROGRAMME, find a c program to find the area under the curve y=f...

find a c program to find the area under the curve y=f(x) between x=a and x=b,intregrate y=f(x)between the limits of a and b.the area under a curve between two points can be found b

Arrays, how to calculate students''s averange test scores

how to calculate students''s averange test scores

Jsbjj, what are the output deice

what are the output deice

What is double data rate sdram, What is double data rate SDRAM?  Double...

What is double data rate SDRAM?  Double data rates SDRAM are those which can transfer data on both edges of the clock and their bandwidth is fundamentally doubled for long burs

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd