
416 Introduction to Soft Computing
11.3.6 Comparison of Basic Uninformed Search Strategies
All the three exhaustive searches, viz., breadth- rst, depth- rst and depth- rst iterative deepening, may
be used to perform bidirectional searches with suitable modi cations. e advantage of bidirectional
search is that it reduces the time complexity from O(b
d
) to O(b
d/2
). is is because both the forward and
the backward searches are expected to meet midway between the start state and the goal. Table 11.4 pres-
ents a comparative picture of the approximate complexities and admissibility of the basic uninformed
search strategies. Here b is t