Namespaces
Variants
Actions

Difference between revisions of "Search algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
s1100701.png
 +
$#A+1 = 49 n = 0
 +
$#C+1 = 49 : ~/encyclopedia/old_files/data/S110/S.1100070 Search algorithm
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''on a graph, graph search''
 
''on a graph, graph search''
  
An [[Algorithm|algorithm]] that tries to find all nodes in a [[Network|network]] or [[Graph|graph]] that satisfy a given property. Such algorithms are also used, e.g., to optimize a function on a graph or network or on a set which can easily be turned into a graph, such as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s1100701.png" />. (Two <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s1100702.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s1100703.png" /> vectors of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s1100704.png" /> are joined if an only if they differ in precisely one coordinate, yielding a hypercube.) Thus, these are definite relations and similarities between graph search and search theory as a systematic optimization technique (of enumeration type) [[#References|[a3]]]. See [[#References|[a4]]] for a very complete overview of global optimization (from the search point of view, including random search).
+
An [[Algorithm|algorithm]] that tries to find all nodes in a [[Network|network]] or [[Graph|graph]] that satisfy a given property. Such algorithms are also used, e.g., to optimize a function on a graph or network or on a set which can easily be turned into a graph, such as $  \{ 0,1 \}  ^ {n} $.  
 +
(Two 0 $-
 +
$  1 $
 +
vectors of length $  n $
 +
are joined if an only if they differ in precisely one coordinate, yielding a hypercube.) Thus, these are definite relations and similarities between graph search and search theory as a systematic optimization technique (of enumeration type) [[#References|[a3]]]. See [[#References|[a4]]] for a very complete overview of global optimization (from the search point of view, including random search).
  
Two of the most often used search techniques in graphs or networks are depth-first search and breadth-first search. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s1100705.png" /> be a finite oriented graph (cf. [[Graph, oriented|Graph, oriented]]). For each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s1100706.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s1100707.png" /> be the set of edges (arcs) issuing from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s1100708.png" />. For instance, in Fig.a1, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s1100709.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007011.png" />.
+
Two of the most often used search techniques in graphs or networks are depth-first search and breadth-first search. Let $  \Gamma = ( V,E ) $
 +
be a finite oriented graph (cf. [[Graph, oriented|Graph, oriented]]). For each $  v \in V $,  
 +
let $  A ( v ) $
 +
be the set of edges (arcs) issuing from $  v $.  
 +
For instance, in Fig.a1, $  A ( 1 ) = \{ ( 1,2 ) , ( 1,4 ) \} $,
 +
$  A ( 3 ) = \{ ( 3,6 ) \} $,  
 +
$  A ( 7 ) = \emptyset $.
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/s110070a.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/s110070a.gif" />
Line 9: Line 31:
 
Figure: s110070a
 
Figure: s110070a
  
It is assumed that the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007013.png" />, are given some fixed total order (cf. also [[Totally ordered set|Totally ordered set]]) for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007014.png" />. The following algorithm picks out all nodes in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007015.png" /> that are reachable from a source node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007016.png" /> by means of a directed path. These nodes will be marked. Central to the algorithm is a certain list <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007017.png" />, which can be seen as a sort of wave front indicating the boundary of the spreading blob of marked points:
+
It is assumed that the sets $  A ( v ) $,  
 +
$  v \in V $,  
 +
are given some fixed total order (cf. also [[Totally ordered set|Totally ordered set]]) for all $  v $.  
 +
The following algorithm picks out all nodes in $  \Gamma $
 +
that are reachable from a source node s $
 +
by means of a directed path. These nodes will be marked. Central to the algorithm is a certain list $  L $,  
 +
which can be seen as a sort of wave front indicating the boundary of the spreading blob of marked points:
  
 
unmark all points;
 
unmark all points;
  
mark the source node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007018.png" />;
+
mark the source node s $;
  
set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007019.png" />;
+
set $  L = \{ s \} $;
  
as long as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007020.png" /> is non-empty, run the following iterative procedure:
+
as long as $  L $
 +
is non-empty, run the following iterative procedure:
  
choose a node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007021.png" />;
+
choose a node $  i \in L $;
  
select the first oriented edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007022.png" /> that runs (from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007023.png" />) to an unmarked node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007024.png" /> (if any);
+
select the first oriented edge $  ( i,j ) \in A ( i ) $
 +
that runs (from $  i $)  
 +
to an unmarked node $  j $(
 +
if any);
  
mark the node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007025.png" />;
+
mark the node $  j $;
  
define the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007026.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007027.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007028.png" />;
+
define the function $  { \mathop{\rm revp} } $
 +
on $  j $
 +
as $  { \mathop{\rm revp} } ( j ) = i $;
  
add <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007029.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007030.png" />;
+
add $  j $
 +
to $  L $;
  
if there is no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007031.png" /> that runs to an unmarked node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007032.png" />, remove <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007033.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007034.png" />.
+
if there is no $  ( i,j ) \in A ( i ) $
 +
that runs to an unmarked node $  j $,  
 +
remove $  i $
 +
from $  L $.
  
stop when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007035.png" /> is empty.
+
stop when $  L $
 +
is empty.
  
The algorithm does not yet specify how to select a node from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007036.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007037.png" /> is treated as a queue, i.e., the node selected is the one that has been longest in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007038.png" /> (first-in-first-out) the result is breadth-first search. On the other hand, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007039.png" /> is treated as a stack, i.e., the node selected is the one that was last added to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007040.png" /> (last-in-first-out) the result is depth-first search.
+
The algorithm does not yet specify how to select a node from $  L $.  
 +
If $  L $
 +
is treated as a queue, i.e., the node selected is the one that has been longest in $  L $(
 +
first-in-first-out) the result is breadth-first search. On the other hand, if $  L $
 +
is treated as a stack, i.e., the node selected is the one that was last added to $  L $(
 +
last-in-first-out) the result is depth-first search.
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/s110070b.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/s110070b.gif" />
Line 41: Line 85:
 
For an oriented tree as in Fig.a2 (downwards oriented), starting at the indicated node, breadth-first search will first pick the three children of the node indicated (in some order) and then will proceed to the next layer. Depth-first search will first pick a maximal downward chain (maximal in the sense that it ends at a leaf, not necessarily maximal in length) and then go back to another child of the last branching node in that chain.
 
For an oriented tree as in Fig.a2 (downwards oriented), starting at the indicated node, breadth-first search will first pick the three children of the node indicated (in some order) and then will proceed to the next layer. Depth-first search will first pick a maximal downward chain (maximal in the sense that it ends at a leaf, not necessarily maximal in length) and then go back to another child of the last branching node in that chain.
  
The order which is used on the edge sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007041.png" /> also matters, but not as much.
+
The order which is used on the edge sets $  A ( v ) $
 +
also matters, but not as much.
  
The edges picked out by the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007042.png" /> (reverse path), i.e., the edges <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007043.png" /> form an oriented tree comprising the reachable nodes from the source node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007044.png" />.
+
The edges picked out by the function $  { \mathop{\rm revp} } $(
 +
reverse path), i.e., the edges $  ( { \mathop{\rm revp} } ( j ) ,j ) $
 +
form an oriented tree comprising the reachable nodes from the source node s $.
  
The results of the algorithm in four cases are given below for the case of Fig.a1.''''''<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1">search</td> <td colname="2" style="background-color:white;" colspan="1">marking</td> <td colname="3" style="background-color:white;" colspan="1">oriented</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">method</td> <td colname="2" style="background-color:white;" colspan="1">sequence</td> <td colname="3" style="background-color:white;" colspan="1">tree</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">breadth first,</td> <td colname="2" style="background-color:white;" colspan="1">1 2 4 3 5 6 7</td> <td colname="3" style="background-color:white;" colspan="1">
+
The results of the algorithm in four cases are given below for the case of Fig.a1.<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1">search</td> <td colname="2" style="background-color:white;" colspan="1">marking</td> <td colname="3" style="background-color:white;" colspan="1">oriented</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">method</td> <td colname="2" style="background-color:white;" colspan="1">sequence</td> <td colname="3" style="background-color:white;" colspan="1">tree</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">breadth first,</td> <td colname="2" style="background-color:white;" colspan="1">1 2 4 3 5 6 7</td> <td colname="3" style="background-color:white;" colspan="1">
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/" />
  
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">lexicographic</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">order</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007045.png" /></td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">breadth first,</td> <td colname="2" style="background-color:white;" colspan="1">1 4 2 5 3 7 6</td> <td colname="3" style="background-color:white;" colspan="1">
+
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">lexicographic</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">order</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">on the $  A ( i ) $
 +
</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">breadth first,</td> <td colname="2" style="background-color:white;" colspan="1">1 4 2 5 3 7 6</td> <td colname="3" style="background-color:white;" colspan="1">
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/" />
  
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">reverse</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">lexicographic</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">order</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007046.png" /></td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">depth first</td> <td colname="2" style="background-color:white;" colspan="1">1 2 3 6 5 7 4</td> <td colname="3" style="background-color:white;" colspan="1">
+
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">reverse</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">lexicographic</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">order</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">on the $  A ( i ) $
 +
</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">depth first</td> <td colname="2" style="background-color:white;" colspan="1">1 2 3 6 5 7 4</td> <td colname="3" style="background-color:white;" colspan="1">
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/" />
  
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">lexicographic</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">order</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007047.png" /></td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">depth first</td> <td colname="2" style="background-color:white;" colspan="1">1 4 5 7 2 3 6</td> <td colname="3" style="background-color:white;" colspan="1">
+
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">lexicographic</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">order</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">on the $  A ( i ) $
 +
</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">depth first</td> <td colname="2" style="background-color:white;" colspan="1">1 4 5 7 2 3 6</td> <td colname="3" style="background-color:white;" colspan="1">
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/" />
  
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">reverse</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">lexicographic</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">order</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007048.png" /></td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> </tbody> </table>
+
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">reverse</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">lexicographic</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">order</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">on the $  A ( i ) $
 +
</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> </tr> </tbody> </table>
  
 
</td></tr> </table>
 
</td></tr> </table>
  
There is an obvious analogous search algorithm for non-oriented graphs. These algorithms run in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110070/s11007049.png" /> time.
+
There is an obvious analogous search algorithm for non-oriented graphs. These algorithms run in $  O ( \# V + \# E ) $
 +
time.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.K. Ahuja,  T.L. Magnanti,  J.B. Orlin,  "Network flows"  G.L. Nemhauser (ed.)  A.H.G. Rinnooy Kan (ed.)  M.J. Todd (ed.) , ''Optimization'' , North-Holland  (1991)  pp. 211–370</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H.M. Salkin,  "Integer programming" , Addison-Wesley  (1975)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  C.H. Papadimitriou,  K. Steiglitz,  "Combinatorial optimization" , Prentice-Hall  (1982)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.A. Zhigljavsky,  "Theory of global random search" , Kluwer Acad. Publ.  (1991)  (In Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.K. Ahuja,  T.L. Magnanti,  J.B. Orlin,  "Network flows"  G.L. Nemhauser (ed.)  A.H.G. Rinnooy Kan (ed.)  M.J. Todd (ed.) , ''Optimization'' , North-Holland  (1991)  pp. 211–370</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H.M. Salkin,  "Integer programming" , Addison-Wesley  (1975)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  C.H. Papadimitriou,  K. Steiglitz,  "Combinatorial optimization" , Prentice-Hall  (1982)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.A. Zhigljavsky,  "Theory of global random search" , Kluwer Acad. Publ.  (1991)  (In Russian)</TD></TR></table>

Latest revision as of 08:12, 6 June 2020


on a graph, graph search

An algorithm that tries to find all nodes in a network or graph that satisfy a given property. Such algorithms are also used, e.g., to optimize a function on a graph or network or on a set which can easily be turned into a graph, such as $ \{ 0,1 \} ^ {n} $. (Two $ 0 $- $ 1 $ vectors of length $ n $ are joined if an only if they differ in precisely one coordinate, yielding a hypercube.) Thus, these are definite relations and similarities between graph search and search theory as a systematic optimization technique (of enumeration type) [a3]. See [a4] for a very complete overview of global optimization (from the search point of view, including random search).

Two of the most often used search techniques in graphs or networks are depth-first search and breadth-first search. Let $ \Gamma = ( V,E ) $ be a finite oriented graph (cf. Graph, oriented). For each $ v \in V $, let $ A ( v ) $ be the set of edges (arcs) issuing from $ v $. For instance, in Fig.a1, $ A ( 1 ) = \{ ( 1,2 ) , ( 1,4 ) \} $, $ A ( 3 ) = \{ ( 3,6 ) \} $, $ A ( 7 ) = \emptyset $.

Figure: s110070a

It is assumed that the sets $ A ( v ) $, $ v \in V $, are given some fixed total order (cf. also Totally ordered set) for all $ v $. The following algorithm picks out all nodes in $ \Gamma $ that are reachable from a source node $ s $ by means of a directed path. These nodes will be marked. Central to the algorithm is a certain list $ L $, which can be seen as a sort of wave front indicating the boundary of the spreading blob of marked points:

unmark all points;

mark the source node $ s $;

set $ L = \{ s \} $;

as long as $ L $ is non-empty, run the following iterative procedure:

choose a node $ i \in L $;

select the first oriented edge $ ( i,j ) \in A ( i ) $ that runs (from $ i $) to an unmarked node $ j $( if any);

mark the node $ j $;

define the function $ { \mathop{\rm revp} } $ on $ j $ as $ { \mathop{\rm revp} } ( j ) = i $;

add $ j $ to $ L $;

if there is no $ ( i,j ) \in A ( i ) $ that runs to an unmarked node $ j $, remove $ i $ from $ L $.

stop when $ L $ is empty.

The algorithm does not yet specify how to select a node from $ L $. If $ L $ is treated as a queue, i.e., the node selected is the one that has been longest in $ L $( first-in-first-out) the result is breadth-first search. On the other hand, if $ L $ is treated as a stack, i.e., the node selected is the one that was last added to $ L $( last-in-first-out) the result is depth-first search.

Figure: s110070b

For an oriented tree as in Fig.a2 (downwards oriented), starting at the indicated node, breadth-first search will first pick the three children of the node indicated (in some order) and then will proceed to the next layer. Depth-first search will first pick a maximal downward chain (maximal in the sense that it ends at a leaf, not necessarily maximal in length) and then go back to another child of the last branching node in that chain.

The order which is used on the edge sets $ A ( v ) $ also matters, but not as much.

The edges picked out by the function $ { \mathop{\rm revp} } $( reverse path), i.e., the edges $ ( { \mathop{\rm revp} } ( j ) ,j ) $ form an oriented tree comprising the reachable nodes from the source node $ s $.

The results of the algorithm in four cases are given below for the case of Fig.a1.

<tbody> </tbody>
search marking oriented
method sequence tree
breadth first, 1 2 4 3 5 6 7

lexicographic
order
on the $ A ( i ) $
breadth first, 1 4 2 5 3 7 6

reverse
lexicographic
order
on the $ A ( i ) $
depth first 1 2 3 6 5 7 4

lexicographic
order
on the $ A ( i ) $
depth first 1 4 5 7 2 3 6

reverse
lexicographic
order
on the $ A ( i ) $

There is an obvious analogous search algorithm for non-oriented graphs. These algorithms run in $ O ( \# V + \# E ) $ time.

References

[a1] R.K. Ahuja, T.L. Magnanti, J.B. Orlin, "Network flows" G.L. Nemhauser (ed.) A.H.G. Rinnooy Kan (ed.) M.J. Todd (ed.) , Optimization , North-Holland (1991) pp. 211–370
[a2] H.M. Salkin, "Integer programming" , Addison-Wesley (1975)
[a3] C.H. Papadimitriou, K. Steiglitz, "Combinatorial optimization" , Prentice-Hall (1982)
[a4] A.A. Zhigljavsky, "Theory of global random search" , Kluwer Acad. Publ. (1991) (In Russian)
How to Cite This Entry:
Search algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Search_algorithm&oldid=16418
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article