/usr/share/mozart/doc/fdt/node32.html is in mozart-doc 1.4.0-8ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>7.2 Example: Pythagoras</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="node31.html#section.propagators.fractions"><< Prev</A></TD><TD><A href="node30.html">- Up -</A></TD><TD><A href="node33.html#section.propagators.squares">Next >></A></TD></TR></TABLE><DIV id="section.propagators.pythagoras"><H2><A name="section.propagators.pythagoras">7.2 Example: Pythagoras</A></H2><P>Not all propagators exploit coreferences in products (e.g. <IMG alt="x\cdot x + y\cdot y = z\cdot
z" src="latex143.png">). For the example of this section it will be essential to exploit such coreferences, and you will learn how to do it. </P><P>The example also illustrates the case where a propagator for a redundant constraint improves the performance of a script by decreasing the number of necessary propagation steps, but without significantly changing the search tree. </P><DIV class="unnumbered"><H3><A name="label92">Problem Specification</A></H3><P>How many triples <IMG alt="(A,B,C)" src="latex144.png"> exist such that\ <IMG alt="A^2+B^2=C^2" src="latex145.png"> and <IMG alt="A\le B\le C\le 1000" src="latex146.png">? </P></DIV><DIV class="unnumbered"><H3><A name="label93">Model</A></H3><P>The model has three variables <IMG alt="A" src="latex98.png">, <IMG alt="B" src="latex39.png">, and <IMG alt="C" src="latex31.png">. Each variable is constrained to the finite domain <IMG alt="1\#1000" src="latex147.png">. The model imposes the constraints <IMG alt="A^2+B^2=C^2" src="latex145.png"> and <IMG alt="A\le B\le C" src="latex148.png">. </P><P>The script will also create a propagator for the redundant constraint <IMG alt="2\cdot B^2\ge C^2" src="latex149.png">. </P></DIV><DIV class="unnumbered"><H3><A name="label94">Distribution Strategy</A></H3><P>We distribute on the variables <IMG alt="A" src="latex98.png">, <IMG alt="B" src="latex39.png">, <IMG alt="C" src="latex31.png"> using the standard first-fail strategy.</P><P> </P><DIV class="figure" id="progpythagoras"><HR><P><A name="progpythagoras"></A></P><P></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Square</SPAN> X S}<BR> {FD<SPAN class="keyword">.</SPAN>times X X S}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P> </P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Pythagoras</SPAN> Root}<BR> [A B C] = Root<BR> AA BB CC<BR><SPAN class="keyword">in</SPAN> <BR> Root <SPAN class="keyword">:::</SPAN> 1<SPAN class="keyword">#</SPAN>1000<BR> AA = {Square A}<BR> BB = {Square B}<BR> CC = {Square C}<BR> AA <SPAN class="keyword">+</SPAN> BB <SPAN class="keyword">=:</SPAN> CC<BR> A <SPAN class="keyword">=<:</SPAN> B<BR> B <SPAN class="keyword">=<:</SPAN> C<BR> 2<SPAN class="keyword">*</SPAN>BB <SPAN class="keyword">>=:</SPAN> CC % <SPAN class="comment">redundant constraint<BR></SPAN> {FD<SPAN class="keyword">.</SPAN>distribute ff Root}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P></P><P class="caption"><STRONG>Figure 7.2:</STRONG> A script that enumerates Pythagoras triples.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label95">Script</A></H3><P>Given the script in <A href="node32.html#progpythagoras">Figure 7.2</A>, we can compute the number of different triples with the statement </P><DL class="anonymous"><DD class="code"><CODE>{Browse {Length {SearchAll Pythagoras}}}</CODE></DD></DL><P> The script introduces a defined constraint </P><BLOCKQUOTE class="code"><CODE>{Square X S}</CODE></BLOCKQUOTE><P> saying that <CODE>S</CODE> is the square of <CODE>X</CODE>. This constraint is implemented with a propagator provided by </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>times X X S}</CODE></BLOCKQUOTE><P> This propagator will start propagating as soon as the store constrains <CODE>X</CODE> to a finite domain. This in contrast to the propagator created by <CODE>X<SPAN class="keyword">*</SPAN>X<SPAN class="keyword">=:</SPAN>S</CODE>, which will start work only after both <CODE>X</CODE> and <CODE>S</CODE> are constrained to finite domains in the constraint store. To define <CODE>Square</CODE> with this constraint, we would have to write </P><BLOCKQUOTE class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Square</SPAN> X S}<BR> {FD<SPAN class="keyword">.</SPAN>decl S}<BR> X<SPAN class="keyword">*</SPAN>X <SPAN class="keyword">=:</SPAN> S<BR><SPAN class="keyword">end</SPAN></CODE></BLOCKQUOTE><P></P><P>The propagator for the redundant constraint does not significantly reduce the size of the search tree. However, it reduces the number of propagation steps from about 1000000 to about 500000, which makes computation twice as fast.</P><DIV class="apropos"><P class="margin">statistics</P><P> To find out about this, pop up the <A href="../panel/index.html">Oz Panel</A> and reset the statistics. Also switch on the status message feature and pop up the emulator buffer. Now enter the statement </P><BLOCKQUOTE class="code"><CODE>{Browse {Length {SearchAll Pythagoras}}}</CODE></BLOCKQUOTE><P> and print the statistics after the execution of the statement has finished. This will show something like </P><BLOCKQUOTE class="code"><CODE>solutions: 881 Variables created: 3<BR>clones: 1488 Propagators created: 7<BR>failures: 608 Propagator invocations: 490299</CODE></BLOCKQUOTE><P> in the emulator buffer. Now remove the propagator for the redundant constraint from the definition of the script, redefine it, reset the statistics, run the statement, and print the statistics. This time you will see something like </P><BLOCKQUOTE class="code"><CODE>solutions: 881 Variables created: 3<BR>clones: 1878 Propagators created: 6<BR>failures: 998 Propagator invocations: 1190397</CODE></BLOCKQUOTE><P></P></DIV><P>If we drop the redundant constraint, it seems sensible to not have separate propagators for the squares but simply have one propagator created with </P><BLOCKQUOTE class="code"><CODE>A<SPAN class="keyword">*</SPAN>A <SPAN class="keyword">+</SPAN> B<SPAN class="keyword">*</SPAN>B <SPAN class="keyword">=:</SPAN> C<SPAN class="keyword">*</SPAN>C</CODE></BLOCKQUOTE><P> Unfortunately, this will dramatically increase the size of the search tree. The reason for this increase is the fact that the created propagator does not realize the coreferences in the constraint it implements, that is, it treats the two occurrences of <CODE>A</CODE>, say, as if they were independent variables.</P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node31.html#section.propagators.fractions"><< Prev</A></TD><TD><A href="node30.html">- Up -</A></TD><TD><A href="node33.html#section.propagators.squares">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 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|