<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD><TITLE>2.8 Distribution Strategies</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="node9.html#section.constraints.example"><< Prev</A></TD><TD><A href="node2.html">- Up -</A></TD><TD><A href="node11.html#section.constraints.order">Next >></A></TD></TR></TABLE><DIV id="section.constraints.distribution"><H2><A name="section.constraints.distribution">2.8 Distribution Strategies</A></H2><P>A <A name="label35"></A><EM>distributor</EM> is a computational agent implementing a <A name="label36"></A><EM>distribution strategy</EM>. If a thread creates a distributor, the thread is blocked until the distributor has done its job. If a distribution step is needed, the distributor becomes active and generates the constraint with which the space will be distributed. If there is more than one distributor in existence, one of them is chosen indeterministically whenever a distribution step is needed. </P><P>Usually, a distribution strategy is defined on a sequence <IMG alt="x_1,\ldots,x_n" src="latex87.png"> of variables. When a distribution step is necessary, the strategy selects a not yet determined variable in the sequence and distributes on this variable. </P><P class="margin">standard possibilities to distribute on a variable</P><P> There are a few standard possibilities to distribute on a variable <IMG alt="x" src="latex42.png">: </P><UL><LI><P>distribute with <IMG alt="x=l" src="latex88.png">, where <IMG alt="l" src="latex89.png"> is the least possible value for <IMG alt="x" src="latex42.png">.</P></LI><LI><P>distribute with <IMG alt="x=u" src="latex90.png">, where <IMG alt="u" src="latex91.png"> is the largest possible value for <IMG alt="x" src="latex42.png">.</P></LI><LI><P>distribute with <IMG alt="x=m" src="latex92.png">, where <IMG alt="m" src="latex93.png"> is a possible value for <IMG alt="x" src="latex42.png"> that is in the middle of the least and largest possible value for <IMG alt="x" src="latex42.png">.</P></LI><LI class="page" id="page.domainsplitting"><P>distribute with <IMG alt="x\le m" src="latex94.png">, where <IMG alt="m" src="latex93.png"> is a possible value for <IMG alt="x" src="latex42.png"> that is in the middle of the least and largest possible value for <IMG alt="x" src="latex42.png"> (so called <A name="label37"></A><EM>domain splitting</EM>).</P></LI></UL><P> </P><P class="margin">naive distribution</P><P> A <A name="label38"></A><EM>naive distribution strategy</EM> will select the leftmost undetermined variable in the sequence. </P><P class="margin">first-fail distribution</P><P> A <A name="label39"></A><EM>first-fail distribution strategy</EM> will select the leftmost undetermined variable in the sequence whose domain in the constraint store has minimal size. In other words, it will select the leftmost undetermined variable for which the number of different possible values is minimal.</P><P>For most problems, first-fail strategies yield much smaller search trees than naive strategies.</P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node9.html#section.constraints.example"><< Prev</A></TD><TD><A href="node2.html">- Up -</A></TD><TD><A href="node11.html#section.constraints.order">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
>
1182
