SKEDSOFT

A Generic Searching Algorithm: 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 (on the next page), 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. 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 s0, . . . , sk from the frontier. If goal(sk) is true (i.e., sk is a goal node), it has found a solution and returns the path that was found, namely s0, . . . , sk. Otherwise, the path is extended by one more arc by finding the neighbors of sk. For every neighbor s of sk, the path s0, . . . , sk, s is added to the frontier. This step is known as expanding the node sk. 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 on page 170 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.

Generic graph searching algorithm

1: 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 ≠ {} do
13: select and remove s0, . . . , s_k from Frontier
14: if goal(s_k) then
15: return s0, . . . , s_k
16: Frontier ← Frontier∪ {s0, . . . , s_k, s : s_k, s ∈ A}
17: return ⊥

• 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.