Sophie

Sophie

distrib > Mandriva > 2010.0 > i586 > media > contrib-release > by-pkgid > bd5c3d824c3db63ffd9226c15941e6ad > files > 1188

mozart-1.4.0-1mdv2010.0.i586.rpm

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>3.3 The Explorer</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="node15.html#section.problem.money">&lt;&lt; Prev</A></TD><TD><A href="node13.html">- Up -</A></TD><TD><A href="node17.html#section.problem.primitives">Next &gt;&gt;</A></TD></TR></TABLE><DIV id="section.problem.explorer"><H2><A name="section.problem.explorer">3.3 The Explorer</A></H2><P>The Explorer is a graphical tool of the Mozart programming environment. It can run scripts and display the explored search trees. It can also display the information in the constraint stores associated with the nodes of the search tree. </P><P>The statement </P><DL class="anonymous"><DD class="code"><CODE>{ExploreAll&nbsp;Money}</CODE></DD></DL><P> tells the Explorer to run the script <CODE>Money</CODE> and explore the entire search tree. The Explorer will pop up a window and display the explored nodes of the search tree (see left part of <A href="node16.html#figconozsolver">Figure&nbsp;3.3</A>). Choice nodes appear as blue circles, failure nodes as red boxes, and solution nodes as green diamonds. Fully explored subtrees not containing solution nodes are collapsed into a single red triangle. </P><P></P><DIV id="figconozsolver"><HR><P><A name="figconozsolver"></A></P><TABLE align="center" class="dyptic" id="fig.conozsolver.table"><TR valign="top"><TD><P></P><DIV align="center"><IMG alt="" src="explorer-a.gif" id="pic.explorer-a"></DIV><P></P></TD><TD><P></P><DIV align="center"><IMG alt="" src="explorer-b.gif" id="pic.explorer-b"></DIV><P></P></TD></TR></TABLE><P class="caption"><STRONG>Figure&nbsp;3.3:</STRONG> The Explorer with the search tree of <CODE>Money</CODE>.</P><HR></DIV><P> </P><P>You can select any node of the displayed search tree by clicking it with the left mouse button. Select the red triangle and type the command <KBD>h</KBD> (hide/unhide). This will replace the triangle with the actual nodes of the tree (see right part of <A href="node16.html#figconozsolver">Figure&nbsp;3.3</A>). You now see the full search tree of <CODE>Money</CODE>, which consists of three choice nodes, three failure nodes, and one solution node. Typing the command <KBD>h</KBD> once more will switch back to the compact representation of the failed subtree. </P><P class="margin">double clicking nodes</P><P> Next, double click the green solution node with the left mouse button.</P><P>This will display the unique solution </P><BLOCKQUOTE class="code"><CODE>sol(d:7&nbsp;e:5&nbsp;m:1&nbsp;n:6&nbsp;o:0&nbsp;r:8&nbsp;s:9&nbsp;y:2)</CODE></BLOCKQUOTE><P> of the Money Puzzle in the Browser. You can also double click a blue choice node. This will display the information about the solution that was accumulated in the constraint store before the node was distributed. Double clicking the top node of the tree, for instance, will display </P><BLOCKQUOTE class="code"><CODE>sol(d:_[2<SPAN class="keyword">#</SPAN>8]&nbsp;&nbsp;e:_[4<SPAN class="keyword">#</SPAN>7]&nbsp;&nbsp;m:1&nbsp;&nbsp;n:_[5<SPAN class="keyword">#</SPAN>8]&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;o:0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r:_[2<SPAN class="keyword">#</SPAN>8]&nbsp;&nbsp;s:9&nbsp;&nbsp;y:_[2<SPAN class="keyword">#</SPAN>8])</CODE></BLOCKQUOTE><P> in the Browser. This way, the Explorer and the Browser can display the annotated search tree shown in <A href="node15.html#figconmoneytree">Figure&nbsp;3.2</A>. </P><P class="margin">open and closed choice nodes</P><P> The statement </P><DL class="anonymous"><DD class="code"><CODE>{ExploreOne&nbsp;Money}</CODE></DD></DL><P> tells the Explorer to run the script <CODE>Money</CODE> until the first solution is found. This time the Explorer will show a partial search tree that contains the solution node in the rightmost position, and also contains an open choice node. An <A name="label48"></A><EM>open choice node</EM> is a choice node for which not all direct descendents have been explored yet. A <A name="label49"></A><EM>closed choice node</EM> is a choice node for which all direct descendents have been explored already. While closed choice nodes are displayed in dark blue, open choice nodes are displayed in light blue. Not yet explored descendents of an open choice node are not displayed. </P><P>To check whether there are further solutions, you can resume the search process by selecting the root node and typing the command <KBD>n</KBD> (next). This will resume the search until either the next solution is found or all nodes of the search tree are explored. </P><P class="margin">stopping exploration</P><P> You can stop the exploring Explorer at any time by typing the command <KBD>C-g</KBD>. </P><P class="margin">resuming exploration</P><P> You can resume the exploration of a partial search tree by selecting any choice node and typing the command <KBD>n</KBD> or <KBD>a</KBD>. The command <KBD>n</KBD> (next) will resume the exploration of the selected subtree until a further solution is found or the subtree is fully explored. The command <KBD>a</KBD> (all) will resume the exploration of the selected subtree until it is fully explored. </P><P class="margin">resetting the Explorer</P><P> The command <KBD>C-r</KBD> will reset the Explorer and show only the root node of the search tree. By double clicking you can see in the Browser what is known about the solution before the first distribution step. You can request the exploration of the seach tree by typing <KBD>n</KBD> or <KBD>a</KBD>. </P><P class="margin">hand-guided exploration</P><P> You can guide the search of the Explorer by hand. Reset the Explorer by typing <KBD>C-r</KBD>. This will select the root node, which is an open choice node. Now type the command <KBD>o</KBD> (one) to compute the first descendent of the root. Select the root once more and type <KBD>o</KBD> again. This will compute the second and final descendent of the root. Note that the root has now changed from light blue indicating an open choice node to dark blue indicating a closed choice node. </P><P class="margin">zooming the search tree</P><P> The right vertical scroll bar of the Explorer's window zooms the size of the displayed search tree. You can zoom the tree to fit the size of the window by clicking the zoom bar with the right mouse button.</P><P></P><DIV class="exercise" id="problem.ex.a"><P><B>Exercise&nbsp;3.1</B> (<A href="answers.html#label191">See solution</A>)</P><BLOCKQUOTE><P>With the Explorer it is easy to observe the effect of different distribution strategies. Replace the first-fail distribution strategy in <CODE>Money</CODE> with the naive strategy </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>distribute&nbsp;naive&nbsp;Root}</CODE></BLOCKQUOTE><P> which distributes on the leftmost undetermined variable and its least possible value. Draw the new search tree with the Explorer and observe that it is twice as large as the tree obtained with first-fail distribution.</P></BLOCKQUOTE></DIV><DIV class="exercise" id="problem.ex.b"><P><B>Exercise&nbsp;3.2</B> (<A href="answers.html#label190">See solution</A>)</P><BLOCKQUOTE><P>Write a script that finds distinct digits for the letters <IMG alt="A" src="latex98.png">, <IMG alt="B" src="latex39.png">, <IMG alt="D" src="latex1.png">, <IMG alt="E" src="latex2.png">, <IMG alt="G" src="latex99.png">, <IMG alt="L" src="latex100.png">, <IMG alt="N" src="latex4.png">, <IMG alt="O" src="latex5.png">, <IMG alt="R" src="latex6.png">, and <IMG alt="T" src="latex101.png"> such that the equation </P><BLOCKQUOTE><P><IMG alt="DONALD+GERALD=ROBERT" src="latex102.png"></P></BLOCKQUOTE><P> holds without leading zeros. Run the script with the Explorer and study the search tree. Try both first-fail and naive distribution. Observe that first-fail distribution yields a search tree that is by one order of magnitude smaller than the search tree obtained with naive distribution.</P></BLOCKQUOTE></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node15.html#section.problem.money">&lt;&lt; Prev</A></TD><TD><A href="node13.html">- Up -</A></TD><TD><A href="node17.html#section.problem.primitives">Next &gt;&gt;</A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~schulte/">Christian&nbsp;Schulte</A> and&nbsp;<A href="http://www.ps.uni-sb.de/~smolka/">Gert&nbsp;Smolka</A><BR><SPAN class="version">Version 1.4.0 (20090610)</SPAN></ADDRESS></BODY></HTML>