<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>6.1 Example: Coloring a Map</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="node27.html">- Up -</A></TD><TD><A href="node29.html#section.minimizing.conference">Next >></A></TD></TR></TABLE><DIV id="section.minimizing.mapcolor"><H2><A name="section.minimizing.mapcolor">6.1 Example: Coloring a Map</A></H2><DIV class="unnumbered"><H3><A name="label79">Problem Specification</A></H3><P>Given a map showing the West European countries Netherlands, Belgium, France, Spain, Portugal, Germany, Luxemburg, Switzerland, Austria, and Italy, find a coloring such that neighboring countries have different color and a minimal number of colors is used. </P></DIV><DIV class="unnumbered"><H3><A name="label80">Model</A></H3><P>We have a variable <IMG alt="NbColors" src="latex130.png"> saying how many different colors we can use. Moreover, we have a variable for every country. For every pair <IMG alt="A" src="latex98.png">, <IMG alt="B" src="latex39.png"> of countries having a border in common we impose the constraint <IMG alt="A\neq B" src="latex131.png">. We represent colors as numbers. Hence we constrain all variables for countries to integers in <IMG alt="0\#{NbColors}" src="latex132.png">. </P></DIV><DIV class="unnumbered"><H3><A name="label81">Distribution Strategy</A></H3><P>We first distribute on <IMG alt="NbColors" src="latex130.png">, trying the numbers <IMG alt="0,1,2,\ldots" src="latex133.png"> in ascending order. After <IMG alt="NbColors" src="latex130.png"> is determined, we distribute on the variables for the countries using the usual first-fail strategy. </P><DIV id="progmapcoloring"><HR><P><A name="progmapcoloring"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">MapColoring</SPAN> Data}<BR> Countries = {Map Data <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> C<SPAN class="keyword">#</SPAN>_} C <SPAN class="keyword">end</SPAN>}<BR><SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Color}<BR> NbColors = {FD<SPAN class="keyword">.</SPAN>decl}<BR> <SPAN class="keyword">in</SPAN> <BR> {FD<SPAN class="keyword">.</SPAN>distribute naive [NbColors]}<BR> %% <SPAN class="comment">Color: Countries --> 1#NbColors<BR></SPAN> {FD<SPAN class="keyword">.</SPAN>record color Countries 1<SPAN class="keyword">#</SPAN>NbColors Color}<BR> {ForAll Data<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> A<SPAN class="keyword">#</SPAN>Bs}<BR> {ForAll Bs <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> B} Color<SPAN class="keyword">.</SPAN>A <SPAN class="keyword">\=:</SPAN> Color<SPAN class="keyword">.</SPAN>B <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN>}<BR> {FD<SPAN class="keyword">.</SPAN>distribute ff Color}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR> <BR>Data = [ austria <SPAN class="keyword">#</SPAN> [italy switzerland germany]<BR> belgium <SPAN class="keyword">#</SPAN> [france netherlands germany luxemburg]<BR> france <SPAN class="keyword">#</SPAN> [spain luxemburg italy]<BR> germany <SPAN class="keyword">#</SPAN> [austria france luxemburg netherlands]<BR> italy <SPAN class="keyword">#</SPAN> nil<BR> luxemburg <SPAN class="keyword">#</SPAN> nil<BR> netherlands <SPAN class="keyword">#</SPAN> nil<BR> portugal <SPAN class="keyword">#</SPAN> nil<BR> spain <SPAN class="keyword">#</SPAN> [portugal]<BR> switzerland <SPAN class="keyword">#</SPAN> [italy france germany austria] ]</CODE></DD></DL><P class="caption"><STRONG>Figure 6.1:</STRONG> A script for the Map Coloring Problem together with a data specification.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label82">Script</A></H3><P>The script appears in <A href="node28.html#progmapcoloring">Figure 6.1</A>. It is parameterized with the specification of the map to be colored. The figure shows the specification of a map containing some European countries.</P><P>The script first creates a local variable <CODE>NbColors</CODE> that specifies the number of different colors to be used for coloring the map. Then it distributes naively on <CODE>NbColors</CODE>. Recall that a distributor blocks its thread until it has done its job. After <CODE>NbColors</CODE> is determined by distribution, the variable <CODE>Color</CODE> is constrained to a record mapping the country names to integers in <CODE>1<SPAN class="keyword">#</SPAN>NbColors</CODE>. This implicitly creates the variables for the Countries. Next the script creates a propagator </P><BLOCKQUOTE class="code"><CODE>Color<SPAN class="keyword">.</SPAN>A <SPAN class="keyword">\=:</SPAN> Color<SPAN class="keyword">.</SPAN>B</CODE></BLOCKQUOTE><P> for every pair <CODE>A</CODE>, <CODE>B</CODE> of bordering countries. Finally, the script distributes on <CODE>Color</CODE> using the first-fail strategy.</P><P>The statement </P><BLOCKQUOTE class="code"><CODE>{ExploreOne {MapColoring Data}}</CODE></BLOCKQUOTE><P> will show the search tree explored to find the first solution, which looks as follows: </P><BLOCKQUOTE class="code"><CODE>color(<BR> austria: 1 belgium: 3 france: 1 <BR> germany: 2 italy: 2 luxemburg: 4 <BR> netherlands: 1 portugal: 1 spain: 2 <BR> switzerland: 3 <BR> )</CODE></BLOCKQUOTE><P> The search tree of <CODE>MapColoring</CODE> is interesting. First, colorings with 0, 1, 2 and 3 colors are searched and not found. Then a coloring with 4 colors is searched. Now a solution is found quickly, without going through further failure nodes. There are many solutions using 4 colors since the particular color given to a country does not matter.</P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node27.html">- Up -</A></TD><TD><A href="node29.html#section.minimizing.conference">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
>
1201
