Topic: Search Algorithms

Notes
UPPSC Polytechnic Lecturer 2025 (CS)
Contains 8 PDF lessons

Generated: 6 April 2026

KnowledgeGate
Module

Paper 2 | Artificial Intelligence & High Performan

Topic
Search Algorithms

Subtopic
Uninformed Search Strategies

Lesson

Uninformed Search
Strategies

Lesson 1 of 8
 Search Algorithms
Uninformed Search Strategies

[Link]

[Link]
 Uniform Cost Search (UCS)
Uniform Cost Search is an informed search algorithm that expands nodes based on the cost of the path leading to
them. It is an extension of Breadth-First Search (BFS) that takes into account the cost of reaching each node to
find the lowest-cost path to the goal.

Example: Consider the graph below

Based on the cost we will expand the graph in order: a → b → d → c → f → e → g → h

[Link]

[Link]
 UCS Algorithm:
1. Start with the initial state as the root node.
2. Maintain a priority queue or a priority-based data structure to store nodes based on their path cost.
3. Enqueue the root node with a path cost of zero.
4. While the priority queue is not empty, do the following:
▪ Dequeue the node with the lowest path cost from the priority queue.
▪ If the dequeued node is the goal state, terminate the search and return the solution.
▪ Otherwise, expand the node and enqueue its unvisited neighboring nodes with their updated path costs.
5. Repeat steps 4 until the goal state is found or the priority queue is empty.

Advantages:
❖ Optimal Solution: Uniform Cost Search guarantees finding the lowest-cost path to the goal.
❖ Flexibility: It can handle problems with varying edge costs, making it suitable for scenarios where cost is a
critical factor.

Disadvantages:
❖ Time and Space Complexity: The time and space complexity of UCS can be high, especially in large search
spaces or when there are many nodes with different path costs.
❖ Inefficiency in Uninformed Settings: In cases where all edge costs are the same, Uniform Cost Search
effectively becomes a Breadth-First Search, losing its optimality advantage.
[Link]

[Link]
 Completeness: Uniform Cost Search is complete if the search space is finite, and all path costs are greater than
some threshold.

Optimality: Uniform Cost Search is optimal as it guarantees finding the lowest-cost path to the goal.

Time Complexity: The time complexity of Uniform Cost Search depends on the number of nodes and the cost of
the lowest-cost path to the goal. In the worst case, it can be exponential, i.e., O(b^d), where b is the branching
factor and d is the depth of the shallowest goal node.

Space Complexity: The space complexity of Uniform Cost Search can also be exponential in the worst case,
i.e., O(b^d), as it may need to store all the nodes along the lowest-cost path in memory.

[Link]

[Link]
 Depth Limited Search (DLS)
● Depth-Limited Search is an extension of Depth-First Search (DFS) that limits the depth of exploration to
avoid infinite loops or excessively deep paths. It sets a predefined depth limit and terminates the search if the
limit is reached without finding a solution.

● Id limit is l, then nodes at depth l are treated as if they have no successors.

[Link]

[Link]
 DLS Algorithm:
1. Start with the initial state as the root node.
2. Set a depth limit for the search.
3. Explore a node and recursively explore its unvisited neighboring nodes, decrementing the depth limit by 1.
4. If the depth limit reaches 0, backtrack and return to the previous node.
5. Repeat steps 3 and 4 until a goal state is found or the depth limit is reached.

Advantages:
❖ Avoids Infinite Loops: By limiting the depth of exploration, Depth-Limited Search prevents getting stuck in
infinite loops that may occur in cyclic or infinitely deep search spaces.
❖ Memory Efficiency: Depth-Limited Search requires less memory compared to an unlimited DFS, as it only
keeps track of a limited number of levels in the search tree.

Disadvantages:
❖ Completeness Not Guaranteed: Depth-Limited Search is not complete if the depth limit is smaller than the
depth of the goal state. It may fail to find a solution even if one exists.
❖ Non-Optimal Solutions: Depth-Limited Search does not guarantee finding the optimal solution, as it may
terminate before reaching the shallowest goal state.

[Link]

[Link]
 Completeness: Depth-Limited Search is not complete if the depth limit is smaller than the depth of the shallowest
goal state.

Optimality: Depth-Limited Search does not guarantee finding the optimal solution, as it may terminate before
reaching the shallowest goal state.

Time Complexity: The time complexity of Depth-Limited Search depends on the depth limit and the structure of
the search space. In the worst case, it can be exponential, i.e., O(b^l), where b is the branching factor and l is the
depth limit.

Space Complexity: The space complexity of Depth-Limited Search depends on the depth limit and the maximum
number of nodes stored in memory at any given time. In the worst case, it can be O(b*l), where b is the branching
factor and l is the depth limit.

[Link]

[Link]
 Bi-Directional Search (BDS)
● Bidirectional Search is a search algorithm that simultaneously performs two separate searches, one forward
from the initial state and one backward from the goal state. It aims to meet in the middle by searching for a
common node reached from both directions.
● The motivation is that bd/2 + bd/2 is much less than bd. Bidirectional search is implemented by replacing the
goal test with a check to see whether the frontiers of the two searches intersect; if they do, a solution has
been found.

[Link]

[Link]
 BDS Algorithm:
1. Start with the initial state and the goal state.
2. Maintain two separate queues or priority queues, one for the forward search and one for the backward search.
3. Enqueue the initial state in the forward queue and the goal state in the backward queue.
4. While both queues are not empty, do the following:
a. Dequeue a node from each queue.
b. If the dequeued nodes are the same or connected, a path has been found. Terminate the search and
combine the paths from both directions.
c. Otherwise, expand the forward node and enqueue its unvisited neighboring nodes in the forward queue.
d. Expand the backward node and enqueue its unvisited neighboring nodes in the backward queue.
5. Repeat steps 4 until a path is found or both queues are empty.

[Link]

[Link]
 Advantages:

❖ Faster Exploration: Bidirectional Search can be faster than traditional searches by exploring the search space
simultaneously from both ends, potentially reducing the search effort.
❖ Reduces Effective Branching Factor: As the search progresses from both directions, the effective branching
factor is reduced, leading to a more efficient search.

Disadvantages:

❖ Increased Memory Requirement: Bidirectional Search requires storing visited nodes from both directions,
leading to increased memory consumption compared to unidirectional searches.
❖ Additional Overhead: The coordination and synchronization between the two searches introduce additional
overhead in terms of implementation complexity.

[Link]

[Link]
 Completeness: Bidirectional Search is complete if both the forward and backward searches are complete in a
finite search space.

Optimality: Bidirectional Search is optimal if both the forward and backward searches are optimal.

Time Complexity: The time complexity of Bidirectional Search depends on the branching factor, the depth of the
shallowest goal state, and the meeting point of the two searches. In the best case, it can be O(b^(d/2)), where b is
the branching factor and d is the depth of the goal state.

Space Complexity: The space complexity of Bidirectional Search depends on the memory required to store
visited nodes from both directions. In the best case, it can be O(b^(d/2)), where b is the branching factor and d is
the depth of the goal state.

[Link]

[Link]
 Problems in Uninformed Search
1. Blind Exploration: Uninformed search strategies, such as Breadth-First Search or Depth-First Search, lack
domain-specific knowledge or heuristics. They explore the search space without any information about the
problem structure or the goal state.

1. Inefficient in Complex Spaces: Uninformed search strategies can be inefficient in large or complex search
spaces, as they may require extensive exploration of irrelevant or unpromising paths.

1. Lack of Guidance: Without guidance or knowledge about the problem, uninformed search strategies may
spend unnecessary time exploring unproductive areas, resulting in suboptimal or inefficient solutions.

1. Limited Adaptability: Uninformed search strategies do not adapt to the problem domain or utilize available
information effectively. They follow a fixed set of rules or heuristics that do not consider the specifics of the
problem.

1. Inability to Prioritize: Uninformed search strategies do not prioritize certain paths or nodes based on their
potential or relevance. They treat all nodes equally, which can lead to a broader exploration instead of
focusing on more promising areas.
[Link]

[Link]
Module

Paper 2 | Artificial Intelligence & High Performan

Topic
Search Algorithms

Subtopic
Fundamentals of Heuristic Search

Lesson

Fundamentals of Heuristic
Search

Lesson 2 of 8
 Search Algorithms
Fundamentals of Heuristic Search

[Link]

[Link]
 Informed (Heuristic) Search Strategies
❖ Heuristic search strategies are like smart search methods that use special knowledge or hints to find solutions
more efficiently. It's similar to when we use our intuition or common sense to solve a problem.

❖ Imagine you are trying to find the shortest route to a

friend's house in an unfamiliar city. Instead of randomly
exploring different roads, you ask locals for directions and
use landmarks as clues to guide your search. This
approach helps you make more informed decisions and
find the best route faster.

❖ Heuristic search strategies use similar principles. They

have specific information about a problem and use it to
estimate which actions or paths are more likely to lead to
the desired solution. It's like having a knowledgeable
guide showing you the way.

[Link]

[Link]
 ❖ Advantages: Heuristic search strategies can be more efficient because they focus on exploring the most
promising options based on the available knowledge. It's like following the best leads or clues when searching
for something, which saves time and effort.

❖ Limitations: The effectiveness of heuristic search strategies depends on the quality of the information or
knowledge they have. If the clues or hints are inaccurate or misleading, the strategy may lead to suboptimal or
incorrect solutions.

❖ Note: Heuristic search strategies strike a balance between exploring new possibilities and using domain-
specific knowledge. They mimic how we approach problem-solving in real life, relying on relevant information to
make better decisions and find solutions more effectively.

[Link]

[Link]
 Conditions for optimality: Admissibility and consistency
• The first condition we require for optimality is that h(n) be an admissible heuristic.

• An admissible heuristic is one that never overestimates the cost to reach the goal. Admissible heuristics are
by nature optimistic because they think the cost of solving the problem is less than it actually is.

• For example, Straight-line distance is admissible because the shortest path between any two points is a straight
line, so the straight line cannot be an overestimate.

[Link]

[Link]
Module

Paper 2 | Artificial Intelligence & High Performan

Topic
Search Algorithms

Subtopic
Best First Search

Lesson

Best First Search

Lesson 3 of 8
 Search Algorithms
Best First Search

[Link]

[Link]
 Best-first search
• Best First Search is combination of depth first and breadth first searches. It uses the property of both
searches to find out best solution.

• As Depth first search, solution can be found without computing all nodes and in breadth first does not get
trapped in dead ends.

• The best first search allows us to switch between paths using the advantage of both approaches. At each
step the most valued node (according to heuristic function) is chosen. If one of the nodes chosen generates
nodes that are less valued, then BFS can go for another at the same level and in effect the search changes
from depth first search to breadth first search. If on searching for other node if no other node meets the
criteria, then BFS go back to previously unexpanded node as branch is not forgotten and the search
method reverts to the descendants of the first choice and proceeds.

[Link]

[Link]
 There are of course many different ways of defining a heuristic function h. But there are also different ways of
using h to decide which path to expand next; which gives rise to different best-first search algorithms.

One option is greedy best-first search:

● expand a path with an end node n such that h(n) is minimal

Breadth-first and depth-first search may also be seen as special cases of best-first search (which do not use h at
all):

● Breadth-first: expand the (leftmost of the) shortest path(s)

● Depth-first: expand the (leftmost of the) longest path(s)

[Link]

[Link]
[Link]

[Link]
 Best-first search
• Idea: use an evaluation function f(n) for each node
– f(n) provides an estimate for the total cost.
🡪 Expand the node n with smallest f(n).
• Implementation:
Order the nodes in fringe increasing order of cost.
• Special cases:
– greedy best-first search
– A* search
Advantages of Best-First Search
• It can find a solution without exploring much of the state space.
• It uses less memory than other informed search methods like A* as it does not store all the generated nodes.

Disadvantages of Best-First Search

• It is not complete. In some cases, it may get stuck in an infinite loop.
• It is not optimal. It does not guarantee the shortest possible path will be found.
• It heavily depends on the accuracy of the heuristic.

[Link]

[Link]
 Completeness and Optimality
• Best-First Search is not complete and not optimal. It is not complete because it can get stuck in an infinite
loop, for instance, if it keeps going back and forth between two nodes. It is not optimal as it does not always
find the shortest path to the goal, it is heavily dependent on the heuristic.

Time and Space Complexity

• The time and space complexity of Best-First Search are both O(b^d), where b is the branching factor
(number of successors per state), and d is the depth of the shallowest solution. These complexities can be
very high in problems with a large number of states and actions. In the worst case, the algorithm will need
to visit all nodes, and since each node is stored, the space complexity is also proportional to the number of
nodes.

[Link]

[Link]
 Example: Greedy Best-first Search
Greedy best-first search means always trying to continue with the node that seems closest to the goal. This will
work sometimes, but not all of the time:

Clearly, greedy best-first search is not optimal. Like depth-first search, it is also not complete.
[Link]

[Link]
 Properties of greedy best-first search
Complete No — can get stuck in loops For example, going from Iasi to Fagaras, Iasi → Neamt → Iasi → Neamt →
...
Complete in finite space with repeated-state checking

Time O(bm), but a good heuristic can give dramatic improvement

(more laer)
Space O(bm)—keeps all nodes in memory Optimal No
(For example, the cost of the path found in the previous slide was
450. The path Arad, Sibiu, Rimnicu Vilcea, Pitesti, Bucharest has a cost of 140+80+97+101 = 418.)

[Link]

[Link]
Module

Paper 2 | Artificial Intelligence & High Performan

Topic
Search Algorithms

Subtopic
A* Search Algorithm

Lesson

A-start Search
[Link]

Lesson 4 of 8
 Search Algorithms
A* Search Algorithm

[Link]

[Link]
 A* Search: Minimizing the total estimated solution cost
• A* Search is an informed search algorithm that combines the advantages of both Uniform Cost Search and
Greedy Best-First Search. It evaluates a node based on a combination of the cost of the path from the start
node to that node and an estimated heuristic function that estimates the cost to reach the goal form the current
node.

• A∗ search evaluates nodes by combining g(n), the cost to reach the node, and h(n), the estimated cost to get
from the node to the goal:
f(n) = g(n) + h(n)

• Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path
from n to the goal, we have

f(n) = estimated cost of the cheapest solution through n

[Link]

[Link]
 A* Search Algorithm:
1. Start with the initial state as the root node.

1. Create an evaluation function that combines the cost of the path and a heuristic estimate.

1. Initialize an empty priority queue or priority-based data structure.

1. Enqueue the initial state into the priority queue based on the evaluation function.

1. While the priority queue is not empty, do the following:

1. Dequeue the node with the highest priority from the priority queue.
2. If the dequeued node is the goal state, terminate the search and return the solution.
3. Otherwise, expand the node and enqueue its unvisited neighboring nodes into the priority queue based on
the evaluation function.

1. Repeat steps 5 until a solution is found or the priority queue is empty.

[Link]

[Link]
 Advantage:
• Optimality: A* Search guarantees finding the optimal solution if certain conditions are met.
• Efficiency: By using the heuristic function, A* Search focuses on more promising paths, leading to efficient
exploration of the search space.

Disadvantage:
• Heuristic Accuracy: The quality of the heuristic function greatly affects the performance of A* Search.
Inaccurate or misleading heuristics can lead to suboptimal solutions.

Completeness: A* Search is complete if the search space is finite and the heuristic function is admissible (never
overestimates the actual cost).

Optimality: A* Search is optimal if the heuristic function is admissible and consistent (also known as monotonic).

Time Complexity: The time complexity of A* Search depends on the heuristic function, the branching factor, and
the structure of the search space. In the worst case, it can be exponential.

Space Complexity: The space complexity of A* Search depends on the size of the priority queue and the
number of nodes stored in memory. In the worst case, it can be exponential.
[Link]

[Link]
 Completeness: On finite graphs with non-negative edge weights A* is guaranteed to terminate and is complete,
On infinite graphs with a finite branching factor and edge costs that are bounded away from zero, A* is guaranteed
to terminate only if there exists a solution.

• Time Complexity: O(bd)

• Space Complexity: O(bd)

Some observations made: If C* is the cost of the optimal solution path, then we can say the following:

• A* expands all nodes with f(n) < C*. In our example we found the optimal solution cost = 418, all the nodes
having cost less than 418 was expanded in our example.

• A* expands no nodes with f(n) > C*—for example, Timisoara is not expanded in even though it is a child of the
root.

[Link]

[Link]
 Conditions for optimality: Admissibility and consistency
• A second, slightly stronger condition called consistency (or monotonicity) is required only for applications of
A∗ to graph search.

• A heuristic h(n) is consistent if, for every node n and every successor n’ of n generated by any action a, the
estimated cost of reaching the goal from n is no greater than the step cost of getting to n’ plus the estimated
cost of reaching the goal from n’:
h(n) ≤ c(n, a, n’) + h(n )

A heuristic is consistent if h(n)≤c(n,a,n′)+h(n′)

If h is consistent, we have

f(n′)=g(n′)+h(n′)

=g(n)+c(n,a,n′)+h(n′)
≥g(n)+h(n)
=f(n)
[Link]

I.e., f(n) is nondecreasing along any path.

[Link]
 • This is a form of the general triangle inequality, which stipulates that each side of a triangle cannot be longer
than the sum of the other two sides.

• Every consistent heuristic is also admissible. Consistency is therefore a stricter requirement than admissibility.

• For example, hSLD ; we know that the general triangle inequality is satisfied when each side is measured by the
straight-line distance and that the straight-line distance between n and n’ is no greater than c(n, a, n’). Hence,
hSLD is a consistent heuristic.

• A∗ has the following properties: the tree-search version of A∗ is optimal if h(n) is admissible, while the
graph-search version is optimal if h(n) is consistent.

[Link]

[Link]
 Heuristic Functions
• We can generate a number of admissible heuristic functions and chose the one which dominates the others.

• One problem with generating new heuristic functions is that one often fails to get a single “clearly best”
heuristic. If a collection of admissible heuristics h1 . . .hm is available for a problem and none of them dominates
any of the others, which should we choose?

• We can resolve this by defining h(n) = max{h1(n), . . . , hm(n)} .

[Link]

[Link]
 • Completeness: On finite graphs with non-negative edge weights A* is guaranteed to terminate and is
complete, On infinite graphs with a finite branching factor and edge costs that are bounded away from zero, A*
is guaranteed to terminate only if there exists a solution.

• Time Complexity: O(bd)

• Space Complexity: O(bd)

Some observations made:

If C* is the cost of the optimal solution path, then we can say the following:

• A* expands all nodes with f(n) < C*. In our example we found the optimal solution cost = 418, all the nodes
having cost less than 418 was expanded in our example.

• A* expands no nodes with f(n) > C*—for example, Timisoara is not expanded in even though it is a child of the
root.

[Link]

[Link]
Module

Paper 2 | Artificial Intelligence & High Performan

Topic
Search Algorithms

Subtopic
AO* and Branch-Based Search

Lesson

AO-start and
Branch-Based Search

Lesson 5 of 8
 Search Algorithms
AO* and Branch-Based Search

[Link]

[Link]
 AO Search Algorithm*
The AO* algorithm builds a solution graph that contains a single initial node and a number of goal nodes. It
progressively expands the current "best" partial solution. At each step, the algorithm chooses the node with the
minimum heuristic value for expansion.

[Link]

[Link]
 Example: Consider the AND-OR Graph given below:

• In figure above the top node A is expanded producing two area one leading to B and leading to CD .

• The numbers at each node represent the value of f' at that node (cost of getting to the goal state from current
state).

• For simplicity, it is assumed that every operation (traversal) has a unit cost.

[Link]

[Link]
 • With the given information: it appears that C is the most promising node to expand since its f' = 3 i.e. the lowest.

• But going through B would be better since to expand C we must also expand D and the combined cost would
be 9 (3 + 4 + 1 + 1).

• Through B it would be 6(5+1).

[Link]

[Link]
 Example: Consider the AND-OR Graph given below:

• We start by expanding the root node i.e. A and it leads to B and C-D.

• On B the cost is (4 + 1) = 5 and on CD the cost is: (3+2+1+1) = 7. So we choose B for further expansion.

• B can lead to E or F. Expanding E we get the cost as: (6+1) = 7 and on expanding F we get the cost as: (8 + 1)
= 9. So we choose E and update the new heuristic value of B.

[Link]

[Link]
 • Now we again back propagate the heuristic value to A from B. Thus we get the update heuristic value of A as:
(7 + 1) = 8.

• Now the heuristic value on the RHS of the Tree is less than the LHS. So we now expand the RHS of the tree.

• Expanding C towards G we get the updated heuristic value of C as (2 + 1) = 3. Expanding C towards HI we get
the updated heuristic value as: (1+1+1+1) = 4. Thus the minimum heuristic value for C is 3.

[Link]

[Link]
 • Expanding D towards J we get the updated heuristic value of D as: (1 + 1) = 2.

• Thus back propagating the updated heuristic values to root A we get: (3 + 2 + 1 + 1) = 7

[Link]

[Link]
 The pseudocode of AO* is as follows:

1. Initialize the graph with a single node (the start node).

2. While the solution graph contains non-terminal nodes (nodes that have successors not in the graph):
■ Choose a non-terminal node for expansion based on a given strategy.
■ Expand the node (add successors to the graph and update the costs of nodes).
3. The process continues until the start node is labeled as a terminal node.

Advantages of AO Algorithm*
• It can efficiently solve problems with multiple paths due to its use of heuristics.
• It is optimal when the heuristic function is admissible (never overestimates the true cost).

Disadvantages of AO Algorithm*
• It can consume a large amount of memory, similar to the A* algorithm.
• The performance of AO* is heavily dependent on the accuracy of the heuristic function. If the heuristic function
is not well-chosen, AO* could perform poorly.

[Link]

[Link]
 • Completeness and Optimality
• AO* is complete, meaning it is guaranteed to find a solution if one exists. It is also optimal, meaning it will
find the best solution, provided that the heuristic function is admissible (never overestimates the true cost)
and consistent (satisfies the triangle inequality).

• Time and Space Complexity

• The time and space complexity of the AO* algorithm is highly dependent on the problem at hand,
particularly the size of the state space, the number of goals, and the quality of the heuristic function. In the
worst case, the algorithm will need to visit all nodes, and since each node is stored, the space complexity is
also proportional to the number of nodes.

[Link]

[Link]
Module

Paper 2 | Artificial Intelligence & High Performan

Topic
Search Algorithms

Subtopic
Local Search Fundamentals

Lesson

Local Search Fundamentals

Lesson 6 of 8
 Search Algorithms
Local Search Fundamentals

[Link]

[Link]
 Local Search Algorithms and Optimization Problems
• Local search algorithms operate using a single current node (rather than multiple paths as seen in previous
algorithms) and generally move only to new state is the new state is better than the current state.

• Typically, the paths followed by the search are not retained whereas previously we were retaining the paths in
some algorithms. That is once we reach new state older state is forgotten.

• Local search algorithms are not systematic, but they have two key advantages:
(1) They use very little memory—usually a constant amount; and
(2) They can often find reasonable solutions in large or infinite (continuous) state spaces for which
systematic algorithms are unsuitable.

[Link]

[Link]
 Hill Climbing
• It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better
solution by making a change, If the change produces a better solution, another incremental change is made to
the new solution, and so on until no further improvements can be found.

• Hill climbing is sometimes called greedy local search because it grabs a good neighbor state without thinking
ahead about where to go next.

[Link]

[Link]
 Algorithm for Simple Hill climbing:
• Step 1: Evaluate the initial state. If it is a goal state then stop and return success. Otherwise, make initial state
as current state.

• Step 2: Loop until the solution state is found or there are no new operators present which can be applied to the
current state.

a) Select a state that has not been yet applied to the current state and apply it to produce a new
state.

b) Perform these to evaluate new state

i. If the current state is a goal state, then stop and return success.
ii. If it is better than the current state, then make it current state and proceed further.
iii. If it is not better than the current state, then continue in the loop until a solution is found.

• Step 3: Exit.

[Link]

[Link]
 Advantages of Hill Climbing:
• It's simple to understand and easy to implement.
• It requires less computational power compared to other search algorithms.
• If the heuristic is well chosen, it can find a solution (albeit not necessarily the optimal one) in a reasonable time.

Disadvantages of Hill Climbing:

• It's not guaranteed to find the optimal solution.
• It's highly sensitive to the initial state and can get stuck in local optima.
• It does not maintain a search history, which can cause the algorithm to cycle or loop.
• It can't deal effectively with flat regions of the search space (plateaux) or regions that form a ridge.

[Link]

[Link]
 Problems with Hill Climbing
• Local maxima: a local maximum is a peak that is higher than each of its neighboring states but lower than the
global maximum. Hill-climbing algorithms that reach the vicinity of a local maximum will be drawn upward
toward the peak but will then be stuck with nowhere else to go.

[Link]

[Link]
 • Ridges: A ridge is shown in Figure. Ridges result in a sequence of local maxima that is very difficult for greedy
algorithms to navigate.

[Link]

[Link]
 • Plateaux: a plateau is a flat area of the state-space landscape. It can be a flat local maximum, from which no
uphill exit exists, or a shoulder, from which progress is possible. A hill-climbing search might get lost on the
plateau. In each case, the algorithm reaches a point at which no progress is being made.

[Link]

[Link]
Module

Paper 2 | Artificial Intelligence & High Performan

Topic
Search Algorithms

Subtopic
Advanced Local Optimization Techniques

Lesson

Advanced Local
Optimization Techniques

Lesson 7 of 8
 Search Algorithms
Advanced Local Optimization Techniques

[Link]

[Link]
 • Simulated Annealing: This technique allows the hill climbing algorithm to make bad moves (i.e., moving to
worse states) with a certain probability, especially in the early stages of the search. This probability is reduced
over time. The aim is to avoid getting stuck in local optima and ridges.

• Tabu Search: To prevent the algorithm from getting stuck in a loop or revisiting states, a list of previously
visited states can be maintained, which are then avoided in future steps.

• Local Beam Search: To tackle plateaux and local optima, this variation of hill climbing keeps track of k states
rather than just one. It begins with k randomly generated states. At each step, all the successors of all k states
are generated, and if any one is a goal, it halts. Else, it selects the best k successors from the complete list and
repeats.

[Link]

[Link]
 Simulated annealing
• A hill-climbing algorithm that never makes “downhill” moves toward states with lower value (or higher cost) is
guaranteed to be incomplete, because it can get stuck on a local maximum.

• A purely random walk—that is, moving to a successor chosen uniformly at random from the set of successors—
is complete but extremely inefficient.

• It will be reasonable to try to combine hill climbing with a random walk in some way that yields both efficiency
and completeness.

• Simulated annealing is such an algorithm that combines hill algorithm with random walk.

• Annealing is the process used to temper or harden metals and glass by heating them to a high temperature and
then gradually cooling them, thus allowing the material to reach a low energy crystalline state.

[Link]

[Link]
 Local beam search
• The local beam search algorithm keeps track of k states rather than just one state.

• It begins with k randomly generated states. At each step, all the successors of all k states are generated. If any
one is a goal, the algorithm halts.

• Otherwise, it selects the k-best successors from the complete list and repeats.

• In a local beam search, useful information is passed among the parallel search threads.

• The states that generate the best successors say to the others, “Come over here, the grass is greener!”

• The algorithm quickly abandons unfruitful searches and moves its resources to where the most progress is
being made.

[Link]

[Link]
 Problem Encountered
• Local beam search can suffer from a lack of diversity among the k states—they can quickly become
concentrated in a small region of the state space, making the search little more than an expensive version of hill
climbing.

• A variant called stochastic beam search, analogous to stochastic hill climbing, helps alleviate this problem.

• Instead of choosing the best k from the pool of candidate successors, stochastic beam search chooses k
successors at random, with the probability of choosing a given successor being an increasing function of its
value.

Random-restart hill climbing :

• To avoid local optima, you can perform multiple runs of the algorithm from different random initial states. This is
called random-restart hill climbing and increases the chance of finding a global optimum.

[Link]

[Link]
Module

Paper 2 | Artificial Intelligence & High Performan

Topic
Search Algorithms

Subtopic
Means–Ends Analysis

Lesson

Means–Ends Analysis

Lesson 8 of 8
 Search Algorithms
Means–Ends Analysis

[Link]

[Link]
 Means-Ends Analysis
• We have studied the strategies which can reason either in forward or backward, but a mixture of the two
directions is appropriate for solving a complex and large problem.

• Such a mixed strategy, make it possible that first to solve the major part of a problem and then go back and
solve the small problems arise during combining the big parts of the problem. Such a technique is
called Means-Ends Analysis.

• Means-Ends Analysis is problem-solving techniques used in Artificial intelligence for limiting search in AI
[Link] is a mixture of Backward and forward search technique.

[Link]

[Link]
 How means-ends analysis Works:

• The means-ends analysis process can be applied recursively for a problem.

• It is a strategy to control search in problem-solving. Following are the main Steps which describes the working
of MEA technique for solving a problem. Given a current state and a goal state:

• First, evaluate the difference between Current State and the Goal State.

• Select the various operators which can be applied for each difference.

• Apply the operator at each difference, which reduces the difference between the current state and goal
state.

[Link]

[Link]
 Example: Consider the figure given below:

Using Mean End Analysis:

• We first evaluate the difference between the current and the goal state. For each difference, we will generate a
new state and will apply the operators.

• Applying Delete operator: The first difference that we find is that in goal state there is no dot symbol which is
present in the initial state, so, first we will apply the Delete operator to remove this dot.

[Link]

[Link]
 • Applying Move Operator: After applying the Delete operator, the new state occurs which we will again
compare with goal state.

• After comparing these states, there is another difference that is the triangle is outside the circle, so, we will
apply the Move Operator.

[Link]

[Link]
 • Applying Expand Operator: Now a new state is generated in the third step, and we will compare this state
with the goal state. After comparing the states there is still one difference which is the size of the triangle, so,
we will apply Expand operator, and finally, it will generate the goal state.

[Link]

[Link]
 Operator Subgoaling
• In the MEA process, we detect the differences between the current state and goal state. Once these differences
occur, then we can apply an operator to reduce the differences.

• But sometimes it is possible that an operator cannot be applied to the current state.

• So we create the subproblem of the current state, in which operator can be applied, such type of backward
chaining in which operators are selected, and then sub goals are set up to establish the preconditions of the
operator is called Operator Subgoaling.

[Link]

[Link]
 Here is a brief description of how Means-Ends Analysis works:

[Link] Differences: The first step in means-ends analysis is to compare the current state with the goal
state. The differences between these two states are noted.

[Link] Sub-goals: For each difference identified in step one, the algorithm sets a sub-goal to reduce that
difference. These sub-goals need to be addressed in order to move closer to the final goal.

[Link] Operators: An operator is an action that moves the current state closer to the goal state. The means-
ends analysis looks for operators that can be applied to each of the sub-goals set in step two.

[Link] Operators: The algorithm applies the operator that is expected to make the most progress towards
the goal state. If a direct application is not possible due to constraints, the algorithm sets a new sub-goal to
eliminate the constraint.

[Link]: The above steps are repeated until the goal state is reached or until no useful operators can be
found.

[Link]

[Link]
 Local beam search
• The local beam search algorithm keeps track of k states rather than just one state.

• It begins with k randomly generated states. At each step, all the successors of all k states are generated. If any
one is a goal, the algorithm halts.

• Otherwise, it selects the k-best successors from the complete list and repeats.

• In a local beam search, useful information is passed among the parallel search threads.

• The states that generate the best successors say to the others, “Come over here, the grass is greener!”

• The algorithm quickly abandons unfruitful searches and moves its resources to where the most progress is
being made.

[Link]

[Link]
 Problem Encountered
• Local beam search can suffer from a lack of diversity among the k states—they can quickly become
concentrated in a small region of the state space, making the search little more than an expensive version of hill
climbing.

• A variant called stochastic beam search, analogous to stochastic hill climbing, helps alleviate this problem.

• Instead of choosing the best k from the pool of candidate successors, stochastic beam search chooses k
successors at random, with the probability of choosing a given successor being an increasing function of its
value.

[Link]

[Link]
 Branch and Bound
• A branch and bound algorithm is an optimization technique to get an optimal solution to the problem.

• The idea of a branch-and-bound search is to maintain the lowest-cost path to a goal found so far, and its cost.

• It systematically enumerates all candidate solutions and dispose of obviously impossible solutions.

• The first part of branch-and-bound, branching, requires several choices to be made so that the choices branch
out into the solution space.

• Branching out to all possible choices guarantees that no potential solutions will be left uncovered.

• But because the target problem is usually NP-complete or even NP-hard, the solution space is often too vast to
traverse.

• The branch-and-bound algorithm handles this problem by bounding and pruning.

• Bounding refers to setting a bound on the solution quality, and pruning means trimming off branches in the
solution tree whose solution quality is estimated to be poor.
[Link]

[Link]
 • Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower
estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best
one found so far by the algorithm.

• Bounding and pruning are the essential concepts of the branch-and-bound technique, because they are used to
effectively reduce the search space.

[Link]

[Link]