Unit - 3
Search Algorithms:
● Search algorithms are methods used to find an optimal sequence of actions or decisions (a "path") from
an initial state to a desired goal state within a defined problem space.
● They form the basis of problem-solving in many AI applications like pathfinding, game playing, and
planning.
● A search algorithm takes a search problem as input and returns a solution, or an indication of failure.
● The entire set of possible states and actions is often represented as a search tree forming various paths
from the initial state to goal state.
● Each node in the search tree corresponds to a state in the state space and the edges in the search tree
correspond to actions.
● The search tree describes paths between these states, reaching towards the goal.
Example:
The primary way these algorithms are categorized is based on whether they use domain-specific knowledge to
guide the search.
Categories of Search Algorithms:
1. Uninformed Search (Blind Search):
● These algorithms have no additional information about the problem domain, such as the location of
the goal.
● They explore the search space systematically but blindly, treating all nodes equally.
● Different search methods are:
○ Breadth-first Search.
○ Depth-first Search.
○ Dijkstra’s Algorithm or Uniform Cost Search.
○ Depth-limited and iterative deepening search.
○ Bidirectional Search
Breadth-first Search:
● Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph level by level.
● It starts at a chosen source node and explores all of the neighbor nodes at the present depth before
moving on to the nodes at the next depth level.
● Steps in this search are as follows:
○ Start and Queue: It begins at a source node (or root) and uses a queue data structure to keep
track of nodes to visit.
○ Visit and Enqueue:
■ The source node is added to the queue and marked as visited.
■ While the queue is not empty, the algorithm performs the following steps:
○ Dequeue: It removes a node from the front of the queue. This is the current node being
processed.
○ Explore Neighbors: It examines all the unvisited neighbors of the current node.
○ Mark and Enqueue Neighbors: For each unvisited neighbor:
■ It marks the neighbor as visited.
■ It adds the neighbor to the back of the queue.
Characteristics and Applications
Feature Description
Order of Traversal Level-by-level or "breadth-wise."
Data Structure Queue (FIFO: First-In, First-Out).
Completeness Complete; it is guaranteed to find a solution if
one exists in a finite graph.
Optimality (Unweighted Graph) Optimal for finding the shortest path (in terms
of the number of edges) in an unweighted graph
(where all edge weights are equal or 1).
Depth-first Search Algorithm:
● The Depth-First Search (DFS) algorithm is an uninformed search strategy used for traversing or
searching tree or graph data structures.
● It explores as far as possible along each branch before backtracking.
● DFS starts at the root (or any arbitrary node) of a tree or graph and explores as far as possible along the
first path it finds until it reaches a node with no successors (a leaf node) or a pre-defined goal state.
Steps involved in this search are:
● Start: Begin at the root node (initial state).
● Explore Deeply: Follow the first unvisited child of the current node.
● No Successors/Goal Found: If the current node has no unvisited children or is a leaf node, or if the
goal is found, the search moves to the next step.
● Backtrack: If a dead end is reached (no unvisited children), the algorithm backtracks (moves up) to
the immediate parent node and tries to explore its next unvisited child.
● Repeat: Steps 2-4 are repeated until the goal state is found or all nodes in the graph/tree have been
visited.
DFS typically uses a Stack data structure (implicitly or explicitly) to keep track of the nodes to visit,
prioritizing the last-added node (the deepest one).
bfs fifo (queue), dfs LIFO (last in , first out ) stack
2. Informed (Heuristic) Search Algorithms:
● These algorithms use a heuristic function, h(n), which estimates the cost from the current state n to the
goal state.
● This domain-specific knowledge allows them to search more efficiently by prioritizing the most
promising paths.
● These can find solutions more efficiently than an uniformed strategy.
h(n) = estimated cost of the cheapest path from the state at node n to a goal state.
● Different search methods are:
○ Greedy best-first searchmeans un in formed alogathims goe blindly and reach a goal but this
○ A* Search informed algarthims have some information or a knowledge about path and also the
goal so it is more effective
