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

How can we read .doc document in asp.net, How can I read .doc document in A...

How can I read .doc document in ASP.Net? You can read from a text file like this.   Private void Button12_Click(object sender, System.EventArgs e) { string path="C:

Explain the significance of encryption, Problem: (i) What are the main...

Problem: (i) What are the main threats that an organisation holding sensitive data, such as Public Data, on computer storage must guard against? (ii) To protect such data,

Why SS7 protocol is use, SS7 Protocol uses: (A) Out of band signalling...

SS7 Protocol uses: (A) Out of band signalling. (B) Associated signalling. (C) Speech control signalling. (D) No signalling. Ans: SS7 Protocol uses Out of

Special theory of relativty, michelson-morley experiment-motivation and exp...

michelson-morley experiment-motivation and experimental setup

Define asynchronous bus, Define asynchronous bus. Asynchronous buses ar...

Define asynchronous bus. Asynchronous buses are the ones in which every item being transferred is accompanied by a control signal that shows its presence to the destination uni

What is phase encoding, What is phase encoding or Manchestor encoding? ...

What is phase encoding or Manchestor encoding?  It is the method for combining clock information with data. It is a scheme in which alters in magnetization occur for each data

Interconnection network in-array processing, Interconnection Network (IN): ...

Interconnection Network (IN):  IN performs data exchange between the PEs, manipulation functions and data routing. This IN is under the control of CU.

What is the network service access policy, What is the Network Service Acce...

What is the Network Service Access Policy A high-level, issue-specific policy which defines those services that are allowed or denied from the restricted network. It also co

Determine the synchronization of bits, Determine the synchronization of bit...

Determine the synchronization of bits The synchronization provided by use of start and stop bits, an extra bit known as a parity bit may optionally be transmitted along with th

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