UNIT II – PROBLEM
SOLVING METHODOLOGY
Heuristic search strategies – heuristic functions - Local search and
optimization problems – local search in continuous space – search
with non-deterministic actions – search in partially observable
environments – online search agents and unknown environments.
Heuristic Search Strategies
Heuristic Search Strategies in Artificial Intelligence (AI) are
problem-solving methods that use domain-specific knowledge
(heuristics) to find solutions more efficiently than uninformed
search strategies (like BFS or DFS). They guide the search
process towards the most promising paths, often leading to
faster and more optimal results.
What is a Heuristic?
•A heuristic is a rule of thumb or educated guess used to estimate the cost
or distance to the goal.
•Denoted as h(n), where n is a node, it estimates the cost from node n to the
goal.
Why Use Heuristic Search?
•Reduces search time.
•Focuses only on relevant parts of the search space.
•Useful in large and complex problem spaces (e.g., chess,
navigation, planning).
Common Heuristic Search Strategies:
• 1. Greedy Best-First Search
• 2. A * Search
• 3. Beam Search
• 4. Hill Climbing
HEURISTIC FUNCTIONS
Best First Search Algorithm(Greedy search)
f(n)= h(n)
Were, h(n)= estimated cost from node n to the goal.
The greedy best first algorithm is implemented by the priority queue.
A* Search Algorithm
LOCAL SEARCH AND OPTIMIZATION
PROBLEMS
• A Local Search Optimization Problem is a type of problem
where:
👉 You want to find the best solution
👉 You start with one possible solution
👉 You keep making small changes (called neighbors)
👉 You move to a better solution if found
👉You stop when no better solution is nearby
• You don’t explore all possibilities — only nearby option
Features of Local search
• Keep track of single current state
• Move only to neighboring states
• Ignore paths
Examples of Local Search Algorithms
1. Hill Climbing
2. Simulated Annealing
3. Local Beam Search
4. Genetic Algorithm
Local Search in Continuous Space
Local search in continuous space is an AI optimization technique used to find the best
solution when the variables can take any real (decimal) values, rather than only
fixed or discrete values.
Unlike discrete problems (e.g., 8-puzzle), continuous space problems involve
variables such as weight, height, temperature, or neural network parameters.
Example
Suppose an AI system wants to find the minimum value of:
Here, x can be any real number.
• Start at x = 5
• Move to x = 3
• Then x = 1
• Finally x = 0
At x = 0, the function value is minimum.
Local Search in Continuous Space
Suppose we want to minimize:
Current (x)
4 16
The global minimum is at: 3 9
2 4
1 1
0 0
Assume our starting point is:
The algorithm keeps moving towards a point having a smaller value.
So:
Finally, it reaches:
which is the minimum.
Examples of Local Search in Continuous Space
•Gradient Descent
•Hill Climbing
•Simulated Annealing
•Genetic Algorithm
•Particle Swarm Optimization (PSO)
Gradient Descent
• Gradient Descent is an optimization technique used to find the minimum value
of a function.
• It looks at the slope (gradient) of the function and moves in the direction where
the value decreases.
Example
• Imagine you are standing on a mountain and want to reach the bottom.
• Look at the slope around you.
• Find the direction going downward.
• Take a small step.
• Repeat until you reach the bottom.
Examples of Local Search in Continuous
Space
Hill Climbing
• Hill Climbing is a local search algorithm that continuously moves to a better
neighboring state.
• For maximization, it moves uphill.
Simulated Annealing
Simulated Annealing is a probabilistic local search algorithm that sometimes accepts
worse solutions, especially at high temperature, to escape local optima and gradually
converges toward an optimal solution.
Examples of Local Search in Continuous
Space
Genetic Algorithm
Genetic Algorithm is an evolutionary search and optimization technique that uses
selection, crossover, and mutation to evolve a population of candidate solutions
toward better solutions.
Particle Swarm Optimization (PSO)
Particle Swarm Optimization is a population-based optimization technique inspired
by the social behaviour of birds or fish, where particles update their positions using
their own best experience and the best experience of the swarm.
SEARCH WITH NON-DETERMINISTIC ACTIONS
online search agents and unknown
environments