Artificial Intelligence : Unit - 2 Part - 5 : Hill Climbing Search – AI Search Technique

 

UNIT – II

 Hill Climbing Search – AI Search Technique

---

Introduction

What is Hill Climbing?

Hill Climbing is a heuristic local search algorithm used in Artificial Intelligence to find the optimal solution by progressively improving the current state based on a heuristic function.

• It starts from an initial state and repeatedly moves to the neighbor with the highest value (or lowest cost).
• The process continues until no neighbor is better than the current state — meaning a peak (maximum) is reached.

💡 Think of it as climbing a hill where each step is taken in the direction that appears steepest upward.

---

Real-Life Analogy

Imagine you're in a foggy mountain range.

You can't see far ahead. But you can feel the slope under your feet.

So, you keep moving uphill step-by-step until you find that every direction leads downward — you've reached the top (or a local peak).

---

Key Features of Hill Climbing

Feature	Description
Type	Informed Search (uses heuristics)
Approach	Greedy, local improvement
Goal	Maximize (or minimize) a given evaluation function
Heuristic Used?	✅ Yes (h(n) – heuristic value)
Memory Efficient?	✅ Yes (uses minimal memory)

---

 

How Hill Climbing Works (Step-by-Step)

1. Start at an initial state
• Choose any starting point in the state space.
2. Evaluate all neighboring states
• Use a heuristic function h(n) to determine their "quality".
3. Choose the neighbor with the best heuristic value
• Move in that direction.
4. Repeat steps 2–3
• Until one of the following happens:
• ✅ Goal is reached
• ❌ No better neighbor exists → stuck in local maxima

---

Example:

Let’s say a robot must choose between 4 paths:

State	Heuristic Value (h(n))
A	10
B	20
C	25 ← Best
D	15

• The algorithm chooses state C as the next move because it has the highest heuristic value among all neighbors.

---

Types of Hill Climbing

1️. Simple Hill Climbing

• Chooses the first neighbor that is better than the current state.
• Doesn’t check all neighbors.
• Pros: Faster
• Cons: May miss the best possible move.

2️. Steepest Ascent Hill Climbing

• Evaluates all neighbors and selects the best one.
• Pros: More accurate
• Cons: Slower, computationally heavier.

3️. Stochastic Hill Climbing

• Randomly selects one of the better neighbors.
• Pros: Can help avoid local maxima.
• Cons: Less predictable, not always optimal.

---

Problems in Hill Climbing

Problem	Description
Local Maximum	A solution that is better than its neighbors, but not the global maximum.
Plateau	A flat region where many neighboring states have the same value.
Ridge	A slope that leads upward but is difficult to detect with small moves.

🧠 These problems can cause the algorithm to get stuck, even if a better solution exists elsewhere.

---

Applications of Hill Climbing

• 🤖 Robot Path Planning: When only local terrain info is available.
• 🧠 Machine Learning: To adjust weights in models like neural networks.
• 🎮 Game AI: Making greedy and fast decisions in real-time.
• 📈 Function Optimization: Finding maxima/minima of mathematical functions.

---

Advantages & Disadvantages

Advantages	Disadvantages
✅ Simple to implement	❌ Can get stuck in local maxima
✅ Very memory-efficient (constant space usage)	❌ May not find the global optimum
✅ Fast on simple problems	❌ Struggles with plateaus and ridges

---

Summary

• Hill Climbing is a heuristic algorithm that greedily chooses the best next move based on local information.
• It’s a simple, fast, and space-efficient algorithm, suitable for real-time decisions.
• However, it is not guaranteed to find the global optimum, especially when the state space has local maxima, plateaus, or ridges.
• Types include:
• Simple Hill Climbing
• Steepest Ascent Hill Climbing
• Stochastic Hill Climbing

---

Final Thought:

“Hill Climbing is like trying to reach the highest mountain, but only by looking at the path right in front of you.”
It’s efficient but not always wise — sometimes, you must take a step back to move forward.