Artificial Intelligence : Unit - 2 Part - 6 : 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.

============================================================

Hill Climbing Algorithm Example

Now that you understand the logic behind the hill climbing algorithm, here is a simple example of a hill climbing algorithm applied to the Travelling Salesman Problem (TSP).

Imagine a salesman who needs to visit a set of cities and return to the starting city. All the while, he was aiming to minimize the total distance travelled.

Hill Climbing Search Algorithm

1. Start Position: The salesman starts at a random city. Let’s say they start at A.

2. Evaluate Neighbours: Look at the neighbouring cities to the current position. These represent potential moves. For city A, neighbours are B, C, and D.

3. Choose the Best Move: Evaluate the total distance for each move and choose the city that minimises the total distance. Suppose moving to city B results in the shortest total distance.

4. Move and Repeat: Move to city B and repeat the process from this new city. Now, the neighbours are A, C, and D.

5. Choose Again: Evaluate the total distance for each move and choose the city that minimises the total distance. Move to city C, as it provides the shortest total distance.

6. Repeat until No Improvement: Keep repeating this process until there is no move that reduces the total distance further. The salesman might explore different routes until reaching a local minimum in terms of total distance.

Example Steps of the Hill Climbing Search:

1. Start at A
2. Neighbours: B, C, D, Move to B (total distance: 10)
3. Neighbours: A, C, D, Move to C (total distance: 25)
4. Neighbours: A, B, D, Move to D (total distance: 45)
5. Neighbours: A, B, C, Move to A (total distance: 57)