Course Material

for

BECE309L-Artificial Intelligence and Machine Learning-Module-2

Module 2: Problem-solving by Searching
• Search Space –
• Search
algorithms,
strategies
• Search in
complex
environments

Source: [Link]
Terminologies Module-2; Topic-2: Search Algorithms
• Search: Searching is a step by step procedure to solve a search-problem in a given search space.
In a problem-solving context, the state space represents all possible states that a system or agent
can be in. Each state represents a particular configuration, situation, or condition.
• States: In the context of a state space, a "state" refers to a specific configuration or situation
that the problem-solving agent can occupy. States can represent a wide range of conditions,
depending on the problem..
• A search problem can have three main factors:
• Search Space: Search space represents a set of possible solutions, which a system may
have.
• Initial State: It is a state from where agent begins the search.
• Goal test/state: The desired state that the system or agent aims to reach. The goal state is
typically defined in terms of certain criteria or conditions.
• Search tree: A tree representation of search problem is called Search tree. The root of the
search tree is the root node which is corresponding to the initial state.
• Actions: It gives the description of all the available actions to the agent.
• Path: A path is a sequence of actions or operators that leads from the initial state to a particular
state in the search space.
Terminologies Module-2; Topic-2: Search Algorithms

• Transition model: A description of what each action do, can be represented as a transition
model.
• Search Algorithm: Forward state space search is guided by a search algorithm that
systematically explores the search space, searching for a solution path from the initial state to a
goal state.
• Path Cost: It is a function which assigns a numeric cost to each path.
• Solution: It is an action sequence which leads from the start node to the goal node.
• Optimal Solution: If a solution has the lowest cost among all solutions.
• Heuristic Functions: Informed search algorithms may employ heuristic functions to guide the
search more efficiently by estimating the cost or distance to the goal state from a given state.
• Informed and Uninformed Search: Informed search algorithms (e.g., A*) use heuristic
information, while uninformed search algorithms (e.g., BFS, DFS) operate without heuristic
guidance.
• Complex Problem-Solving: State space search aids in solving complex problems, optimizing
processes, and improving decision-making in various real-world scenarios.
 Module-2; Topic-1: State Space
State Space
• State-space consists of all the
possible states together with
actions to solve a specific
problem.
• In the graphical representation of
state space (such as trees), the
states are represented by nodes
while the actions are represented
by arcs.
• Any state space has an initial
‘Start’ node and an ending ‘Goal’ • The path from the initial start node to the
node or multiple Goal States. final goal node is known as the ‘Solution’ for
the particular problem.
A problem may have multiple goals as well as Source:
paths. [Link]
e/state-space-search-in-artificial-intelligence
 Module-2; Topic-1: State Space
State Space
 Module-2; Topic-2: Search Algorithms
Properties of Search Algorithms
• Completeness: A search algorithm is said
to be complete if it guarantees to return a
solution if at least any solution exists for
any random input.
• Optimality: If a solution found for an
algorithm is guaranteed to be the best
solution (lowest path cost) among all other
solutions, then such a solution for is said to
be an optimal solution.
• Time Complexity: Time complexity is a
measure of time for an algorithm to
complete its task.
• Space Complexity: It is the maximum
storage space required at any point during
the search, as the complexity of the
problem.
Types of search algorithms Module-2; Topic-2: Search Algorithms

• Based on the search problems we can classify the search algorithms into
uninformed (Blind search) search and informed search (Heuristic search)
algorithms.
Uninformed/Blind Search Module-2; Topic-2: Search Algorithms

• The uninformed search does not contain any

domain knowledge such as closeness, the
location of the goal.
• It operates in a brute-force way as it only
includes information about how to traverse
the tree and how to identify leaf and goal
nodes.
• Uninformed search applies a way in which
search tree is searched without any
information about the search space like
initial state operators and test for the goal, so
it is also called blind search.
• It examines each node of the tree until it
achieves the goal node.
Source:
[Link]
s_8935/
Uninformed/Blind Search Module-2; Topic-2: Search Algorithms

Advantages of Uninformed Search Algorithms:

• Simplicity: Uninformed search algorithms can be likened to straightforward puzzle-solving
recipes. Their simplicity makes them an excellent starting point for beginners, as they don’t
involve intricate strategies or pre-existing knowledge.
• Efficiency in Simplicity: These algorithms shine when dealing with less complex problems.
They swiftly reach solutions, particularly when the search space isn’t vast or complicated.
• Versatility: Comparable to a toolkit containing various tools, uninformed search algorithms
possess the adaptability to tackle different challenges. Whether deciphering puzzles or
navigating perplexing mazes, these algorithms rise to the occasion.
Challenges of Uninformed Search Algorithms:
• Inefficiency at Times: Visualize these algorithms as explorers occasionally taking scenic
detours. In situations of complexity, these detours can slow down the search process.
• Getting Stuck: Picture a maze with concealed dead ends. Similarly, uninformed search
algorithms can become trapped where they can’t advance. It leads to moments of frustration and
inefficiency.
Breadth-first Search Module-2; Topic-2: Search Algorithms

• A strategy for traversing a tree or graph, which

searches breadthwise in a tree or graph.
• BFS algorithm starts searching from the root
node of the tree and expands all successor node
at the current level before moving to nodes of
next level.
• The breadth-first search algorithm is an
example of a general-graph search algorithm.
• Breadth-first search implemented using First-
In-First Out (FIFO) queue data structure.
• Time Complexity: Time Complexity of BFS
algorithm can be obtained by the number of
nodes traversed in BFS until the shallowest
Node. Where b: Branching factor (maximum
number of successors of any node).d: Depth
of the shallowest goal node. • Space Complexity: Space complexity of BFS
T (b) = 1+b2+b3+.......+ bd= O (bd) algorithm is given by the Memory size of frontier
which is O(bd).
Breadth-first Search Module-2; Topic-2: Search Algorithms

• Completeness: BFS is complete, which means if

the shallowest goal node is at some finite depth,
then BFS will find a solution.
• Optimality: BFS is optimal if path cost is a non-
decreasing function of the depth of the node.
Advantages:
• BFS will provide a solution if any solution exists.
• If there are more than one solutions for a given
problem, then BFS will provide the minimal
solution which requires the least number of steps.
Disadvantages:
• It requires lots of memory since each level of the
tree must be saved into memory to expand the
next level.
• BFS needs lots of time if the solution is far away
from the root node.
Breadth-first Search-Example Module-2; Topic-2: Search Algorithms

Find the route from S to G using BFS.

Step-1 Step-2

The path in the

2nd depth level
that is SBG
Source:
[Link]
le/Uninformed-Search-Strategie
Step-4 s_8935/
Step-3
Depth-first Search Module-2; Topic-2: Search Algorithms
• Depth-first search is a recursive algorithm for
traversing a tree or graph data structure, which
starts from the root node and follows each path
to its greatest depth node before moving to the
next path.
• DFS uses a stack data structure for its
implementation.
• The process of the DFS algorithm is similar to
the BFS algorithm.
• Completeness: DFS search algorithm is
complete within finite state space as it will
expand every node within a limited search tree.
Root node--->Left node ----> right nod
• Time Complexity: Time complexity of DFS will
be equivalent to the node traversed by the
• Space Complexity: DFS algorithm needs to store
algorithm. It is given by:
only single path from the root node, hence space
• T(n)= 1+ n2+ n3 +.........+ nm=O(nm)
complexity of DFS is equivalent to the size of the
• Where, m= maximum depth of any node fringe set, which is O(bm).
and this can be much larger than d
(Shallowest solution depth)
Depth-first Search Module-2; Topic-2: Search Algorithms

• Optimal: DFS search algorithm is non-

optimal, as it may generate a large number of
steps or high cost to reach to the goal node.
• Advantage:
• DFS requires very less memory as it only
needs to store a stack of the nodes on the path
from root node to the current node.
• It takes less time to reach to the goal node than
BFS algorithm (if it traverses in the right path).
• Disadvantage:
• There is the possibility that many states keep
re-occurring, and there is no guarantee of
finding the solution. Root node--->Left node ----> right nod
• DFS algorithm goes for deep down searching • Space Complexity: DFS algorithm needs to store
and sometime it may go to the infinite loop. only single path from the root node, hence space
complexity of DFS is equivalent to the size of the
fringe set, which is O(bm).
 Module-2; Topic-2: Search Algorithms
Depth-first Search-Example
Find the route from S to G using DFS.
Step-1 Step-2

The path in the

3nd depth level
that is SADG
Source:
[Link]
ninformed-Search-Strategies_8935/
Step-4 Step-3
Depth Based Vs. Breadth based Module-2; Topic-2: Search Algorithms

Source: [Link]
Uniform-cost Search Algorithm Module-2; Topic-2: Search Algorithms

• Uniform-cost search is a searching

algorithm used for traversing a weighted
tree or graph.
• This algorithm comes into play when a
different cost is available for each edge.
• The primary goal of the uniform-cost search
is to find a path to the goal node which has
the lowest cumulative cost.
• Uniform-cost search expands nodes
according to their path costs form the root
node. It can be used to solve any graph/tree
where the optimal cost is in demand.
• A uniform-cost search algorithm is
implemented by the priority queue. It gives
maximum priority to the lowest cumulative
cost.

Source: [Link]
Uniform-cost Search Algorithm Module-2; Topic-2: Search Algorithms

Algorithm
• Set a variable NODE to the initial state, i.e.,
the root node and expand it.
• After expanding the root node, select one
node having the lowest path cost and
expand it further. (Remember, the selection
of the node should give an optimal path
cost.)
• If the goal node is searched with optimal
value, return goal state, else carry on the
search.

Source: [Link]
Uniform-cost Search Algorithm Module-2; Topic-2: Search Algorithms

The performance measure of Uniform-cost search

• Completeness: It guarantees to reach the goal state.
• Optimality: It gives optimal path cost solution for
the search.
• Space and time complexity: The worst space and
time complexity of the uniform-cost search is
Let C* is Cost of the optimal solution, and ε is each
step to get closer to the goal node. Then the number of
steps is = C*/ε+1. Here we have taken +1, as we start
from state 0 and end to C*/ε.
Hence, the worst-case time complexity of Uniform-
cost search is O(b1 + [C*/ε])
The same logic is for space complexity so, the worst-
case space complexity of Uniform-cost search is
O(b1 + [C*/ε]).
Optimal: Uniform-cost search is always optimal as it only
Source: [Link]
selects a path with the lowest path cost.
search-algorithms
 Module-2; Topic-2: Search Algorithms
Depth limited search Algorithm
• A depth-limited search algorithm is similar
to depth-first search with a predetermined
limit.
• Depth-limited search can solve the drawback
of the infinite path in the Depth-first search.
• It uses LIFO (Last in First Out) order, which
is based on the stack, in order to expand the
unexpanded nodes in the search tree.
• The search proceeds to the deepest level of
the tree where it has no successors. This
search expands nodes till infinity, i.e., the
depth of the tree.
• In this algorithm, the node at the depth limit
will treat as it has no successor nodes further.

Source: [Link]
search-algorithms
 Module-2; Topic-2: Search Algorithms
Depth limited search Algorithm
• Set a variable NODE to the initial state, i.e.,
the root node.
• Set a variable GOAL which contains the
value of the goal state.
• Loop each node by traversing deeply in one
direction/path in search of the goal node.
• While performing the looping, start
removing the elements from the stack in
LIFO order.
• If the goal state is found, return goal state
otherwise backtrack to expand nodes in other
direction.
DFS works starting from the initial node A (root node)
and traversing in one direction deeply till node I and
then backtrack to B and so on. Therefore, the sequence
will be A->B->D->I->E->C->F->G.
Source: [Link]
search-algorithms
 Module-2; Topic-2: Search Algorithms
Depth limited Search Algorithm
The performance measure of DFS
• Completeness: DLS search algorithm is complete if the solution is above the depth-
limit.
• Time Complexity: Time complexity of DLS algorithm is O(bℓ).
• Space Complexity: Space complexity of DLS algorithm is O(b×ℓ).
• Optimal: Depth-limited search can be viewed as a special case of DFS, and it is also
not optimal even if ℓ>d.
• Advantages:
Depth-limited search is Memory efficient.
• Disadvantages:
• Depth-limited search also has a disadvantage of incompleteness.
• It may not be optimal if the problem has more than one solution.

Source: [Link]
Iterative Deepening First depth Search Module-2; Topic-2: Search Algorithms

• This algorithm performs depth-first search

up to a certain "depth limit", and it keeps
increasing the depth limit after each
iteration until the goal node is found.
• This Search algorithm combines the
benefits of Breadth-first search's fast
search and depth-first search's memory
efficiency.
• The iterative search algorithm is useful
uninformed search when search space is
large, and depth of goal node is unknown.
• IDS blends aspects of both BFS and DFS.
It initiates with BFS and progressively
probes deeper levels until a solution
emerges.
• While it guarantees a solution, IDS might
not be as efficient as pure BFS or DFS.
Source: [Link]
Iterative Deepening First depth Search Module-2; Topic-2: Search Algorithms

• The performance measure of Iterative

deepening search
• Completeness: Iterative deepening
search may or may not reach the goal
state.
• Optimality: It does not give an optimal
solution always.
• Space Complexity: It has the same
space complexity as BFS, i.e., O(bd).
• Time Complexity: It has O(d) time
complexity.
• Disadvantages of Iterative deepening
search
• The drawback of iterative deepening
search is that it seems wasteful because it
generates states multiple times.

Source: [Link]
Bidirectional Search Algorithm Module-2; Topic-2: Search Algorithms

• Bidirectional search algorithm runs

two simultaneous searches, one form
initial state called as forward-search
and other from goal node called as
backward-search, to find the goal
node.
• Bidirectional search replaces one
single search graph with two small
subgraphs in which one starts the
search from an initial vertex and other
starts from goal vertex.
• The search stops when these two
graphs intersect each other.
• Bidirectional search can use search
techniques such as BFS, DFS, DLS,
etc.

Source: [Link]
Bidirectional Search Algorithm Module-2; Topic-2: Search Algorithms

• Completeness: Bidirectional Search is

complete if we use BFS in both searches.
• Time Complexity: Time complexity of
bidirectional search using BFS is O(bd).
• Space Complexity: Space complexity of
bidirectional search is O(bd).
• Optimal: Bidirectional search is Optimal.
• Advantages:
• Bidirectional search is fast.
• Bidirectional search requires less memory
• Disadvantages:
• Implementation of the bidirectional search tree
is difficult.
• In bidirectional search, one should know the
goal state in advance.
Source: [Link]
A comparative analysis on uninformed Module-2; Topic-2: Search Algorithms
(Blind search) search

Source: [Link]
Informed Search/ Heuristic Search in AI Module-2; Topic-2: Search Algorithms
• Informed search algorithm contains an array of
knowledge such as how far we are from the goal, path
cost, how to reach to goal node, etc.
• Heuristic is a function which is used in Informed Search,
and it finds the most promising path. Heuristic function
estimates how close a state is to the goal.
• Heuristic function is represented by h(n), and it
calculates the cost of an optimal path between the pair of
states.
• It takes the current state of the agent as its input and
produces the estimation of how close agent is from the goal.
• The heuristic method, however, might not always give the
best solution, but it guaranteed to find a good solution in
reasonable time.
Heuristic function
Best-first Search (Greedy search) Module-2; Topic-2: Search Algorithms

• Set an OPEN list and a CLOSE list where the

OPEN list contains visited but unexpanded
nodes and the CLOSE list contains visited as
well as expanded nodes.
• Initially, traverse the root node and visit its next
successor nodes and place them in the OPEN
list in ascending order of their heuristic value.
• Select the first successor node from the OPEN
list with the lowest heuristic value and expand
further.
• Now, rearrange all the remaining unexpanded
nodes in the OPEN list and repeat above two
steps.
• If the goal node is reached, terminate the
search, else expand further.
Best-first Search (Greedy search) Module-2; Topic-2: Search Algorithms

The performance measure of Best-first search

Algorithm:
• Completeness: Best-first search is incomplete even in
finite state space.
• Optimality: It does not provide an optimal solution.
• Time and Space complexity: It has O(bm) worst time
and space complexity, where m is the maximum
depth of the search tree. If the quality of the heuristic
function is good, the complexities could be reduced
substantially.
Disadvantages of Best-first search
• BFS does not guarantees to reach the goal state.
• Since the best-first search is a greedy approach, it does
not give an optimized solution.
• It may cover a long distance in some cases.
 Module-2; Topic-2: Search Algorithms
A* Search Algorithm
• A* search is the most widely used
informed search algorithm where a node
n is evaluated by combining values of the
functions g(n)and h(n).
• The function g(n) is the path cost from
the start/initial node to a node n and h(n)
is the estimated cost of the cheapest path
from node n to the goal node.

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

• where f(n) is the estimated cost of the

cheapest solution through n.
 Module-2; Topic-2: Search Algorithms
A* Search Algorithm
• A* search finds an optimal solution as it has
the admissible heuristic function h(n) which
believes that the cost of solving a problem is
less than its actual cost.
• A heuristic function can
either underestimate or overestimate the cost
required to reach the goal node.
• But an admissible heuristic function never
overestimates the cost value required to reach
the goal state.

h(n) is the actual heuristic cost value and h’(n) is the estimated heuristic cost value.
 Module-2; Topic-2: Search Algorithms
A* Search Algorithm
S is the root node, and G is the goal node.
Starting from the root node S and moving
towards its next successive nodes A and B. In
order to reach the goal node G, calculate the f(n)
value of node S, A and B using the evaluation
equation i.e.
f(n)=g(n)+h(n)
Calculation of f(n) for node S:
f(S)=(distance from node S to S) + h(S)
0+10=10.
Calculation of f(n) for node A:
f(A)=(distance from node S to A)+h(A)
2+12=14
Calculation of f(n) for node B:
Therefore, node A has the lowest f(n) value. Hence, node A will
f(B)=(distance from node S to B)+h(B) be explored to its next level nodes C and D and again calculate
3+14=17 the lowest f(n) value. After calculating, the sequence we get
is S->A->D->G with f(n)=13(lowest value).
 Module-2; Topic-2: Search Algorithms
A* Search Algorithm
• Struct Node: This defines a nodestructure that represents a
grid cell. It contains the x and y coordinates of the node, the
cost g from the starting node to that node, the heuristic value
h (estimated cost from that node to the destination node),
and a pointer to the starting node of the path.
• Calculate heuristic: This function calculates a heuristic
using the Euclidean distance between a node and the target
• AStarSearch: This function runs the A* search algorithm. It
takes the start and destination coordinates, a grid, and returns
a vector of pairs representing the coordinates of the shortest
path from start to finish.
• Primary: The program's main function takes input grids,
origin, and target coordinates from the user. It then calls
AStarSearch to find the shortest path and prints the result.
 Module-2; Topic-2: Search Algorithms
A* Search Algorithm
• The performance measure of A* search
• Completeness: The star(*) in A* search
guarantees to reach the goal node.
• Optimality: An underestimated cost will
always give an optimal solution.
• Space and time complexity: A* search has
O(bd) space and time complexities.
Advantage of A* search
• A* is efficient if an efficient and acceptable
heuristic function is used.
• A* can be used to find optimal solutions
efficiently as long as a meaningful heuristic
can be defined.
Disadvantage of A* search
• A* mostly runs out of space for a long
period.
 Module-2; Topic-2: Search Algorithms
A* Search Algorithm-Applications
• Pathfinding in Games: A* is often used in video games for character movement, enemy
AI navigation, and finding the shortest path from one location to another on the game
map. Robotics and Autonomous Vehicles: A* is used in robotics and autonomous
vehicle navigation to plan anoptimal route for robots to reach a destination, avoiding
obstacles and considering terrain costs. This is crucial for efficient and safe movement in
natural environments.
• Maze solving: A* can efficiently find the shortest path through a maze, making it
valuable in many maze-solving applications, such as solving puzzles or navigating
complex structures.
• Route planning and navigation: In GPS systems and mapping applications, A* can be
used to find the optimal route between two points on a map, considering factors such as
distance, traffic conditions, and road network topology.
• Puzzle-solving: A* can solve various diagram puzzles, such as sliding puzzles, Sudoku,
and the 8-puzzle problem. Resource Allocation: In scenarios where resources must be
optimally allocated, A* can help find the most efficient allocation path, minimizing cost
and maximizing efficiency.
 Module-2; Topic-2: Search Algorithms
A* Search Algorithm-Applications
• Network Routing: A* can be used in computer networks to find the most efficient
route for data packets from a source to a destination node.
• Natural Language Processing (NLP): In some NLP tasks, A* can generate
coherent and contextualresponses by searching for possible word sequences based on
their likelihood and relevance.
• Path planning in robotics: A* can be used to plan the path of a robot from one
point to another, considering various constraints, such as avoiding obstacles or
minimizing energy consumption.
• Game AI: A* is also used to makeintelligent decisions for non-player characters
(NPCs), such as determining the best way to reach an objective or coordinate
movements in a team-based game.

Source: [Link]
 Module-2; Topic-3: Search in Complex Environments
Search in Complex Environments
• In search algorithm, When a goal is found, the
path to that goal constitutes a solution to the
problem.
• However, in many problems, the path to the goal
is irrelevant; the goal state itself is the solution.
• Local search algorithms operate by searching
from a start state to neighboring states, without
keeping track of the paths, nor the set of states
that have been reached. Local search algorithms
can also solve optimization problems, in which
the aim is to find the best state according to an
objective function.
• They are not systematic – they might never
explore a portion of the search space where a
solution actually resides.
• Two advantages-Use very little memory, and
Often find reasonable solutions in large or
infinite state spaces (systematic algorithms may
be unsuitable). Source: [Link]
 Module-2; Topic-3: Search in Complex Environments
Different regions in the State
Space Diagram
• Local maximum: It is a state which is better
than its neighboring state however there
exists a state which is better than it(global
maximum). This state is better because here
the value of the objective function is higher
than its neighbors.
• Global maximum: It is the best possible
state in the state space diagram. This is
because, at this stage, the objective function
has the highest value.
• Current state: The region of the state space
• Plateau/flat local maximum: It is a flat
diagram where we are currently present during
region of state space where neighboring the search.
states have the same value. • Shoulder: It is a plateau that has an uphill edge.
• Ridge: It is a region that is higher than its
neighbors but itself has a slope. It is a special
kind of local maximum. Source: [Link]
 Module-2; Topic-3: Search in Complex Environments
Hill Climbing search algorithm
• In Hill Climbing, the algorithm starts with an initial
solution and then iteratively makes small changes to
it in order to improve the solution.
• Hill-climbing search keeps track of one current state
and on each iteration moves to the neighboring state
with highest value—that is, it heads in the direction
that provides the steepest ascent.
• These changes are based on a heuristic function that
evaluates the quality of the solution. The algorithm
continues to make these small changes until it
reaches a local maximum, meaning that no further
improvement can be made with the current set of
moves.
• It terminates when it reaches a “peak” where no • Note that one way to use hill-climbing search is
neighbor has a higher value. to use the negative of a heuristic cost function as
• Hill climbing does not look ahead beyond the the objective function; that will climb locally to
the state with smallest heuristic distance to the
immediate neighbors of the current state.
goal.
Source: [Link]
 Module-2; Topic-3: Search in Complex Environments
Hill Climbing search algorithm
Key Features:
• Generate and Test Approach: This feature involves
generating neighboring solutions and evaluating their
effectiveness, always aiming for an upward move in
the solution space.
• Greedy Local Search: The algorithm uses a cheap
strategy, opting for immediate beneficial moves that
promise local improvements.
• No Backtracking: Unlike other algorithms, Hill
Climbing Algorithm in AI does not revisit or
reconsider previous decisions, persistently moving
forward in the quest for the optimal solution.

Source: [Link]
 Module-2; Topic-3: Search in Complex Environments
Hill Climbing search algorithm
Advantages of Hill Climbing algorithm:
• Hill Climbing is a simple and intuitive algorithm that is easy to understand and implement.
• It can be used in a wide variety of optimization problems, including those with a large search
space and complex constraints.
• Hill Climbing is often very efficient in finding local optima, making it a good choice for problems
where a good solution is needed quickly.
• The algorithm can be easily modified and extended to include additional heuristics or constraints.
Disadvantages of Hill Climbing algorithm:
• Hill Climbing can get stuck in local optima, meaning that it may not find the global optimum of
the problem.
• The algorithm is sensitive to the choice of initial solution, and a poor initial solution may result in
a poor final solution.
• Hill Climbing does not explore the search space very thoroughly, which can limit its ability to find
better solutions.
• It may be less effective than other optimization algorithms, such as genetic algorithms or
simulated annealing, for certain types of problems.
Source: [Link]
 Module-2; Topic-3: Search in Complex Environments
Simple Hill Climbing
• Simple hill climbing is the simplest way to implement a
hill climbing algorithm.
• Evaluate the initial state. If it is a goal state then stop and
return success. Otherwise, make the initial state as the
current state.
• Loop until the solution state is found or there are no new
operators present which can be applied to the current
state.
• Select a state that has not been yet applied to the
current state and apply it to produce a new state.
• Perform these to evaluate the new state. • The search algorithm only evaluates the neighbor node
• If the current state is a goal state, then stop and state at a time and selects the first one which optimizes
return success. current cost and set it as a current state. It only checks
• If it is better than the current state, then make it it's one successor state, and if it finds better than the
the current state and proceed further. current state, then move else be in the same state.
• If it is not better than the current state, then The features are
• Less time consuming
continue in the loop until a solution is found. •
Less optimal solution and the solution is not guaranteed
• Exit from the function.
Source: [Link]
Steepest-Ascent hill climbing Module-2; Topic-3: Search in Complex Environments
• The steepest-Ascent algorithm is a variation of simple
hill climbing algorithm.
• This algorithm examines all the neighboring nodes of the
current state and selects one neighbor node which is
closest to the goal state.
• Step 1: Evaluate the initial state, if it is goal state then
return success and stop, else make current state as initial
state.
• Step 2: Loop until a solution is found or the current state
does not change.
• Let SUCC be a state such that any successor of the
current state will be better than it.
• For each operator that applies to the current state:
• Apply the new operator and generate a new state.
• Evaluate the new state.
• If it is goal state, then return it and quit, else compare it
to the SUCC.
• If it is better than SUCC, then set new state as SUCC.
• If the SUCC is better than the current state, then set
current state to SUCC.
• Step 5: Exit. Source: [Link]
 Module-2; Topic-3: Search in Complex Environments
Stochastic hill climbing
• It does not examine all the neighboring nodes before deciding which
node to select. It just selects a neighboring node at random and
decides (based on the amount of improvement in that neighbor)
whether to move to that neighbor or to examine another.
Algorithm
• Evaluate the initial state. If it is a goal state then stop and return
success. Otherwise, make the initial state the current state.
Repeat these steps until a solution is found or the current state does not
change.
Select a state that has not been yet applied to the current state.
Apply the successor function to the current state and generate all
the neighbor states.
Among the generated neighbor states which are better than the
current state choose a state randomly (or based on some
probability function).
If the chosen state is the goal state, then return success, else make
it the current state and repeat step 2 of the second point.
Exit from the function.
Source: [Link]
 Module-2; Topic-3: Search in Complex Environments
Problems in different regions in
Hill climbing
1. Local Maximum: A local maximum is a peak state in the landscape
which is better than each of its neighboring states, but there is another state
also present which is higher than the local maximum.
Solution: Backtracking technique can be a solution of the local maximum
in state space landscape. Create a list of the promising path so that the
algorithm can backtrack the search space and explore other paths as well.
2. Plateau: A plateau is the flat area of the search space in which all the
neighbor states of the current state contains the same value, because of this
algorithm does not find any best direction to move. A hill-climbing search
might be lost in the plateau area.
Solution: The solution for the plateau is to take big steps or very little
steps while searching, to solve the problem. Randomly select a state which
is far away from the current state so it is possible that the algorithm could
find non-plateau region.
3. Ridges: A ridge is a special form of the local maximum. It has an area
which is higher than its surrounding areas, but itself has a slope, and
cannot be reached in a single move.
Solution: With the use of bidirectional search, or by moving in different
directions, we can improve this problem.
Source: [Link]
Simulated Annealing Module-2; Topic-3: Search in Complex Environments

• A hill-climbing algorithm which

never makes a move towards a lower
value guaranteed to be incomplete
because it can get stuck on a local
maximum.
• And if algorithm applies a random
walk, by moving a successor, then it
may complete but not efficient.
Simulated Annealing is an algorithm
which yields both efficiency and
completeness.
• In mechanical term Annealing is a
• The same process is used in simulated annealing in which the
process of hardening a metal or glass algorithm picks a random move, instead of picking the best
to a high temperature then cooling move. If the random move improves the state, then it follows
gradually, so this allows the metal to the same path. Otherwise, the algorithm follows the path which
reach a low-energy crystalline state. has a probability of less than 1 or it moves downhill and
chooses another path.
Source: [Link]
Simulated Annealing Module-2; Topic-3: Search in Complex Environments

• Combine hill climbing with a random walk

that yields both efficiency and
completeness.
• In metallurgy, 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.
• Consider gradient descent, Getting a ping- • The simulated-annealing-Start by shaking hard
pong ball into the deepest crevice in a and then gradually reduce the intensity of the
bumpy surface. shaking.
• If we let the ball roll, it will come to rest at • Quite similar to hill climbing.
a local minimum. • Instead of picking the best move, however it picks
• If we shake surface, we can bounce the ball a random move.
out of the local minimum. • If the move improves the situation, it is always
accepted. Otherwise, the algorithm accepts the
move with some probability less than 1
Source: [Link]
Local Beam Search Module-2; Topic-3: Search in Complex Environments

• It keeps track of k states rather than just one.

• It begins with k randomly generated states.
• At each step, all the successor 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.
• Differ from random restart searchRandom restart runs
independently.
• In local beam search, useful information is passed among
the parallel search threadsProblems“Come over here, the
grass is greener!”
• Lack of diversity among the k states.
• Stochastic beam search helps alleviate this problemChoose
k successors at random, with the probability of choosing a
given successor being an increasing function of its
[Link] to the process of natural
selection“Successors” (offspring) of a “state” (organism)
populate the next generation according to its “value”
(fitness)
Source: [Link]
Conclusion Module-2-Conclusion
• Search Space: In AI, the search space encompasses all possible states or configurations that can
be explored to find a solution to a problem.
• Operators: Operators define how the agent transitions between states within the state space. They
represent actions or movements that lead to new states.
• Each state represents a configuration of the problem, and the search process involves navigating
through this space to identify a goal state.
• Search in Complex Environments: Complex environments often feature high-dimensional spaces,
dynamic changes, or partially observable states.
• Key considerations include: State Representation: Efficiently representing states can
significantly impact search performance.
• Heuristic Functions: Designing effective heuristics is crucial for guiding informed search
algorithms. Good heuristics can dramatically reduce search time.
• Search Space Pruning: Techniques like alpha-beta pruning in game theory help eliminate
unnecessary parts of the search space, optimizing search processes.
• Handling Uncertainty: In environments with uncertainty, approaches like Monte Carlo Tree
Search (MCTS) and Partially Observable Markov Decision Processes (POMDPs) are employed to
make decisions based on probabilistic models.
 Module-2-Conclusion
Conclusion
• Problem-solving in AI through searching involves navigating a vast search space to find optimal
solutions efficiently.
• Search Strategies: Different search strategies, such as breadth-first search (BFS), depth-first
search (DFS), and A*, guide the exploration of state spaces. Each strategy has its advantages
and limitations.
• Informed and Uninformed Search: Informed search algorithms (e.g., A*) use heuristic
information, while uninformed search algorithms (e.g., BFS, DFS) operate without heuristic
—is crucial for tackling different problems.
• Heuristics: Heuristic functions estimate the cost from a state to the goal, providing guidance to
informed search algorithms like A*. A good heuristic can significantly enhance search
efficiency. In complex environments, effective state representation, heuristic design, and search
space pruning are vital for enhancing performance.
• Effective problem-solving in AI relies on understanding the search space and selecting
appropriate search algorithms and strategies tailored to the specific challenges of the
environment. Balancing between exploration and exploitation, along with leveraging heuristics,
is key to achieving efficient search outcomes in complex scenarios.
• Complex Problem-Solving: State space search aids in solving complex problems, optimizing
processes, and improving decision-making in various real-world scenarios.
 Module-2-Conclusion
Conclusion
Conclusion Module-2-Conclusion
Search Algorithms and Strategies

Breadth-first search (BFS), Depth-first search (DFS), Depth limited search(DLS), Iterative
Deepening First depth Search(IDS), Bidirectional Search Algorithm(BDS), Uniform-cost Search
(UCS)
Conclusion Module-2-Conclusion

Search in Complex Environment

• Hill Climbing can be useful in a variety of optimization problems, such as scheduling,
route planning, and resource allocation.
• However, it has some limitations, such as the tendency to get stuck in local maxima
and the lack of diversity in the search space.
• Therefore, it is often combined with other optimization techniques, such as genetic
algorithms or simulated annealing, to overcome these limitations and improve the
search results.