#1 India's Top IT Training Institute
×

About Uncodemy

Know more about who we are and what we stand for.

About Us

About Us

Discover our mission to equip individuals with essential IT skills and industry expertise.

Read More →
UnCodeMy Gallery

UnCodeMy Gallery

Explore highlights from our IT training sessions and success stories.

Read More →
Mentors

Mentors

Meet the industry experts who train and guide you through your course.

Read More →
Free Resources

Free Resources

Free tutorials, interview questions, tools and calculators to help you learn.

Explore →
×

Free Resources

Learn, practice and plan your career — bilkul free.

Tutorials

Tutorials

Step-by-step written tutorials to learn any technology at your own pace.

Read More →
Free Counselling

Free Counselling

Book a free video counselling session and pick the right course for you.

Read More →
Online Compiler

Online Compiler

Write, run and test your code online — no setup required.

Read More →
Searching Algorithms

Search Algorithms in AI - Types of Search Algorithms in AI & Techniques

What are Search Algorithms in AI?

Search algorithms help AI systems explore possible states to find a path from an initial state to a goal state — fundamental to problem-solving agents.

Uninformed Search Techniques

  • Breadth-First Search (BFS): Explores all nodes at the current depth before moving deeper.
  • Depth-First Search (DFS): Explores as far as possible along a branch before backtracking.
  • Uniform Cost Search: Expands the node with the lowest path cost.

Informed (Heuristic) Search Techniques

  • Greedy Best-First Search: Chooses the node closest to the goal based on a heuristic.
  • A* Search: Combines path cost and heuristic estimate for optimal, efficient search.

Local Search Algorithms

  • Hill Climbing: Continuously moves toward increasing value.
  • Simulated Annealing: Allows occasional worse moves to avoid local optima.

Applications

Search algorithms power route planning (like GPS navigation), puzzle solvers, and game-playing AI such as chess engines.

Key Takeaway: Mastering this topic is a key step toward becoming a well-rounded AI professional, capable of building real-world, intelligent systems.

How the Main Algorithms Compare

Choosing a search algorithm usually comes down to four questions: will it find a solution if one exists (complete), will it find the best one (optimal), how long does it take, and how much memory does it need. Here, b is the branching factor and d is the depth of the shallowest solution.

AlgorithmComplete?Optimal?Memory behaviour
BFSYes, if b is finiteYes, when every step costs the sameHigh: stores a whole level, roughly O(b^d)
DFSNot in infinite or cyclic spaces without checksNoLow: only the current path
Uniform CostYes, with positive step costsYesHigh, similar to BFS
Greedy Best-FirstNoNoCan be high
A*YesYes, with an admissible heuristicHigh: keeps the frontier in memory

Iterative deepening DFS is a useful middle option: it repeats depth-limited DFS with increasing limits, giving BFS-like completeness with DFS-like memory use.

Inside A*: f(n) = g(n) + h(n)

A* ranks each node by g(n), the cost already paid to reach it, plus h(n), a guess of the remaining cost. It always expands the node with the lowest total. If h(n) never overestimates the true remaining cost, the heuristic is called admissible and A* is guaranteed to return an optimal path.

On a grid where you can move up, down, left or right, Manhattan distance (the sum of horizontal and vertical gaps to the goal) is admissible because no path can be shorter than it. Straight-line distance is admissible when diagonal moves are allowed too.

import heapq

def a_star(grid, start, goal):
    def h(p):
        return abs(p[0] - goal[0]) + abs(p[1] - goal[1])

    frontier = [(h(start), 0, start)]
    best_g = {start: 0}
    while frontier:
        f, g, node = heapq.heappop(frontier)
        if node == goal:
            return g
        r, c = node
        for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 0:
                ng = g + 1
                if ng < best_g.get((nr, nc), float("inf")):
                    best_g[(nr, nc)] = ng
                    heapq.heappush(frontier, (ng + h((nr, nc)), ng, (nr, nc)))
    return None   # goal unreachable

Cells with 0 are open and 1 are walls. Setting h to zero turns this into uniform cost search, which shows how closely the two are related.

Picking an Algorithm for a Problem

  • All steps cost the same and the space is small: BFS is simple and finds the shortest path.
  • Steps have different costs, no good estimate available: uniform cost search, which is essentially Dijkstra's algorithm.
  • You can estimate distance to the goal: A* usually explores far fewer nodes.
  • Memory is tight and any solution will do: DFS or iterative deepening.
  • Optimisation with no clear goal state, such as scheduling: local search like hill climbing or simulated annealing.

Errors That Cost Correctness

  • Using a heuristic that overestimates, which makes A* faster but can return a longer path.
  • Forgetting a visited set in graph search, so the algorithm loops around cycles.
  • Stopping when the goal is first added to the frontier rather than when it is removed; with uneven costs this can miss a cheaper route.

Ready to master Artificial Intelligence?

Build real-world AI skills with hands-on projects and mentor-guided training.

Explore Course