Page 29 - DCAP506_ARTIFICIAL_INTELLIGENCE

Unit 2: Problems, Problem Spaces and Search

For applications of DFS to search problems in artificial intelligence, though, the graph to be Notes
searched is frequently either excessively large to visit in its entirety or even infinite, and DFS
may undergo from non-termination when the length of a path in the search tree is infinite.
Consequently, the search is only performed to a restricted depth, and because of restricted
memory accessibility one naturally does not use data structures that keep track of the set of all
formerly visited vertices. Here, the time is still linear in the number of extended vertices and
edges (even though this number is not similar as the size of the complete graph since some
vertices may be searched more than once and others not at all) but the space complexity of this
alternative of DFS is only comparative to the depth limit, much slighter than the space required
for searching to the similar depth using breadth-first search. For such applications, DFS also
provides itself much better to heuristic methods of selecting a likely-looking branch. When a
suitable depth limit is not recognized a priori, iterative deepening depth-first search applies
DFS frequently with a sequence of rising limits; in the artificial intelligence mode of analysis,
with a branching factor superior than one, iterative deepening enhances the running time by
only a constant factor over the case in which the accurate depth limit is recognized due to the
geometric growth of the number of nodes for each level.

2.4.1 Vertex Orderings

It is also probable to utilize the depth-first search to linearly order the vertices of the original
graph (or tree). There are three general methods of performing this:
 A preordering is a list of the vertices so that they were first visited by the depth-first search
algorithm. This is a compact and usual manner of illustrating the development of the
search. A preordering of an expression tree is the expression in Polish notation.

 A postordering is a list of the vertices so that they were last visited by the algorithm. A
postordering of an expression tree is the expression in reverse Polish notation.
 A reverse postordering is the reverse of a postordering, which is defined a list of the
vertices in the conflicting order of their previous visit. When probing a tree, reverse
postordering is similar as preordering, but generally they are dissimilar when looking
for a graph.

Task Make distinction between preordering and postordering.

2.4.2 Applications

Algorithms that utilize depth-first search as a building block comprise:
 Locating connected components.
 Topological sorting.

 Finding 2-(edge or vertex)-connected components.
 Locating strongly connected components.
 Planarity Testing

 Solving puzzles with only one solution, like mazes. (DFS can be adapted to discover all
solutions to a maze by only involving nodes on the present path in the visited set.)
 bi connectivity.

LOVELY PROFESSIONAL UNIVERSITY 23