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

Identify the main enhancements brought along by tkip, Question: (a) Id...

Question: (a) Identify the four main enhancements brought along by TKIP on WPA to solve the problems in WEP. (b) The term WarDriving has been frequently used while talking

Explain about threads model - programming model, Q. Explain about Threads M...

Q. Explain about Threads Model - programming model? In this model a single process can have many as well as concurrent execution paths. The main program is planned to run by na

Computer grphics, Advantages of DDa algorithms for line drawimg

Advantages of DDa algorithms for line drawimg

Embedded, explain djnz instruction of intel 8051 microcontroler

explain djnz instruction of intel 8051 microcontroler

Explain characteristics of latch and flip-flop, Explain characteristics of ...

Explain characteristics of Latch and Flip-Flop. Latches are level-sensitive and transparent While the clock is high it passes input value to Output While the clock is l

Incorporating vbscript into htmlpage, To add scripts into your Web pages ta...

To add scripts into your Web pages tag is used. The tag signifies the start of the script section, whereas marks the end. An example of this is d

Classes, write a program to copt values of object without using copy constr...

write a program to copt values of object without using copy constructor or = operator

Integrating virtual memory, Integrating Virtual Memory, TLBs, and Caches - ...

Integrating Virtual Memory, TLBs, and Caches - computer architecture:   There are 3 types of misses: 1. a cache miss 2. TLB miss 3. a page fault 2 techniqu

Stata about the magnetic stripes, Stata about the Magnetic stripes  Th...

Stata about the Magnetic stripes  These comprise information/data stored on magnetic material often on the back of a credit/debit card; the information is automatically read b

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