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

Android projects, how should I do connectivity with google play for my andr...

how should I do connectivity with google play for my android GSM based project

Cso, why we don''t use register at the place of ram?

why we don''t use register at the place of ram?

Define parity bit and list its types, Define parity bit and List its types....

Define parity bit and List its types. The most common error detection code used is the parity bit. Parity bit is a extra bit contained with a binary message to make the total n

What are semaphores, What are semaphores? Semaphore : A semaphore is a...

What are semaphores? Semaphore : A semaphore is a synchronization tool which gives a general-purpose solution to controlling access to critical sections. It s an abstract data

Planning too much up front a mistake in an oosad, You can't plan only for t...

You can't plan only for the present phase of the project as your future activities are still coarse granular. To have good planning you require to have fine granularity w.r.t the t

What are the types of calendars in a single interface, What are the types o...

What are the types of calendars in a single interface? Member Event calendar helps users manage their personal time, Kept track of meetings with others, and so on. Tea

Health care professional, Overall, Mr. X is an intelligent and high-functio...

Overall, Mr. X is an intelligent and high-functioning man with good psychological, social, and occupational functioning. The test battery did not reveal any difficulties that warra

Which is valid syntax of the fork and join primitive, Which is valid syntax...

Which is valid syntax of the Fork and Join Primitive? Ans. A valid syntax of the Fork and Join Primitive is as given below: Fork Join

What is the purpose of iop, What is the purpose of IOP. The purpose of ...

What is the purpose of IOP. The purpose of IOP is to given an independent path way for transfer of information among external and internal memory.

What is the difference among a canvas and a scroll panel, Canvas is a compo...

Canvas is a component. ScrollPanel is a container. Canvas is a rectangular area where the application can draw or trap input events. ScrollPane executes horizontal and vertical scr

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