/usr/share/mozart/doc/fst/node2.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>2 The Steiner Problem</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="node1.html#fset.tutorial.intro"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node3.html#fset.examples.hamming">Next >></A></TD></TR></TABLE><DIV id="fset.examples.steiner"><H1><A name="fset.examples.steiner">2 The Steiner Problem</A></H1><P class="margin">Problem Specification</P><P> The ternary Steiner problem of order <IMG alt="n" src="latex30.png"> asks for <IMG alt="n(n-1)/6" src="latex31.png"> sets <IMG alt="s_i
\subset \{1,\ldots,n\}" src="latex32.png"> with cardinality 3 such that every two of them share at most one element. The mathematical properties of the problem require that <IMG alt="n \bmod 6" src="latex33.png"> has to be either 1 or 3 <A href="bib.html#lindnerrosa:80">[LR80]</A>. </P><P class="margin">Model</P><P> We create a list <CODE>Ss</CODE> of <IMG alt="n(n-1)/6" src="latex31.png"> set variables and constrain every set to have a cardinality of 3 and to have an upper bound of <IMG alt="\{1,\ldots,n\}" src="latex34.png">. Further we require that the cardinality of the intersection of every two distinct sets in <CODE>Ss</CODE> must not exceed 1. </P><P class="margin">Distribution Strategy</P><P> Distribution simply takes the sets as they occur in <CODE>Ss</CODE> and adds resp. removes elements from them starting from the smallest element. </P><P class="margin">Solver</P><P> The solver is created by a function <CODE>Steiner</CODE> that takes the order of the Steiner problem as argument and checks if it is a valid order. In case it is valid it returns the actual solver with the list of solution sets as formal argument. </P><P>First, the list <CODE>Ss</CODE> is created and its elements' upper bounds and cardinalities are appropriately constrained. The nested loops built with <CODE>ForAllTail</CODE> and <CODE>ForAll</CODE> impose the constraint that every two sets share at most one element by stating that the cardinality of the intersection of two sets is in <IMG alt="\{0,1\}" src="latex35.png">. Distribution is straightforward and uses the provided library abstraction <CODE>FS<SPAN class="keyword">.</SPAN>distribute</CODE> for naive distribution.. </P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> <BR><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Steiner</SPAN> N}<BR> <SPAN class="keyword">case</SPAN> <BR> N <SPAN class="keyword">mod</SPAN> 6 <SPAN class="keyword">==</SPAN> 1 <SPAN class="keyword">orelse</SPAN> N <SPAN class="keyword">mod</SPAN> 6 <SPAN class="keyword">==</SPAN> 3 <BR> <SPAN class="keyword">then</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Ss} <BR> {FS<SPAN class="keyword">.</SPAN>var<SPAN class="keyword">.</SPAN>list<SPAN class="keyword">.</SPAN>upperBound (N<SPAN class="keyword">*</SPAN>(N<SPAN class="keyword">-</SPAN>1)) <SPAN class="keyword">div</SPAN> 6 [1<SPAN class="keyword">#</SPAN>N] Ss} <BR> {ForAll Ss <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> S} {FS<SPAN class="keyword">.</SPAN>card S 3} <SPAN class="keyword">end</SPAN>} <BR> <BR> {ForAllTail Ss <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> S1<SPAN class="keyword">|</SPAN>Sr} <BR> {ForAll Sr <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> S2} S3 <SPAN class="keyword">in</SPAN> <BR> S3 = {FS<SPAN class="keyword">.</SPAN>intersect S1 S2} <BR> {FS<SPAN class="keyword">.</SPAN>cardRange 0 1 S3} <BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN>}<BR> <BR> {FS<SPAN class="keyword">.</SPAN>distribute naive Ss}<BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">else</SPAN> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> _} <SPAN class="keyword">fail</SPAN> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR> <BR> <BR></PRE></BLOCKQUOTE><P> </P><P>Solving the Steiner problem of order 9 by invoking the Oz Explorer </P><BLOCKQUOTE class="code"><CODE>{ExploreOne {Steiner 9}}</CODE></BLOCKQUOTE><P> yields as solution </P><BLOCKQUOTE class="code"><CODE>[{1<SPAN class="keyword">#</SPAN>3}<SPAN class="keyword">#</SPAN>3 {1 4<SPAN class="keyword">#</SPAN>5}<SPAN class="keyword">#</SPAN>3 {1 6<SPAN class="keyword">#</SPAN>7}<SPAN class="keyword">#</SPAN>3 {1 8<SPAN class="keyword">#</SPAN>9}<SPAN class="keyword">#</SPAN>3 {2 4 6}<SPAN class="keyword">#</SPAN>3 {2 5 8}<SPAN class="keyword">#</SPAN>3 <BR> {2 7 9}<SPAN class="keyword">#</SPAN>3 {3<SPAN class="keyword">#</SPAN>4 9}<SPAN class="keyword">#</SPAN>3 {3 5 7}<SPAN class="keyword">#</SPAN>3 {3 6 8}<SPAN class="keyword">#</SPAN>3 {4 7<SPAN class="keyword">#</SPAN>8}<SPAN class="keyword">#</SPAN>3 {5<SPAN class="keyword">#</SPAN>6 9}<SPAN class="keyword">#</SPAN>3]<SPAN class="keyword">.</SPAN></CODE></BLOCKQUOTE><P> The search tree has depth 50, 4545 choice nodes, and 4521 failure nodes. </P><DIV align="center"><IMG alt="" src="fset_steiner_naive.gif" id="pic.fset_steiner_naive"></DIV><P> </P><P class="margin">Improving the Model</P><P> A promising way to improve the efficiency of a constraint model (where the corresponding problem does not have a unique solution) is to break symmetries and thus to improve constraint propagation. Breaking symmetries can be achieved by imposing an order, in our case, an order on the set variables in <CODE>Ss</CODE>. We can simply interpret every set as a number with three digits to the base <IMG alt="(n+1)" src="latex36.png">. A set with three elements <IMG alt="\{x_1,x_2,x_3\}" src="latex37.png"> can be mapped to an integer by <IMG alt="(n+1)^2x_1+(n+1)x_2+x_3" src="latex38.png">. </P><P class="margin">Extending the Solver</P><P> The finite set library provides <CODE>FS<SPAN class="keyword">.</SPAN>int<SPAN class="keyword">.</SPAN>match</CODE> to match the elements of a set <IMG alt="s" src="latex5.png"> with a fixed number of elements to a vector of size <IMG alt="\#s" src="latex39.png"> of finite domain variables. This library constraint in conjunction with <CODE>Map</CODE> is used to convert the list of sets <CODE>Ss</CODE> to a list of finite domain lists with 3 finite domains per list. Finally the order between adjacent sets is imposed by </P><BLOCKQUOTE class="code"><CODE>N1N1<SPAN class="keyword">*</SPAN>X1 <SPAN class="keyword">+</SPAN> N1<SPAN class="keyword">*</SPAN>X2 <SPAN class="keyword">+</SPAN> X3 <SPAN class="keyword"><:</SPAN> N1N1<SPAN class="keyword">*</SPAN>Y1<SPAN class="keyword">+</SPAN> N1<SPAN class="keyword">*</SPAN>Y2 <SPAN class="keyword">+</SPAN> Y3</CODE></BLOCKQUOTE><P> employing a <CODE>ForAllTail</CODE> loop. </P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">local</SPAN> <BR> N1 = N<SPAN class="keyword">+</SPAN>1 N1N1 = N1<SPAN class="keyword">*</SPAN>N1<BR><SPAN class="keyword">in</SPAN> <BR> {ForAllTail {Map Ss <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> S}<BR> {FD<SPAN class="keyword">.</SPAN>list 3 1<SPAN class="keyword">#</SPAN>N} = {FS<SPAN class="keyword">.</SPAN>int<SPAN class="keyword">.</SPAN>match S}<BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> T}<BR> <SPAN class="keyword">case</SPAN> T <SPAN class="keyword">of</SPAN> [X1 X2 X3]<SPAN class="keyword">|</SPAN>[Y1 Y2 Y3]<SPAN class="keyword">|</SPAN>_ <SPAN class="keyword">then</SPAN> <BR> N1N1<SPAN class="keyword">*</SPAN>X1 <SPAN class="keyword">+</SPAN> N1<SPAN class="keyword">*</SPAN>X2 <SPAN class="keyword">+</SPAN> X3 <SPAN class="keyword"><:</SPAN> N1N1<SPAN class="keyword">*</SPAN>Y1 <SPAN class="keyword">+</SPAN> N1<SPAN class="keyword">*</SPAN>Y2 <SPAN class="keyword">+</SPAN> Y3<BR> <SPAN class="keyword">else</SPAN> <SPAN class="keyword">skip</SPAN> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN>}<BR><SPAN class="keyword">end</SPAN> <BR> <BR></PRE></BLOCKQUOTE><P> This code is to be inserted right before the distribution. Solving the Steiner problem of order 9 results in the following search tree. </P><DIV align="center"><IMG alt="" src="fset_steiner_order.gif" id="pic.fset_steiner_order"></DIV><P> We see that the number of choice nodes decreases from 4545 to 565 and the number of failure nodes decreases from 4521 to 54. This reduction of the search space gives us a speed-up of about 7 and reduces the memory consumption by about 5.5. </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node1.html#fset.tutorial.intro"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node3.html#fset.examples.hamming">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~tmueller/">Tobias Müller</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|