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 shadow mask, Q. What is Shadow Mask? Shadow Mask is a metal she...

Q. What is Shadow Mask? Shadow Mask is a metal sheet that has fine perforations (holes) in it and is situated a short distance before phosphor coated screen. The Phosphor dots

Branding choices, Develop a web traffic plan - suppose that there is no/min...

Develop a web traffic plan - suppose that there is no/minimal advertising budget so you will require to look at branding choices & site design, word-of-mouth and publicity as your

Weka uses a gaussian - radial basis function, A data set with 1000 rows is ...

A data set with 1000 rows is input to a neural network in Weka. The test option is set to 10-fold cross validation and the neural network option validationSetSize = 20%. How many r

Explain about fundamental nature of a computer, Q. Explain about fundamenta...

Q. Explain about fundamental nature of a Computer? The fundamental nature of a Computer is as an information transformer. So a computer should be able to take input and process

Boolean algebra, Boolean algebra. Boolean algebra mathematical method ...

Boolean algebra. Boolean algebra mathematical method based on human reasoning. In Boolean algebra only two states exist; true and false which are written as 1 (true) and 0 (fa

Advantage of doubly linked list over singly linked list, What is the advant...

What is the advantage of doubly linked list over singly linked list?       Ans: Benefits of the doubly linked list over singly linked list 1. A doubly linked list can be pas

How to calculate the logic circuit outputs, How to Calculate the Logic Circ...

How to Calculate the Logic Circuit Outputs? Once the Boolean expression for a circuit output has been acquired, the output logic level can be determined for any set of input le

Learn synchronization principles, Q. Learn synchronization principles? ...

Q. Learn synchronization principles? To learn synchronization subsequent dependencies are recognized:  i)  Data Dependency: These are RAW, WAW and WAR dependency.  ii) Co

Explain the term - instruction execution, Explain the term - Instruction ex...

Explain the term - Instruction execution We  know  that  the  fundamental  function  performed  by  a  computer  is  the  execution  of  program. The program that is to be exec

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