�ݺ�ߣ

Uninformed Search Strategies
• An uninformed search algorithm is one where
there is no clue about how close a state is to
the goal(s).
• Egs: Breadth First Search, Depth First Search,
Uniform Cost Search

Breadth First Search
• Breadth-first search (BFS) is a technique for
traversing a finite graph or a tree to search a
node that meets a set of criteria.
• When all actions have the same cost, then the
appropriate strategy is breadth-first search
• The root node is expanded first, then all the
successors of the root node are expanded next,
then their successors, and so on.

Steps to implement BFS Traversal
Step 1: Define a Queue of size total number of vertices in the
graph.
Step 2: Select any vertex as starting point for traversal. Visit
that vertex and insert it into the Queue.
Step 3: Visit all the adjacent vertices of the vertex which is at
front of the Queue which is not visited and insert them into
the Queue.
Step 4: When there is no new vertex to be visited from the
vertex at front of the Queue then delete that vertex from
the Queue.
Step 5: Repeat step 3 and 4 until queue becomes empty.
Step 6: When queue becomes Empty, then produce final
spanning tree by removing unused edges from the graph

BFS Advantages
• Breadth first search will always find the
shortest path first
• Breadth-first search always finds a solution with
a minimal number of actions, because
– when it is generating nodes at depth d, it has
already generated all the nodes at depth d -1
– so if one of them were a solution, it would have
been found
• The solution which is found is always the
optimal solution.

• It can be very memory intensive since it needs
to keep track of all the nodes in the search
graph/tree.
• It can be slow since it expands all the nodes at
each level before moving on to the next level.
• BFS works better when a user searches for the
vertices(goal state) that stay closer to any
given source(initial state)
BFS Disadvantages

Depth First Search
• Depth-first search (DFS) is an algorithm for
traversing or searching tree or graph data structures
• The algorithm starts at the root node and explores
as far as possible along each branch before
backtracking.
• Depth-first search always expands the deepest
node of any particular path before exploring its
breadth
• DFS traversal of a graph, produces a spanning tree
as final result.

Steps to implement DFS Traversal
Step 1: Define a Stack of size total number of vertices in the graph.
Step 2: Select any vertex as starting point for traversal. Visit that
vertex and push it on to the Stack.
Step 3: Visit any one of the adjacent vertex of the vertex which is
at top of the stack which is not visited and push it on to the
stack.
Step 4: Repeat step 3 until there are no new vertex to be visited
from the vertex on top of the stack.
Step 5: When there is no new vertex to be visited then use back
tracking and pop one vertex from the stack.
Step 6: Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7: When stack becomes Empty, then produce final spanning
tree by removing unused edges from the graph

DFS Advantages
• Requires less memory since it only stores stack
of nodes on the path from root node to current
node.
• It can find solution without examining much
search space and stop once found.
• Takes less time to reach goal node than BFS
algorithm.

DFS Disadvantages
• The disadvantage of Depth-First Search is that
there is a possibility that it may go down the
left-most path forever(indefinitely in a cycle)
• Depth-First Search is not guaranteed to find
the solution.
• And there is no guarantee to find a minimal
solution, if more than one solution.

Comparison
• Breadth first search will always find the solution in
the shortest path
• BFS does not require backtracking
• Consumes more resources
• DFS requires less memory since only the nodes on
the current path are stored.
• By chance, DFS may find a solution without
examining much of the search space at all.
• Since DFS moves blindly down one path, looping
(cycles) is a SERIOUS problem

Uniform Cost Search
• Uniform-cost search is a searching algorithm used for
traversing a weighted tree or graph (Dijkstra's algorithm)
• This algorithm comes into play when a different cost is
available for each edge
• The primary goal is to find a path to the goal node which has
the lowest cumulative cost
• Uniform-cost search expands nodes according to their path
costs from the root node
– g(n) = cost from root to n
• It gives maximum priority to the lowest cumulative cost
– Strategy: expand lowest g(n)
• A uniform-cost search algorithm is implemented by the
priority queue

Uniform Cost Search
Algorithm Characteristics
• Advantages:
– Uniform cost search is optimal because at every
state the path with the least cost is chosen
• Disadvantages:
– It does not care about the number of steps
involved in searching and only concerned about
path cost
– Due to which this algorithm may be stuck in an
infinite loop

Bidirectional search
• The bidirectional search simultaneously searches
forward from the initial state and backwards from the
goal state(s), hoping that the two searches will meet
• Bidirectional search replaces one single search graph
with two small sub graphs(one starts the search from an initial vertex
and other starts from goal vertex)
• Bidirectional search can use search techniques such as
BFS, DFS
• We can consider bidirectional approach when
– Both initial and goal states are unique and completely defined
– The branching factor is exactly the same in both directions

Bidirectional search
• To find if there exists a path from
vertex 0 to vertex 14
• We can execute two searches,
one from vertex 0 and other from
vertex 14.
• When both forward and
backward search meet at vertex
7, we know that we have found a
path from node 0 to 14
• The search can be terminated
now without further exploration

�ݺ�ߣ

Problem Solving through Search - Uninformed Search

Recommended

More Related Content

Similar to Problem Solving through Search - Uninformed Search (20)

Recently uploaded (20)

Problem Solving through Search - Uninformed Search