<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD><TITLE>2.9 Search Order</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="node10.html#section.constraints.distribution"><< Prev</A></TD><TD><A href="node2.html">- Up -</A></TD><TD><A href="node12.html#section.constraints.models">Next >></A></TD></TR></TABLE><DIV id="section.constraints.order"><H2><A name="section.constraints.order">2.9 Search Order</A></H2><P>So far we have not specified in which order search trees are explored. Although this order has no impact on the shape and size of a search tree, it does have an impact on the time and memory resources needed to find one or all solutions: </P><UL><LI><P>If we are only interested in one solution, there is no need to explore the entire search tree. Ideally, we would just explore the path leading from the root to the solution.</P></LI><LI><P>If we are interested in all solutions, we need to explore the entire search tree. However, whether we explore the tree in depth-first or breadth-first manner will make a big difference in the memory needed. The memory requirements of breadth-first exploration are typically exponentially larger than those of depth-first exploration.</P></LI></UL><P> We will assume that the search engine explores the search trees always in a depth-first fashion. Moreover, when the engine distributes with a constraint <IMG alt="C" src="latex31.png">, it explores the space obtained with <IMG alt="C" src="latex31.png"> first and the space obtained with <IMG alt="\neg C" src="latex95.png"> second. </P><P>The above assumptions ensure that the exploration of a search tree is a deterministic process, provided the distribution strategy generating the constraints to distribute with is deterministic.</P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node10.html#section.constraints.distribution"><< Prev</A></TD><TD><A href="node2.html">- Up -</A></TD><TD><A href="node12.html#section.constraints.models">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
>
1183
