AI Search Algorithms: BFS, DFS, and Hill Climbing

Posted on Jul 10, 2026 in Civil Engineering Technology

Breadth First Search (BFS) and Depth First Search (DFS) Algorithms

Breadth First Search (BFS) is a graph traversal algorithm that visits all the vertices level by level. It starts from a source vertex and explores all its neighboring vertices before moving to the next level. BFS uses a Queue (FIFO) data structure.

BFS Algorithm

  1. Start from the source vertex.
  2. Mark the source vertex as visited.
  3. Insert the source vertex into a queue.
  4. Repeat until the queue becomes empty:
    • Remove the front vertex from the queue.
    • Visit all its unvisited adjacent vertices.
    • Mark each adjacent vertex as visited.
    • Insert them into the queue.

BFS Example

      A
     / \
    B   C
   / \ / \
  D  E F  G

Starting vertex = A

Traversal:

  • Queue: A | Visit: A
  • Queue: B, C | Visit: B
  • Queue: C, D, E | Visit: C
  • Queue: D, E, F, G | Visit: D → E → F → G

BFS Traversal Order: A → B → C → D → E → F → G

Applications of BFS

  • Finding the shortest path in an unweighted graph.
  • Web crawling.
  • GPS navigation systems.
  • Social networking.
  • Network broadcasting.

Complexity of BFS

  • Time Complexity: O(V + E)
  • Space Complexity: O(V)

Depth First Search (DFS)

Depth First Search (DFS) is a graph traversal algorithm that explores one branch completely before backtracking. It uses a Stack (LIFO) or Recursion.

DFS Algorithm

  1. Start from the source vertex.
  2. Mark the source vertex as visited.
  3. Visit one unvisited adjacent vertex.
  4. Repeat until no adjacent vertex remains.
  5. Backtrack to the previous vertex.
  6. Continue until all vertices are visited.

DFS Example

      A
     / \
    B   C
   / \ / \
  D  E F  G

Starting vertex = A

Traversal: Visit A → Go to B → Go to D → Backtrack to B → Visit E → Backtrack to A → Go to C → Visit F → Backtrack → Visit G

Hill Climbing Search: Advantages and Limitations

Hill Climbing Search is a heuristic search algorithm used in Artificial Intelligence to find an optimal or near-optimal solution. It starts with an initial state and repeatedly moves to the neighboring state with the highest value (or lowest cost) until no better neighboring state exists. It is similar to climbing a hill by always taking the steepest upward step toward the peak.

Hill Climbing is a local search algorithm because it considers only the current state and its immediate neighbors, without remembering previously visited states.

Hill Climbing Algorithm

  1. Start with an initial state.
  2. Evaluate the current state using a heuristic (evaluation) function.
  3. Generate all neighboring states.
  4. Select the best neighboring state.
  5. If the selected neighbor is better than the current state, move to it.
  6. Repeat Steps 3–5 until no better neighbor exists.
  7. The current state is the solution (may or may not be the global optimum).

Hill Climbing Example

Suppose we want to maximize the function: f(x) = -(x – 5)2 + 25. The maximum value occurs at x = 5.

Current StateFunction Value
x = 19
x = 216
x = 321
x = 424
x = 525 (Maximum)

Starting from x = 1: Move to x = 2 → x = 3 → x = 4 → x = 5. No better neighbor exists, so the algorithm stops at the optimal solution.

Types of Hill Climbing

  • Simple Hill Climbing: Moves to the first better neighbor found.
  • Steepest-Ascent Hill Climbing: Evaluates all neighbors and chooses the best one.
  • Stochastic Hill Climbing: Selects a better neighbor randomly.

Advantages of Hill Climbing

  • Simple and easy to implement.
  • Requires very little memory.
  • Faster than exhaustive search methods.
  • Produces good solutions for optimization problems.
  • Suitable for large search spaces.

Limitations of Hill Climbing

  • Local Maximum: May stop at a local optimum instead of the global optimum.
  • Plateau: May get stuck when neighboring states have the same value.
  • Ridge Problem: The best path may require moving sideways or downward.
  • Not Complete: Does not guarantee finding a solution.
  • Sensitive to Initial State: Different starting points lead to different results.

Applications of Hill Climbing

  • Route and path optimization.
  • Robot navigation.
  • Job scheduling.
  • Game playing.

Simulated Annealing and Local Search in Continuous Spaces

Simulated Annealing (SA)

Simulated Annealing is an improved version of Hill Climbing that can accept worse solutions temporarily to escape local optima. It is inspired by the annealing process in metallurgy.

Working Principle

  • Starts with a high temperature, allowing moves to worse states.
  • As temperature decreases, the probability of accepting worse solutions decreases.
  • At low temperatures, it behaves like Hill Climbing.

The probability of accepting a worse solution is: P = e-ΔE/T

Simulated Annealing Algorithm

  1. Start with an initial solution and a high temperature.
  2. Generate a neighboring solution.
  3. If the new solution is better, accept it.
  4. If it is worse, accept it with probability e-ΔE/T.
  5. Reduce the temperature according to a cooling schedule.

Advantages and Limitations of SA

  • Advantages: Escapes local optima, finds near-global solutions, simple to implement.
  • Limitations: Performance depends on the cooling schedule, may require long execution time, no guarantee of global optimum.

Local Search in Continuous Spaces

This technique is used when variables take continuous (real-valued) values. The most common method is Gradient Descent, which uses the slope of the function to move toward the minimum.

Algorithm Steps

  1. Choose an initial point.
  2. Compute the gradient of the objective function.
  3. Move in the direction of the negative gradient.
  4. Update the current point and repeat until convergence.

Example of Continuous Search

For f(x) = (x – 3)2, the minimum is at x = 3. Starting at x = 8, the algorithm moves toward 6, then 4, and finally settles at 3.

Applications and Advantages

  • Applications: Machine Learning, Neural Networks, Robotics, Image Processing.
  • Advantages: Efficient for continuous problems, suitable for large search spaces, requires less memory.
  • Limitations: Can get trapped in local minima, sensitive to starting points, requires differentiable functions.