SKEDSOFT

Uninformed Search Strategies: A problem determines the graph and the goal but not which path to select from the frontier. This is the job of a search strategy. A search strategy specifies which paths are selected from the frontier. Different strategies are obtained by modifying how the selection of paths in the frontier is implemented.

This section presents three uninformed search strategies that do not take into account the location of the goal. Intuitively, these algorithms ignore where they are going until they find a goal and report success.

Depth-First Search: The first strategy is depth-first search. In depth-first search, the frontier acts like a last-in first-out stack. The elements are added to the stack one at a time. The one selected and taken off the frontier at any time is the last element that was added.

Implementing the frontier as a stack results in paths being pursued in a depth-first manner – searching one path to its completion before trying an alternative path. This method is said to involve backtracking: The algorithm selects a first alternative at each node, and it backtracks to the next alternative when it has pursued all of the paths from the first selection. Some paths may be infinite when the graph has cycles or infinitely many nodes, in which case a depth-first search may never stop. This algorithm does not specify the order in which the neighbors are added to the stack that represents the frontier. The efficiency of the algorithm is sensitive to this ordering.

Suppose n0, . . . , nk is the selected path in the frontier. Then every other element of the frontier is of the form n0, . . . , ni,m, for some index i < n and some node m that is a neighbor of ni; that is, it follows the selected path for a number of arcs and then has exactly one extra node. To understand the complexity (see the box on page 83) of depth-first search, consider an analogy using family trees, where the neighbors of a node correspond to its children in the tree. At the root of the tree is a start node. A branch down this tree corresponds to a path from a start node. Consider the node at the end of path at the top of the frontier. The other elements of the frontier correspond to children of ancestors of that node – the “uncles,” “great uncles,” and so on. If the branching factor is b and the first element of the list has length n, there can be at most n×(b−1) other elements of the frontier. These elements correspond to the b − 1 alternative paths from each node. Thus, for depth-first search, the space used is linear in the depth of the path length from the start to a node.

If there is a solution on the first branch searched, then the time complexity is linear in the length of the path; it considers only those elements on the path, along with their siblings. The worst-case complexity is infinite. Depthfirst search can get trapped on infinite branches and never find a solution, even if one exists, for infinite graphs or for graphs with loops. If the graph is a finite tree, with the forward branching factor bounded by b and depth n, the worst-case complexity is O(bn).

Example: Consider a modification of the delivery graph, in which the agent has much more freedom in moving between locations. The new graph is presented in Figure 3.6. An infinite path leads from ts to mail, back to ts, back to mail, and so forth. As presented, depth-first search follows this path forever, never considering alternative paths from b3 or o109. The frontiers for the first five iterations of the path-finding search algorithm using depth-first search are
[(o103)]
[(o103, ts , o103, b3 , o103, o109]
[o103, ts, mail , o103, ts, o103 , o103, b3 , o103, o109]
[o103, ts, mail, ts , o103, ts, o103 , o103, b3 , o103, o109]
[o103, ts, mail, ts, mail , o103, ts, mail, ts, o103 , o103, ts, o103 ,
o103, b3 , o103, o109]
Depth-first search can be improved by not considering paths with cycles

Because depth-first search is sensitive to the order in which the neighbors are added to the frontier, care must be taken to do it sensibly. This ordering can be done statically (so that the order of the neighbors is fixed) or dynamically (where the ordering of the neighbors depends on the goal). Depth-first search is appropriate when either

• space is restricted;
• many solutions exist, perhaps with long path lengths, particularly for the case where nearly all paths lead to a solution; or
• the order of the neighbors of a node are added to the stack can be tuned so that solutions are found on the first try.

It is a poor method when

• it is possible to get caught in infinite paths; this occurs when the graph is infinite or when there are cycles in the graph; or
• solutions exist at shallow depth, because in this case the search may look at many long paths before finding the short solutions.

Depth-first search is the basis for a number of other algorithms, such as iterative deepening.