/usr/share/mozart/doc/fdt/node44.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 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>10.1 Example: Aligning for a Photo, Revisited</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="node43.html">- Up -</A></TD><TD><A href="node45.html#section.bab.warehouses">Next >></A></TD></TR></TABLE><DIV id="section.bab.align"><H2><A name="section.bab.align">10.1 Example: Aligning for a Photo, Revisited</A></H2><P>In <A href="node37.html#section.reified.photo">Section 8.2</A> we have searched for a solution of the alignment problem which satisfies the maximal number of preferences. To this aim we have introduced a variable which counts the number of satisfied preferences. By distributing this variable with its maximal value first, we have guaranteed that the first solution found is indeed the optimal one. </P><P>In this section we replace this ad-hoc approach by branch and bound. We first restate the script for the problem by omitting the distribution code for the variable summing up the satisfied preferences. The resulting script is shown in <A href="node44.html#progphotorevised">Figure 10.1</A>. </P><DIV id="progphotorevised"><HR><P><A name="progphotorevised"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">RevisedPhoto</SPAN> Root}<BR> Persons = [betty chris donald fred gary mary paul]<BR> Preferences = [betty<SPAN class="keyword">#</SPAN>gary betty<SPAN class="keyword">#</SPAN>mary chris<SPAN class="keyword">#</SPAN>betty chris<SPAN class="keyword">#</SPAN>gary<BR> fred<SPAN class="keyword">#</SPAN>mary fred<SPAN class="keyword">#</SPAN>donald paul<SPAN class="keyword">#</SPAN>fred paul<SPAN class="keyword">#</SPAN>donald]<BR> NbPersons = {Length Persons}<BR> Alignment = {FD<SPAN class="keyword">.</SPAN>record alignment Persons 1<SPAN class="keyword">#</SPAN>NbPersons}<BR> Satisfaction = {FD<SPAN class="keyword">.</SPAN>decl} <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Satisfied</SPAN> P<SPAN class="keyword">#</SPAN>Q S}<BR> {FD<SPAN class="keyword">.</SPAN>reified<SPAN class="keyword">.</SPAN>distance Alignment<SPAN class="keyword">.</SPAN>P Alignment<SPAN class="keyword">.</SPAN>Q <SPAN class="string">'=:'</SPAN> 1 S}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">in</SPAN> <BR> Root = r(satisfaction: Satisfaction<BR> alignment: Alignment)<BR> {FD<SPAN class="keyword">.</SPAN> distinct Alignment}<BR> {FD<SPAN class="keyword">.</SPAN>sum {Map Preferences Satisfied} <SPAN class="string">'=:'</SPAN> Satisfaction}<BR> Alignment<SPAN class="keyword">.</SPAN>fred <SPAN class="keyword"><:</SPAN> Alignment<SPAN class="keyword">.</SPAN>betty % <SPAN class="comment">breaking symmetries<BR></SPAN> {FD<SPAN class="keyword">.</SPAN>distribute split Alignment}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 10.1:</STRONG> The revised script for the Photo Puzzle.</P><HR></DIV><P> </P><P>Next we define an ordering procedure which states that the overall sum of satisfied preferences in an alternative solution must be strictly greater than the corresponding sum in a previous solution: </P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">PhotoOrder</SPAN> Old New}<BR> Old<SPAN class="keyword">.</SPAN>satisfaction <SPAN class="keyword"><:</SPAN> New<SPAN class="keyword">.</SPAN>satisfaction<BR><SPAN class="keyword">end</SPAN> </CODE></DD></DL><P> The optimal solution can be found with the statement </P><DL class="anonymous"><DD class="code"><CODE>{ExploreBest RevisedPhoto PhotoOrder}</CODE></DD></DL><P> We obtain the same solution as in <A href="node37.html#page.reified.photosol">*</A>. But now only 141 choice nodes are needed to find the optimal solution whereas 219 choice nodes were needed in <A href="node37.html#section.reified.photo">Section 8.2</A>. Furthermore, branch and bound allows us to prove in an efficient way that the last solution found is really the optimal one. The full search tree (including the proof of optimality) contains 169 choice nodes; still less than for the search for the best solution with the ad-hoc method. If we inspect the solutions, we observe that the first solution satisfies only a single preference. By imposition of the ordering procedure by the search engine, the next found solution must satisfy more preferences. Indeed, the second solution satisfies two preferences. Following this approach we finally arrive at the optimal solution with six satisfied preferences.</P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node43.html">- Up -</A></TD><TD><A href="node45.html#section.bab.warehouses">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>
|