Uniformed search strategies:

It is also called as blind search. The term means that they have no additional information about states beyond that provided in the problem definition. All they can do is generate successors and distinguish a goal state from a non goal state. All search strategies are distinguished y the order in which nodes are expanded.

Breadth first search:

BFS is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successor, and so on. in general, all the nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded.

BFS can be implemented by calling TREE – SEARCH with an empty fringe i.e. a FIFO queue, assuring that the nodes that are visited first will be expanded first. In other words, calling TREE – SEARCH (Problem, FIFO, QUEUE()) results in a breadth – first search. The FIFO queue puts all newly generated successors at the end of the queue, which means that shallow nodes are expanded before deeper nodes. Figure (5) shows the progress of the search on a simple binary tree.

BFS is complete if the shallowest goal node is at some finite depth, BFS will eventually find it after expanding all shallower nodes. The shallowest goal node is not necessarily the optimal one, technically, BFS is optimal if the path cost is a non decreasing function of the depth of the node.

We consider a hypothetical state space where every state has n successors. The root of the search tree generates b nodes at the first level, each of which generates b more nodes, for a total of $b^2$ at the second level. Each of these generates b more nodes, yielding $b^3$ nodes at the third level and so on.

In worst case, we would expand all but the last node at level d, generating $b^{b+1} - b$ nodes at level d + 1. Then the total number of nodes generated is

$b + b^2 + b^3 + . . . . + b^d + (b^{d+1} – b) = 0 (b^{d+1})$

Every node that is generated must remain in memory, because it is either part of the fringe or is an ancestor of a fringe node. The space complexity is, therefore, the same as the times complexity (plus one node for the root).

Those who do complexity analysis are worried by exponential complexity bounds such as $0(b^{d+1})$

Figure (7) shows why. It lists branching actor b = 10, for various values of the solution depth d. the table assumes that 10,000 can be generated per second and that a node requires 1000 bytes of storage.

There are two lessons to be learned from figure (4)

First, The memory requirements are a bigger problem for BFS than is the execution time, 31 hours would not be too long to wait for the solution to an important problem o depth 8, but few computers have the terabyte of main memory it would take fortunately, there are other search strategies that require less memory.

The second lesson is that the time requirements are still a major factor. If your problem, has a solution at depth 12, then it will take 35 years for 3 Fs to find it. In general, exponential complexity search problems can not be solved by uniformed methods for any but the smallest instances.

Figure (7) Time and memory requirements for BFS.

The number shown assume branching factor b = 10, 10,000 nodes/second, 1000 bytes/node.