<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>4.2 Example: Family</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="node21.html#section.elimination.grocery"><< Prev</A></TD><TD><A href="node20.html">- Up -</A></TD><TD><A href="node23.html#section.elimination.zebra">Next >></A></TD></TR></TABLE><DIV id="section.elimination.family"><H2><A name="section.elimination.family">4.2 Example: Family</A></H2><P></P><DIV class="apropos"><P class="margin">defined constraints</P><P> This example illustrates the use of defined constraints. A <A name="label60"></A><EM>defined constraint</EM> is a procedure </P><BLOCKQUOTE class="code"><CODE>{DefinedConstraint X1 <SPAN class="keyword">...</SPAN> Xn}</CODE></BLOCKQUOTE><P> posting constraints on the variables <CODE>X1</CODE>, ... <CODE>Xn</CODE>. The reasons for introducing defined constraints are more or less the same as for introducing defined procedures in ordinary programming. </P></DIV><P>The script for the example will employ the procedures <CODE>FD<SPAN class="keyword">.</SPAN>sum</CODE>, <CODE>FD<SPAN class="keyword">.</SPAN>sumC</CODE>, and <CODE>FD<SPAN class="keyword">.</SPAN>sumCN</CODE>, which create propagators for linear and nonlinear summation constraints. </P><DIV class="unnumbered"><H3><A name="label61">Problem Specification</A></H3><P>Maria and Clara are both heads of households, and both families have three boys and three girls. Neither family includes any children closer in age than one year, and all children are under age 10. The youngest child in Maria's family is a girl, and Clara has just given birth to a little girl.</P><P> In each family, the sum of the ages of the boys equals the sum of the ages of the girls, and the sum of the squares of the ages of the boys equals the sum of the the squares of ages of the girls. The sum of the ages of all children is 60.</P><P>What are the ages of the children in each family? </P></DIV><DIV class="unnumbered"><H3><A name="label62">Model</A></H3><P>We model a family as a record </P><BLOCKQUOTE class="code"><CODE>Name(boys:[</CODE><I>B1</I><CODE> </CODE><I>B2</I><CODE> </CODE><I>B3</I><CODE>] girls:[</CODE><I>G1</I><CODE> </CODE><I>G2</I><CODE> </CODE><I>G3</I><CODE>])</CODE></BLOCKQUOTE><P> where the variables <I>B1</I>, <I>B2</I> and <I>B3</I> stand for the ages of the boys in descending order (i. e., <I>B3</I> is the age of the youngest boy in the family), and the variables <I>G1</I>, <I>G2</I> and <I>G3</I> stand for the ages of the girls, also in descending order. This representation of a family avoids possible symmetries. The constraints that must hold for a family <I>F</I> with name <I>N</I> will be posted by the defined constraint <CODE>{IsFamily </CODE><I>N</I><CODE> </CODE><I>F</I><CODE>}</CODE>. </P><P>A solution is a pair consisting of Maria's and Clara's family. </P></DIV><DIV class="unnumbered"><H3><A name="label63">Distribution Stratgey</A></H3><P>We distribute on the list of the ages of the children of the two families following a first-fail strategy. The strategy splits the domain of the selected variable and tries the lower part of the domain first. </P></DIV><DIV class="unnumbered"><H3><A name="label64">Script</A></H3><P></P><DIV id="progfamily"><HR><P><A name="progfamily"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Family</SPAN> Root}<BR> </CODE><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A href="node22.html#label66">Definition of IsFamily</A><SPAN class="chunkborder">></SPAN></SPAN><CODE> <BR> </CODE><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A href="node22.html#label65">Definition of AgeList</A><SPAN class="chunkborder">></SPAN></SPAN><CODE> <BR> Maria = {IsFamily maria}<BR> Clara = {IsFamily clara}<BR> AgeOfMariasYoungestGirl = {Nth Maria<SPAN class="keyword">.</SPAN>girls 3}<BR> AgeOfClarasYoungestGirl = {Nth Clara<SPAN class="keyword">.</SPAN>girls 3}<BR> Ages = {FoldR [Clara<SPAN class="keyword">.</SPAN>girls Clara<SPAN class="keyword">.</SPAN>boys Maria<SPAN class="keyword">.</SPAN>girls Maria<SPAN class="keyword">.</SPAN>boys] <BR> Append nil}<BR><SPAN class="keyword">in</SPAN> <BR> Root = Maria<SPAN class="keyword">#</SPAN>Clara<BR> {ForAll Maria<SPAN class="keyword">.</SPAN>boys <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> A} A <SPAN class="keyword">>:</SPAN> AgeOfMariasYoungestGirl <SPAN class="keyword">end</SPAN>}<BR> AgeOfClarasYoungestGirl = 0<BR> {FD<SPAN class="keyword">.</SPAN>sum Ages <SPAN class="string">'=:'</SPAN> 60}<BR> {FD<SPAN class="keyword">.</SPAN>distribute split Ages}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 4.2:</STRONG> A script for the Family Puzzle.</P><HR></DIV><P> </P><P>The script in <A href="node22.html#progfamily">Figure 4.2</A> introduces two defined constraints. The defined constraint </P><BLOCKQUOTE class="code"><I>F</I><CODE>={IsFamily </CODE><I>Name</I><CODE>}</CODE></BLOCKQUOTE><P> imposes constraints saying that <I>F</I> is the representation of a family with name <I>Name</I> (see <A href="node22.html#figure.elim.familydef">Figure 4.3</A>). The defined constraint </P><BLOCKQUOTE class="code"><I>L</I><CODE>={AgeList}</CODE></BLOCKQUOTE><P> imposes constraints saying that <I>L</I> is a list of three integers between <CODE>0</CODE> and <CODE>9</CODE> appearing in descending order (see <A href="node22.html#figure.elim.familydef">Figure 4.3</A>). </P><P></P><DIV id="figure.elim.familydef"><HR><P><A name="figure.elim.familydef"></A></P><P></P><DL><DT><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A name="label65">Definition of AgeList</A><SPAN class="chunkborder">>=</SPAN></SPAN></DT><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">AgeList</SPAN> L}<BR> {FD<SPAN class="keyword">.</SPAN>list 3 0<SPAN class="keyword">#</SPAN>9 L}<BR> {Nth L 1} <SPAN class="keyword">>:</SPAN> {Nth L 2}<BR> {Nth L 2} <SPAN class="keyword">>:</SPAN> {Nth L 3}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P> </P><DL><DT><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A name="label66">Definition of IsFamily</A><SPAN class="chunkborder">>=</SPAN></SPAN></DT><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">IsFamily</SPAN> Name}<BR> Coeffs = [1 1 1 <SPAN class="keyword">~</SPAN>1 <SPAN class="keyword">~</SPAN>1 <SPAN class="keyword">~</SPAN>1]<BR> BoysAges = {AgeList}<BR> GirlsAges = {AgeList}<BR> Ages = {Append BoysAges GirlsAges}<BR><SPAN class="keyword">in</SPAN> <BR> {FD<SPAN class="keyword">.</SPAN>distinct Ages}<BR> {FD<SPAN class="keyword">.</SPAN>sumC Coeffs Ages <SPAN class="string">'=:'</SPAN> 0}<BR> {FD<SPAN class="keyword">.</SPAN>sumCN Coeffs {Map Ages <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> A} [A A] <SPAN class="keyword">end</SPAN>} <SPAN class="string">'=:'</SPAN> 0}<BR> Name(boys:BoysAges girls:GirlsAges)<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P></P><P class="caption"><STRONG>Figure 4.3:</STRONG> Defined constraints for the Family Puzzle.</P><HR></DIV><P> </P><P>The statement </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>sumC Coeffs Ages <SPAN class="string">'=:'</SPAN> 0}</CODE></BLOCKQUOTE><P> creates a propagator for the constraint </P><BLOCKQUOTE><P><IMG alt="1\cdot B_1\;+\;1\cdot B_2\;+\;1\cdot B_3\;+\;(-1)\cdot G_1\;+\;
(-1)\cdot G_2\;+\;(-1)\cdot G_3\;=\;0" src="latex110.png"></P></BLOCKQUOTE><P></P><P>saying that the sum of the ages of the boys equals the sum of the ages of the girls. The statement </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>sumCN Coeffs {Map Ages <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> A} [A A] <SPAN class="keyword">end</SPAN>} <SPAN class="string">'=:'</SPAN> 0}</CODE></BLOCKQUOTE><P> creates a propagator for the constraint </P><BLOCKQUOTE><P><IMG alt="\begin{array}{c}
1\cdot B_1\cdot B_1\;+\;1\cdot B_2\cdot B_2\;+\;1\cdot
B_3\cdot B_3 \;+\;(-1)\cdot G_1\cdot G_1\;+\;
\hskip7mm
\\
(-1)\cdot G_2\cdot G_2\;+\;(-1)\cdot G_3\cdot G_3\;=\;0
\end{array}" src="latex111.png"></P></BLOCKQUOTE><P> saying that the sum of the squares of the ages of the boys equals the sum of the squares of the ages of the girls. The statement </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>sum Ages <SPAN class="string">'=:'</SPAN> 60}</CODE></BLOCKQUOTE><P> creates a propagator for the constraint saying that the sum of the ages of all kids equals <CODE>60</CODE>.</P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node21.html#section.elimination.grocery"><< Prev</A></TD><TD><A href="node20.html">- Up -</A></TD><TD><A href="node23.html#section.elimination.zebra">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
>
1195
