## 3.4 A Generic Searching Algorithm

This section describes a generic algorithm to search for a solution path in a graph. The algorithm is independent of any particular search strategy and any particular graph.

The intuitive idea behind the generic search algorithm, given a
graph, a set of start nodes, and a set of goal nodes, is to
incrementally explore paths from the start nodes. This is done by
maintaining a **frontier** (or **fringe**) of
paths from the start node that have been explored.
The frontier
contains all of the paths that could form initial segments of paths
from a start node
to a goal node.
(See
Figure 3.3, where the frontier is the set of paths
to the gray shaded nodes.)
Initially, the frontier contains trivial paths containing no arcs
from the start nodes. As the search proceeds, the frontier expands into the
unexplored nodes until a goal node is encountered. To expand the
frontier, the searcher selects and removes a path from the frontier, extends the path
with each arc leaving the last node, and adds these new paths to the frontier. A
search strategy defines which element of the frontier is selected at
each step.

**Procedure**Search(

*G,S,goal*)

2:

**Inputs**

3:

*G*: graph with nodes

*N*and arcs

*A*

4:

*S*: set of start nodes

5:

*goal*: Boolean function of states

6:

**Output**

7: path from a member of

*S*to a node for which

*goal*is true

8: or

*⊥*if there are no solution paths

9:

**Local**

10:

*Frontier*: set of paths

11:

*Frontier ←{⟨s⟩: s∈S}*

12:

**while**(

*Frontier ≠{}*)

13:

**select**and

**remove**

*⟨s*from

_{0},...,s_{k}⟩*Frontier*

14:

**if**(

*goal(s*)

_{k})**then**

15:

**return**

*⟨s*

_{0},...,s_{k}⟩16:

*Frontier ←Frontier ∪{⟨s*

_{0},...,s_{k},s⟩: ⟨s_{k},s⟩∈A}17:

**return**

*⊥*

The generic search algorithm is shown in
Figure 3.4.
Initially, the frontier is the set of empty paths from start nodes.
At each step, the algorithm advances the frontier by removing a path
*⟨s _{0},...,s_{k}⟩* from the
frontier. If

*goal(s*is true (i.e.,

_{k})*s*is a goal node), it has found a solution and returns the path that was found, namely

_{k}*⟨s*. Otherwise, the path is extended by one more arc by finding the neighbors of

_{0},...,s_{k}⟩*s*. For every neighbor

_{k}*s*of

*s*, the path

_{k}*⟨s*is added to the frontier. This step is known as

_{0},...,s_{k},s⟩**expanding**the node

*s*.

_{k}This algorithm has a few features that should be noted:

- The selection of a path at line 13 is non-deterministic. The choice of path that is selected can affect the efficiency; see the box for more details on our use of "select". A particular search strategy will determine which path is selected.
- It is useful to think of the
*return*at line 15 as a temporary return; another path to a goal can be searched for by continuing to line 16. - If the procedure returns
*⊥*, no solutions exist (or there are no remaining solutions if the proof has been retried). - The algorithm only tests if a path ends in a goal
node
*after*the path has been selected from the frontier, not when it is added to the frontier. There are two main reasons for this. Sometimes a very costly arc exists from a node on the frontier to a goal node. The search should not always return the path with this arc, because a lower-cost solution may exist. This is crucial when the least-cost path is required. The second reason is that it may be expensive to determine whether a node is a goal node.

If the path chosen does not end at a goal node and the node at the end has no neighbors, extending the path means removing the path. This outcome is reasonable because this path could not be part of a path from a start node to a goal node.