<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>2.6 Distribution and Search Trees</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="node7.html#section.constraints.incomplete"><< Prev</A></TD><TD><A href="node2.html">- Up -</A></TD><TD><A href="node9.html#section.constraints.example">Next >></A></TD></TR></TABLE><DIV id="section.constraints.dast"><H2><A name="section.constraints.dast">2.6 Distribution and Search Trees</A></H2><P>To solve a finite domain problem <IMG alt="P" src="latex20.png">, we can always choose a constraint <IMG alt="C" src="latex31.png"> and solve both <IMG alt="P\cup\{C\}" src="latex61.png"> and <IMG alt="P\cup\{\neg C\}" src="latex62.png">. We say that we have <EM class="noindex">distributed <IMG alt="P" src="latex20.png"> with <IMG alt="C" src="latex31.png"></EM>. </P><P>We can apply the idea to spaces. Suppose <IMG alt="S" src="latex7.png"> is a stable space that is neither failed nor solved. Then we can choose a constraint <IMG alt="C" src="latex31.png"> and <EM class="noindex">distribute <IMG alt="S" src="latex7.png"> with <IMG alt="C" src="latex31.png"></EM>. Distribution yields two spaces, one obtained by adding a propagator for <IMG alt="C" src="latex31.png">, and one obtained by adding a propagator for <IMG alt="\neg C" src="latex63.png">. </P><P>The combination of constraint propagation and distribution yields a complete solution method for finite domain problems. Given a problem, we set up a space whose store contains the basic constraints and whose propagators impose the nonbasic constraints of the problem. Then we run the propagators until the space becomes stable. If the space is failed or solved, we are done. Otherwise, we choose a not yet determined variable <IMG alt="x" src="latex42.png"> and an integer <IMG alt="n" src="latex43.png"> such that <IMG alt="x=n" src="latex17.png"> is consistent with the constraint store and distribute the space with the constraint <IMG alt="x=n" src="latex17.png">. Since we can tell both <IMG alt="x=n" src="latex17.png"> and <IMG alt="x\neq n" src="latex64.png"> to the constraint store (the store already knows a domain for <IMG alt="x" src="latex42.png">), chances are that constraint propagation can restart in both spaces. </P><P>By proceeding this way we obtain a <A name="label34"></A><EM>search tree</EM> as shown in <A href="node8.html#figfd1">Figure 2.1</A>. Each node of the tree corresponds to a space. Each leaf of the tree corresponds to a space that is either solved or failed. The search tree is always finite since there are only finitely many variables all a priori constrained to finite domains. </P><P></P><DIV id="figfd1"><HR><P><A name="figfd1"></A></P><DIV align="center"><IMG alt="" src="search-tree.gif"></DIV><P class="caption"><STRONG>Figure 2.1:</STRONG> A search tree. Diamonds represent solved spaces and boxes represent failed spaces.</P><HR></DIV><P> </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node7.html#section.constraints.incomplete"><< Prev</A></TD><TD><A href="node2.html">- Up -</A></TD><TD><A href="node9.html#section.constraints.example">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
>
1233
