Scribd
Upload
15 views4 pages

Hill Climbing Algorithm Note

Hill Climbing is a search algorithm in Artificial Intelligence that incrementally improves a solution by moving to better neighboring solutions until no better options exist. It has various types, including Simple, Steepest-Ascent, and Stochastic Hill Climbing, each with its own approach to selecting neighbors. Despite its advantages like ease of implementation and speed, it faces limitations such as the Local Maximum Problem and can be enhanced with techniques like Random Restart and Simulated Annealing.

Uploaded by

Sukenuchi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views4 pages

Hill Climbing Algorithm Note

Hill Climbing is a search algorithm in Artificial Intelligence that incrementally improves a solution by moving to better neighboring solutions until no better options exist. It has various types, including Simple, Steepest-Ascent, and Stochastic Hill Climbing, each with its own approach to selecting neighbors. Despite its advantages like ease of implementation and speed, it faces limitations such as the Local Maximum Problem and can be enhanced with techniques like Random Restart and Simulated Annealing.

Uploaded by

Sukenuchi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Hill Climbing Algorithm

Introduction
Hill Climbing is a search algorithm used in Artificial Intelligence to find the best
possible solution to a problem. It is called “hill climbing” because the process is
similar to climbing a hill: you keep moving upward step by step until you reach the
top (the best solution).

Basic Idea
The algorithm starts with an initial solution and then continuously moves to a
better neighboring solution. It always chooses the option that improves the
current state.
 If a better solution is found → move to it

 If no better solution is found → stop


The goal is to reach the highest value (maximum) or lowest value (minimum)
depending on the problem.

Key Terms

 Current State: The present solution

 Neighbor: A slightly different solution near the current one

 Evaluation Function: A function that tells how good a solution is


 Goal State: The best possible solution
How It Works (Step-by-Step)
1. Start with an initial solution

2. Check all neighboring solutions


3. Choose the best neighbor

4. If the neighbor is better than the current state → move to it

5. Repeat steps 2–4


6. Stop when no better neighbor exists

Example (Easy Understanding)


Imagine you are climbing a hill in the fog:
 You cannot see the entire hill

 You only see nearby steps


 You always take the step that goes upward

 You stop when no upward step is available


This is exactly how the Hill Climbing algorithm works.

Types of Hill Climbing

1. Simple Hill Climbing

o Checks neighbors one by one


o Moves to the first better solution

2. Steepest-Ascent Hill Climbing


o Checks all neighbors

o Moves to the best one


3. Stochastic Hill Climbing
o Chooses a random better neighbor

o Useful when many options exist

Advantages

 Easy to understand and implement


 Uses very little memory

 Fast in many cases

 Works well for simple problems

Disadvantages

1. Local Maximum Problem


o The algorithm may stop at a point that is not the best overall solution

2. Plateau Problem
o When many neighboring states have the same value, the algorithm
gets stuck
3. Ridge Problem

o The path to the best solution is not straight, making it hard to reach
Solutions to Problems
To overcome these issues, we can use:

 Random Restart: Start again from a different point


 Allow Sideways Moves: Move even if the value is the same
 Simulated Annealing: Sometimes allow worse moves to escape local
maxima

Applications

Hill Climbing is used in:

 Artificial Intelligence problems

 Optimization problems

 Game playing
 Scheduling
 Machine learning

Conclusion
Hill Climbing is a simple and powerful algorithm that improves solutions step by
step. Although it has some limitations like getting stuck in local maxima, it is still
widely used due to its simplicity and efficiency.

You might also like