<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>2.4 Interval and Domain Propagation</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node5.html#section.constraints.spaces"><< Prev</A></TD><TD><A href="node2.html">- Up -</A></TD><TD><A href="node7.html#section.constraints.incomplete">Next >></A></TD></TR></TABLE><DIV id="section.constraints.intdom"><H2><A name="section.constraints.intdom">2.4 Interval and Domain Propagation</A></H2><P>There are two established schemes for the operational semantics of a propagator. <A name="label32"></A><EM>Domain propagation</EM> narrows the domains of the variables as much as possible; <A name="label33"></A><EM>interval propagation</EM> only narrows the bounds of a domain. </P><P>Consider a propagator for the constraint </P><BLOCKQUOTE><P><IMG alt="{2\cdot X}=Y" src="latex49.png"></P></BLOCKQUOTE><P> over a constraint store </P><BLOCKQUOTE><P><IMG alt="X\in1\#10
\qquad
Y\in1\#7" src="latex50.png"></P></BLOCKQUOTE><P> Under domain propagation, the propagator can narrow the domains to </P><BLOCKQUOTE><P><IMG alt="X\in1\#3
\qquad
Y\in\{2,4,6\}" src="latex51.png"></P></BLOCKQUOTE><P> Under interval propagation, the propagator can narrow only the domain bounds, which yields </P><BLOCKQUOTE><P><IMG alt="X\in1\#3
\qquad
Y\in2\#6" src="latex52.png"></P></BLOCKQUOTE><P> </P><P>In practice, interval propagation is usually preferable over domain propagation because of its lower computational costs. We will see later that Oz offers for some constraints two propagators, one for interval and one for domain propagation. </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node5.html#section.constraints.spaces"><< Prev</A></TD><TD><A href="node2.html">- Up -</A></TD><TD><A href="node7.html#section.constraints.incomplete">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~schulte/">Christian Schulte</A> and <A href="http://www.ps.uni-sb.de/~smolka/">Gert Smolka</A><BR><SPAN class="version">Version 1.4.0 (20090610)</SPAN></ADDRESS></BODY></HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bd5c3d824c3db63ffd9226c15941e6ad
>
files
>
1231
