17-06-2025
Searching Techniques
Dr. Ganapathy S
[World Top 2% Scientist]
Associate Professor
Dept. of Computer Science and Engineering Education,
National Institute of Technical Teachers Training & Research (NITTTR),
(Deemed to be University under distinct category)
Bhopal, MP – 462 002.
sganapathy@[Link], [Link]@[Link]
Session Outcomes
End of the session, the learners are able to:
• Explain the process of A* Algorithm
• Explain the process of Constraint Satisfaction Problem (CSP) Algorithm
• Explain the process of Mean End Analysis Algorithm
• Explain the process of Minimax Algorithm
• Explain the process of Alpha-Beta Pruning Algorithm
1
17-06-2025
A* Algorithm
A* Search Algorithm
• This is informed search technique also called as Heuristic
search.
• It works based on heuristic value and path cost value.
• It uses h(n) – Heuristic value [cost of the cheapest path
from node ‘n’ to the goal node] & g(n) – Path cost [Cost to
reach the node ‘n’]
• Find shortest path through search spaces.
• Estimated cost f(n) = g(n)+h(n)
• It gives fast and optimal results as compared with previous
algorithms.
2
17-06-2025
Why A* Algorithm?
• It is simple and efficient search algorithm which is useful for
finding the optimal solution quickly.
• It is used to find shortest path.
• It is an extension of Diikstra’s shortest path algorithm.
• The extension here is that, instead of using priority queue
to store all the elements, we use heaps (binary trees) to
store them.
• It uses heuristic function for providing additional
information.
A* Search Algorithm
• Algorithm:
• The implementation of A* algorithm is maintaining two lists
as OPEN and CLOSED.
• OPEN contains those nodes that have been evaluated by
the heuristic function but have not been expanded into
successors yet.
• CLOSED contains those nodes that have already been
visited.
3
17-06-2025
A* Search Algorithm
• STEP 1:
• Define a list OPEN
• Initially, OPEN consists solely of a single node, the start node S.
• STEP 2:
• If the list is empty, return failure and exit.
• STEP 3:
• Remove node n with smallest value of f(n) from OPEN and
move it to list CLOSED.
• If node n is a goal state, return success and exit.
• STEP 4:
• Expand node n
A* Search Algorithm
• STEP 5:
• If any successor to n is the goal node, return success and the
solution by tracing the path from goal node to S.
• Otherwise, Go to step 6.
• STEP 6:
• For each successor node,
• Apply the evaluation function f to the node.
• If the node has not been in either list, add it to OPEN.
• STEP 7:
• Go back to step 2.
4
17-06-2025
A* Search Algorithm – An Example
A* Search Algorithm – An Example
5
17-06-2025
A* Search Algorithm – An Example
A* Search Algorithm – An Example
6
17-06-2025
A* Search Algorithm – An Example
Advantages of A*Algorithm
• To find optimal path
• To handle large search spaces
• Tailored to accommodate different problem domains and
heuristics.
• It is flexible and adoptable to varying terrain consts and
constraints.
• It is widely implemented and has a vast amount of
resources and support available.
7
17-06-2025
Disadvantages of A*Algorithm
• Computationally expensive in certain scenarios when
search space is extensive and the number of possible paths
is large.
• It consumes more memory and resources for processing.
• It relies on the quality of the heuristic function. If the
heuristic is poorly designed or does not estimate the
distance to the goal, the optimality will be compromised.
• It struggle with certain types of graphs or search spaces
that exhibit irregular or unpredictable structures.
Applications of A*Algorithm
• In ROBOTICS, it helps robots navigate obstacles and find
optimal paths.
• In VIDEO GAMES, it enables NPCs to navigate game
environments intelligently.
• In ROUTE PLANNING APPLICATIONS, it is used to find the
shortest or fastest routes between locations.
• In LOGISTIC INDUSTRIES, it is used to route and schedule
the vehicles.
• In AI SYSTEMS, used to optimize the decision making
process on NLP and ML.
8
17-06-2025
Constraint Satisfaction
Problem (CSP)
Constraint Satisfaction Problem(CSP)
• Constraint Satisfaction Problems (CSPs) are a class of
computational problems where the goal is to find a solution
that satisfies a set of constraints.
• These constraints impose restrictions on the values or
assignments of variables in such a way that the variables
must be assigned values from their respective domains
while meeting all specified conditions.
• Key elements: Variables, Domains and Constraints
9
17-06-2025
Constraint Satisfaction Problem(CSP)
• Real-world examples of CSPs:
• Sudoku Puzzles: Variables are the empty cells, the domains are
numbers from 1 to 9, and the constraints ensure that no
number is repeated in a row, column or 3X3 subgrid.
• Scheduling Problems: Variables must represent classes,
domains represent time slots, and constraints ensure that
classes with overlapping students or instructors cannot be
scheduled simultaneously.
• Map coloring: Variables represent regions or countries, domains
represent available colors, and constraints ensure that adjacent
regions must have different colors.
Constraint Satisfaction Problem(CSP)
• Types of CSPs:
• Binary CSPs: Two variables only involve at a time. It is simpler to
represent and solve. It is visualized as graph, where the nodes &
edges considered variables and constraints. Ex) Map-coloring
problem
• Non-Binary CSPs: Three or more variables will involve at a time. It is
complex to solve. Ex) Scheduling
• Dynamic CSPs: It evolves over time as new variables or constraints
are added or removed. To resolve real world problems. Ex) Adaptive
Scheduling in logistic
• Fuzzy CSPs: Degrees of satisfaction rather than being strictly
satisfied or violated. Take suitable recommendations. Ex) Product
recommendation based on user preferences.
10
17-06-2025
Constraint Satisfaction Problem(CSP)
• Benefits of CSPs in AI:
• Structured Problem Representation
• CSPs provide a systematic way to represent problems using variables, domains
and constraints.
• This structured approach makes it easier to understand and model real-world
problems like scheduling, resource allocation and planning.
• Versatility
• Highly versatile and can model a wide range of problems across diverse
domains such as scheduling, logistics, configuration and game playing.
• Extension like soft constraints and multi-objective optimization enhance
their applicability.
• Efficient Solving Techniques
• CSP algorithms (e.g., backtracking, forward checking and constraint
propagation) are designed to exploit the structure of problems, leading to
more efficient solutions than brute-force methods.
• Heuristics (e.g., Most constrained variable) further improve performance.
Constraint Satisfaction Problem(CSP)
• Benefits of CSPs in AI:
• Reusability
• CSP frameworks and solvers are reusable across multiple
applications. For example, a scheduling CSP solver can be
adopted for timetabling or resource allocation with minimal
changes.
• Declarative Problem Solving
• CSPs separate the problem definition (constraints and variables)
from the solving mechanism. This declarative approach simplifies
problem-solving and allows focus on the problem rather than
the algorithm.
11
17-06-2025
Constraint Satisfaction Problem(CSP)
• Challenges of CSPs in AI:
• Scalability
• CSPs struggle with large-scale problems due to combinatorial explosion.
• As the number of variables and constraints increases, the search space grows
exponentially, making solving intractable for very large CSPs.
• Dynamic and Evolving Problems
• Many real-world problems are dynamic, where constraints or variables change
over time.
• Standard CSP solvers are not inherently equipped to handle dynamic constraints
without significant modifications.
• Over-Constrained Problems
• In scenarios where no feasible solution exists (over-constrained problems), finding
acceptable compromises can be computationally expensive.
Constraint Satisfaction Problem(CSP)
• Challenges of CSPs in AI:
• Domain Size
• CSP performance heavily depends on domain size. Larger domains increase
the complexity of constraint checking and propagation.
• For example, in scheduling, a large number of time slots or tasks can make
the problem unwieldy.
• Constraint Interaction
• When constraints interact in complex ways, it becomes difficult to detect
and resolve conflicts efficiently.
• Highly interdependent constraints can lead to computational bottlenecks.
• Solver Limitations
• Existing CSP solvers may not always support specific types of constraints or
extensions (e.g., fuzzy or probabilistic constraints).
• Customization often requires significant effort and expertise.
12
17-06-2025
Constraint Satisfaction Problem(CSP)
Constraint Satisfaction Problem(CSP)
• Rules for Crypt Arithmatic Problem:
1. Digit ranges from 0 to 9 only.
2. Each variable should have unique and distinct value.
3. Each letter symbol represents only one digit throughout the problem.
4. You have to find the value of letter in the CSP.
5. There must be only one solution to the problem.
6. The numerical base unless specifically stated is 10.
7. Numbers must not begin with zero. For ex.: 0123 (wrong) & 123 (Right)
13
17-06-2025
Constraint Satisfaction Problem(CSP)
Constraint Satisfaction Problem(CSP)
14
17-06-2025
Constraint Satisfaction Problem(CSP) – An Example
Constraint Satisfaction Problem(CSP) – An Example
15
17-06-2025
Means End Analysis(MEA)
Means End Analysis (MEA)
• It is a mixture of Backward and forward search technique.
• The MEA analysis process centered on the evaluation of the
difference between the current state and goal state.
• 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.
16
17-06-2025
Means End Analysis (MEA)
• The means-ends analysis process can be applied recursively
for a problem. It is a strategy to control search in problem-
solving.
• First, evaluate the difference between initial state and final
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.
Means End Analysis (MEA)
• Operator Subgoaling
• 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.
17
17-06-2025
Means End Analysis (MEA)
• Algorithm for Means-Ends-Analysis:
• Step 1: Compare CURRENT to GOAL, if there are no
difference between both then return Success and Exit.
• Step 2: Else, select the most significant difference and
reduce it by doing the following steps until the success or
failure occurs.
• a. Select a new operator O which is applicable for the
current difference, and if there is no such operator, then
signal failure.
Means End Analysis (MEA)
• Algorithm for Means-Ends Analysis:
• Attempt to apply operator O to CURRENT. Make a
description of two states.
• i) O-Start, a state in which O’s preconditions are satisfied.
• Ii) O-Result, the state that would result if O were applied in O-
Start.
18
17-06-2025
Means End Analysis (MEA)
• If (First-Part <--- MEA (CURRENT, O-START) AND
(LAST-Part <--- MEA (O-Result, GOAL), are successful,
then
signal Success and return the result of combining FIRST-
PART, O, and LAST-PART.
Means End Analysis (MEA) - An Example
19
17-06-2025
Means End Analysis (MEA) - An Example
Evaluating the initial state: In the first step, we will evaluate the
initial state and will compare the initial and goal state to find the
differences between both states.
Means End Analysis (MEA) - An Example
Applying Delete Operator: As we can check the first difference 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.
20
17-06-2025
Means End Analysis (MEA) - An Example
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 square is outside the circle, so, we will apply the Move
Operator.
Means End Analysis (MEA) - An Example
Applying Expand Operator: Now a new state is generated in the
third step, and we will again compare with goal state.
After comparing the states there is still one difference which is the
size of the square, so, we will apply Expand Operator, and finally, it
will generate the goal state.
21
17-06-2025
Minimax Algorithm
Introduction to Game Playing
• Game Playing is an important domain of artificial intelligence.
• Games don’t require much knowledge; the only knowledge we
need to provide is the rules, legal moves and the conditions of
winning or losing the game.
• Both players try to win the game.
• So, both of them try to make the best move possible at each
turn.
• Searching techniques like BFS(Breadth First Search) are not
accurate for this as the branching factor is very high, so searching
will take a lot of time.
22
17-06-2025
Introduction to Game Playing
• So, we need another search procedures that improve –
- Generate procedure so that only good moves are generated.
- Test procedure so that the best move can be explored first.
• The most common search technique in game playing is Minimax
search procedure.
• It is depth-first depth-limited search procedure. It is used for
games like chess and tic-tac-toe.
Minimax Search Algorithm
• It is a backtracking algorithm
• It is used in game theory to find the optical move for a player.
• Two players:
i) Maximizer: Tries to maximize the score
ii) Minimizer: Tries to minimize the score
• It is used in board games like chess, tic-tac-toe and Checkers.
• It is used in decision making in AI agents for competitive scenarios.
23
17-06-2025
Minimax Search Algorithm – An Example
Minimax Search Algorithm – An Example
24
17-06-2025
Minimax Search Algorithm – An Example
Minimax Search Algorithm
• Advantages:
• Optimal decisions: Ensures the best move is made if both players play
optimally.
• Conceptually easy to understand and implement.
• Disadvantages:
• Limited to two player games.
• Time complexity 𝑂(𝑏 ) grows exponentially with depth.
25
17-06-2025
Alpha-Beta Pruning
Algorithm
Alpha-Beta Pruning Algorithm
• It is an optimization technique used in the Minimax algorithm for
decision making in game theory.
• It helps reduce the number of nodes evaluated by the algorithm,
making it more efficient.
• Components:
• Alpha : The best value that the maximizing player can guarantee so far. It is initially
set to negative infinity.
• Beta: The best value that the minimizing player can guarantee so far. It is initially
set to positive infinity.
26
17-06-2025
Alpha-Beta Pruning Algorithm
• Alpha Beta Pruning eliminates branches of the game tree that do
not need to be explored because they cannot affect the final
decision.
• It speeds up the minmax algorithm by “pruning” away
unnecessary parts of the search tree.
Alpha-Beta Pruning Algorithm- An Example
27
17-06-2025
Alpha-Beta Pruning Algorithm- An Example
Alpha-Beta Pruning Algorithm- An Example
28
17-06-2025
Alpha-Beta Pruning Algorithm
• In the best case, Alpha-Beta pruning can reduce the time
complexity of the Minimax algorithm from
𝑂(𝑏 ) to 𝑂(𝑏 / )
where, b is the branching factor and d is the depth of the
tree.
Thank You
29