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

Explain the structure of virtual enterprise, Explain the Structure of Virtu...

Explain the Structure of Virtual Enterprise. The virtual enterprise can be a suitable structure to explore the emerging opportunities for forming value in the information socie

what respects the advance builds, Describe your choice specifically and fu...

Describe your choice specifically and fully, explaining and discussing at length in what respects the advance builds upon or departs from present technology or practice and the sev

How the simulation is done, How the simulation is done Data is entered ...

How the simulation is done Data is entered into the computer and simulation is run. The below scenarios may be tried out: -  Timing of lights varied to see how traffic flow

ERP, ERP usage in real world

ERP usage in real world

Define programmed i/o, Define Programmed I/O. It is the result of input...

Define Programmed I/O. It is the result of input and output instructions written in the computer program. Every data item transfer is initiated by an instruction in the program

Number of addresses in an instruction, Generally the Instruction Set Archit...

Generally the Instruction Set Architecture (ISA) of a processor can be distinguished using five categories:  Operand Storage in the CPU - Where are the operands kept other t

Name the variable types of c, C provides a wide range of variable types. ...

C provides a wide range of variable types. Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

Explain the importance of search engines, Explain the importance of Search ...

Explain the importance of Search Engines The most effective way of finding information on the internet is to use a search engine. Though, it's just as easy to use these ineffic

Define usb, Define USB. The Universal Serial Bus(USB) is an industry st...

Define USB. The Universal Serial Bus(USB) is an industry standard developed to give two speed of operation known as low-speed and full-speed. They provide simple, low cost and

Explain structure of control unit, Q. Explain Structure of Control Unit? ...

Q. Explain Structure of Control Unit? A control unit has a set of input values on the foundation of which it produces an output control signal which in turn performs micro-ope

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