BREADTH FIRST SEARCH (UNINFORMED SEARCH) :

 Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph

data structures.
 It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a
‘search key’), and explores all of the neighbour nodes at the present depth prior to
moving on to the nodes at the next depth level.
 BFS uses a queue data structure for its implementation.

 The equivalent search tree for the above graph is as follows. As BFS traverses the tree
“shallowest node first”, it would always pick the shallower branch until it reaches the
solution
 Advantages:

 BFS is useful for analyzing the nodes in a graph and constructing the shortest path of
traversing through these.
 BFS can traverse through a graph in the smallest number of iterations.
 The architecture of the BFS algorithm is simple and robust.
 The result of the BFS algorithm holds a high level of accuracy in comparison to other
algorithms.

BFS for Tree:

BFS for Graph:

***************************************************************************
DEPTH FIRST SEARCH:
 It is recursive algorithm for traversing a tree or graph data structure.
 Traversal means visiting all the nodes of a graph or tree data structure.
 It is called DFS because it starts from the root and follows each path to its greatest
depth node before moving to the next.
 DFS uses a stack data structure for its implementation.
 The process is similar to BFS algorithm.

Example 1:

Solution:

SABDECG
Example 2:

ADVANTAGES:
 DFS consumes very less memory space.
 It will reach at the goal node in a less time period than BFS if it traverses in a
right path.
 It may find a solution without examining much of search because we may get
the desired solution in the very first go.

***************************************************************************
BEST FIRST SEARCH ALGORITHM:
 An uninformed search algorithm would blindly traverse to the next node in a given
manner without considering the cost associated with that step.
 An informed search, like Best first search, on the other hand would use an evaluation
function to decide which among the various available nodes is the most promising (or
‘BEST’) before traversing to that node.

Step 1: Place the starting node into the OPEN list.

Step 2: If the OPEN list is empty, Stop and return failure.
Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n), and
places it in the CLOSED list.
Step 4: Expand the node n, and generate the successors of node n.
Step 5: Check each successor of node n, and find whether any node is a goal node or not.
If any successor node is goal node, then return success and terminate the search, else
proceed to Step 6.
Step 6: For each successor node, algorithm checks for evaluation function f(n), and then
check if the node has been in either OPEN or CLOSED list. If the node has not been in
both list, then add it to the OPEN list.
Step 7: Return to Step 2.
Initialization: Open [A, B], Closed [S]

Iteration 1: Open [A], Closed [S, B]

Iteration 2: Open [E, F, A], Closed [S, B]

: Open [E, A], Closed [S, B, F]

Iteration 3: Open [I, G, E, A], Closed [S, B, F]

: Open [I, E, A], Closed [S, B, F, G]

Hence the final solution path will be: S----> B----->F----> G

***************************************************************************
AI SEARCH ALGORITHM AND ITS TYPES:
Artificial Intelligence is the study of building agents that act rationally. Most of the time,
these agents perform some kind of search algorithm in the background in order to achieve
their tasks.
 A search problem consists of:
 A State Space. Set of all possible states where you can be.
 A Start State. The state from where the search begins.
 A Goal State. A function that looks at the current state returns whether or not
it is the goal state.
 The Solution to a search problem is a sequence of actions, called the plan that transforms
the start state to the goal state.
 This plan is achieved through search algorithms.
Types of search algorithms:
There are too many powerful search algorithms are available in AI. Here we will discuss six
of the fundamental search algorithms, divided into two categories, as shown below.
UNINFORMED SEARCH ALGORITHMS:
The search algorithms in this section have no additional information on the goal node other
than the one provided in the problem definition. The plans to reach the goal state from the start
state differ only by the order and/or length of actions. Uninformed search is also called Blind
search. These algorithms can only generate the successors and differentiate between the goal
state and non goal state.
The following are uninformed search algorithms.
 Depth First Search
 Breadth First Search
 Uniform Cost Search
Each of these algorithms will have:
 A problem graph, containing the start node S and the goal node G.
 A strategy, describing the manner in which the graph will be traversed to get to G.
 A fringe, which is a data structure used to store all the possible states (nodes) that you
can go from the current states.
 A tree, that results while traversing to the goal node.
 A solution plan, which the sequence of nodes from S to G.
INFORMED SEARCH:
Un informed search algorithms which looked through search space for all possible solutions of
the problem without having any additional knowledge about search space. But informed search
algorithm contains an array of knowledge such as how far we are from the goal, path cost, how
to reach to goal node, etc. This knowledge help agents to explore less to the search space and
find more efficiently the goal node.
The informed search algorithm is more useful for large search space. Informed search
algorithm uses the idea of heuristic, so it is also called Heuristic search.

***************************************************************************