ARTIFICIAL INTELLIGENCE

Class notes

The 8 puzzle problem solution is covered in this article. A 3 by 3 board with 8 tiles (each tile has a number from 1
to 8) and a single empty space is provided. The goal is to use the vacant space to arrange the numbers on the
tiles such that they match the final arrangement. Four neighbouring (left, right, above, and below) tiles can be moved
into the available area.

In this solution, further movements might not always send us closer to the objective, but rather further away.
Regardless of the initial state, the state-space tree searches down the leftmost route from the root. With this
method, an answer node might never be discovered.

We can search the state space tree using a breadth-first approach. It always locates the goal state that is closest to
the root. However, the algorithm tries the same series of movements as DFS regardless of the initial state.
The route taken by the aforementioned algorithm to arrive at the final configuration of the 8-Puzzle from the starting
configuration supplied is shown in the diagram below. Keep in mind that only nodes with the lowest costs
function value are extended.

We suppose that it will costs one unit to move a tile in any direction. In light of this, we create the following costs
function for the 8-puzzle algorithm:

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Bidirectional Search
Bidirectional search is a graph search algorithm which find smallest path from source to goal vertex. It runs
two simultaneous search ----
1. Forward search from source/initial vertex toward goal vertex
2. Backward search from goal/target vertex toward source vertex
Bidirectional search replaces single search graph (which is likely to grow exponentially) with two smaller
sub graphs -- one starting from initial vertex and other starting from goal vertex. The search terminates
when two graphs intersect.
Bidirectional search can be guided by a heuristic estimate of remaining distance from source to goal and
vice versa for finding shortest path possible.
Consider following simple example-

Suppose we want to find if there exists a path from vertex 0 to vertex 14. Here we can execute two searches,
one from vertex 0 and other from vertex 14. When both forward and backward search meet at vertex 7, we
know that we have found a path from node 0 to 14 and search can be terminated now. We can clearly see
that we have successfully avoided unnecessary exploration.
Why bidirectional approach?
Because in many cases it is faster, it dramatically reduce the amount of required exploration.
Suppose if branching factor of tree is b and distance of goal vertex from source is d, then the normal
BFS/DFS searching complexity would be O (𝑏 𝑑 ). On the other hand, if we execute two search operation
then the complexity would be O (𝑏 𝑑/2 ) for each search and total complexity would be O (𝑏 𝑑/2 ) +𝑏 𝑑/2 )
which is far less than O (𝑏 𝑑 ).
When to use bidirectional approach?
We can consider bidirectional approach when-
1. Both initial and goal states are unique and completely defined.
2. The branching factor is exactly the same in both directions.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Performance measures

Completeness: Bidirectional search is complete if BFS is used in both searches.

Optimality: It is optimal if BFS is used for search and paths have uniform cost.
Time and Space Complexity : Time and space complexity is O (𝑏 𝑑/2 )).

Heuristic search strategies

Hill Climbing Algorithm in Artificial Intelligence
1. Hill climbing algorithm is a local search algorithm which continuously moves in the direction of
increasing elevation/value to find the peak of the mountain or best solution to the problem. It
terminates when it reaches a peak value where no neighbor has a higher value.
2. Hill climbing algorithm is a technique which is used for optimizing the mathematical problems.
One of the widely discussed examples of Hill climbing algorithm is Traveling-salesman Problem
in which we need to minimize the distance traveled by the salesman.
3. It is also called greedy local search as it only looks to its good immediate neighbor state and not
beyond that.
4. A node of hill climbing algorithm has two components which are state and value.
5. Hill Climbing is mostly used when a good heuristic is available.
6. In this algorithm, we don't need to maintain and handle the search tree or graph as it only keeps a
single current state.

Features of Hill Climbing:

Following are some main features of Hill Climbing Algorithm:
1. Generate and Test variant: Hill Climbing is the variant of Generate and Test method. The Generate
and Test method produce feedback which helps to decide which direction to move in the search
space.
2. Greedy approach: Hill-climbing algorithm search moves in the direction which optimizes the cost.
3. No backtracking: It does not backtrack the search space, as it does not remember the previous states.

State-space Diagram for Hill Climbing:

The state-space landscape is a graphical representation of the hill-climbing algorithm which is showing a
graph between various states of algorithm and Objective function/Cost.
On Y-axis we have taken the function which can be an objective function or cost function, and state-space
on the x-axis. If the function on Y-axis is cost then, the goal of search is to find the global minimum and
local minimum. If the function of Y-axis is Objective function, then the goal of the search is to find the
global maximum and local maximum.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Different regions in the state space landscape:

Local Maximum: Local maximum is a state which is better than its neighbor states, but there is also
another state which is higher than it.
Global Maximum : Global maximum is the best possible state of state space landsc ape. It has the highest
value of objective function.
Current state: It is a state in a landscape diagram where an agent is currently present.
Flat local maximum : It is a flat space in the landscape where all the neighbor states of current states
have the same value.
Shoulder: It is a plateau region which has an uphill edge.
Types of Hill Climbing Algorithm:
I. Simple hill Climbing:
II. Steepest-Ascent hill-climbing:
III. Stochastic hill Climbing:

1. Simple Hill Climbing:

Simple hill climbing is the simplest way to implement a hill climbing algorithm. It only evaluates the
neighbor node state at a time and selects the first one which optimizes current cost and set it as a
current state. It only checks it's one successor state, and if it finds better than the current state, then move
else be in the same state. This algorithm has the following features:

 Less time consuming

 Less optimal solution and the solution is not guaranteed

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Algorithm for Simple Hill Climbing:

Step 1: Evaluate the initial state, if it is goal state then return success and Stop.
Step 2: Loop Until a solution is found or there is no new operator left to apply.
Step 3: Select and apply an operator to the current state.
Step 4: Check new state:
If it is goal state, then return success and quit.
Else if it is better than the current state then assign new state as a current state.
Else if not better than the current state, then return to step2.

Step 5: Exit.

2. Steepest-Ascent hill climbing: 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. This algorithm consumes more time as it searches for
multiple neighbors

Algorithm for Steepest-Ascent hill climbing:

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.

3. Stochastic hill climbing:

Stochastic hill climbing does not examine for all its neighbor before moving. Rather, this search
algorithm selects one neighbor node at random and decides whether to choose it as a current state or
examine another state.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Problems in Hill Climbing Algorithm:

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.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Solution: With the use of bidirectional search, or by moving in different directions, we can improve this
problem.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Simulated Annealing (SA)

Hill Climbing and Simulated Annealing are both optimization algorithms used for finding
the optimal solution in a search space. However, they differ in their approach to exploring
the search space and handling local optima.
Differences Between Hill Climbing and Simulated Annealing
 Hill Climbing is like climbing a hill by always moving uphill, but it can get stuck on
small peaks (local optima).
 Simulated Annealing allows occasional downhill moves to escape local optima,
improving the chances of finding the global optimum.

Feature Hill Climbing Simulated Annealing

Iteratively moves to the best Sometimes accepts worse solutions to
Basic Idea neighboring solution. escape local optima.
Handling Local Easily gets stuck in local Uses a probability-based approach to
Optima optima. escape local optima.
Exploration vs Focuses on exploitation
Balances exploration and exploitation.
Exploitation (greedy approach).
Acceptance Only accepts moves that Accepts worse solutions with a
Criteria improve the solution. probability that decreases over time.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Feature Hill Climbing Simulated Annealing

Uses a temperature parameter that
Cooling Schedule Not applicable. decreases over time to reduce
randomness.
Fast but may not find the Slower but has a better chance of finding
Performance
global optimum. the global optimum.
Best for problems with smooth Useful for complex and rugged search
Suitability
and simple landscapes. spaces.

 Simulated Annealing simulates the annealing process used in metalworking. The algorithm
begins with a randomly generated initial solution and incrementally improves it by
accepting less desirable solutions with a certain probability. The probability of accepting a
worse solution decreases as the algorithm progresses, which enables it to escape local
optima and find the global optimum.

 Simulated annealing explores the search space and avoids local optimum by employing a
probabilistic method to accept a worse solution with a given probability. The initial
temperature, cooling schedule, and acceptance probability function are just a few of the
tuning parameters. Hill Climbing is faster, but Simulated Annealing is better at locating
the global optimum, particularly for complex issues with numerous local optima.
Simulated Annealing is inspired by annealing in metallurgy. It consists in heating the metal to a high
temperature and then slowly cooling it. In this way, the internal structure of the metal is first broken and
then very slowly "repaired". This results in a metal that has significantly better properties than at the
beginning of the process
Remember how at Hill Climbing we looked at all the neighbors and picked the best one? Simulated
annealing does the same thing, but... But with some probability, it is willing to accept a worse solution. If
we decide on a worse solution at the right moment, we can later get to a better one = get out of the local
minimum/maximum.
A Simulated annealing algorithm is a method to solve bound-constrained and unconstrained optimization
parameters models. The method is based on physical annealing and is used to minimize system energy.
In every simulated annealing example, a random new point is generated. The distance between the current
point and the new point has a basis of the probability distribution on the scale of the proportion of
temperature. The algorithm aims at all those points that minimize the objective with certain constraints and
probabilities. Those points that raise the objective are also accepted to explore all the possible solutions
instead of concentrating only on local minima.
Optimization by simulated annealing is performed by systematically decreasing the temperature and
minimizing the search’s extent.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Simulated Annealing (SA) is an effective and general form of optimization.

 It is useful in finding global optima in the presence of large numbers of local optima.
“Annealing” refers to an analogy with thermodynamics, specifically with the way that metals
cool and anneal.
 Simulated annealing uses the objective function of an optimization problem instead of the energy
of a material.

Stochastic Hill Climbing (Vs) Simulated Annealing:

A considerably upgraded version of stochastic hill-climbing is simulated annealing
Consider that you are climbing a hill and trying to find the optimal steps to reach the top. The main
difference between stochastic hill-climbing and simulated annealing is that
1. In stochastic hill-climbing steps are taken at random and the current point is replaced with a new
point provided the new point is an improvement to the previous point.
2. Whereas in simulated annealing, the search works the same way but sometimes the worse points
are also accepted to allow the algorithm to learn answers that are eventually better.
In machine learning, simulated annealing algorithm mimics this process and is used to find optimal (or most
predictive) features in the feature selection process.

Let’s now try to draw parallels between Annealing in metallurgy and Simulated annealing for Feature
selection:
In terms of feature selection,

1. Set of features represents the arrangement of molecules in the material (metal).

2. No. of Iterations represents time. Therefore, as the no. of iterations decreases temperature
decreases.
3. Change in Predictive performance between the previous and the current iteration represents the
change in material’s energy.

Algorithm
As with other optimization algorithms, we will create a random solution. However, its optimization will
consist in lowering the temperature a pre-defined number of times (n) and based on this temperature and
the generated neighbor we can accept or reject it. A simplified form of the algorithm would work like this:
1. solution = random solution
2. temperature = initial temperature
3. n times
a. neighbor_solution = neighborhood solution based on solutions
b. sneighboring_solution = is better than solution

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

i. true ⇒ solution = neighbor_solution

ii. false ⇒solution = neighbor_solution if temperature is high enough???

c. lower temperature
4. Return best solution found yet
Implementation of SA is surprisingly simple.
The algorithm is basically hill-climbing except instead of picking the best move, it picks a random move.
If the selected move improves the solution, then it is always accepted. Otherwise, the algorithm makes the
move anyway with some probability less than 1. The probability decreases exponentially with the
“badness” of the move, which is the amount delta E by which the solution is worsened (i.e., energy is
increased.)
Prob (accepting uphill move) ~ 1 – exp (delta E / kT))
A parameter T is also used to determine this probability. It is analogous to temperature in an annealing
system. At higher values of T, uphill moves are more likely to occur. As T tends to zero, they become
more and more unlikely, until the algorithm behaves more or less like hill-climbing. In a typical SA
optimization, T starts high and is gradually decreased according to an “annealing schedule”. The parameter
k is some constant that relates temperature to energy (in nature it is Boltzmann’s constant.)
Simulated annealing is typically used in discrete, but very large, configuration spaces, such as the set of
possible orders of cities in the Traveling Salesman problem and in VLSI routing. It has a broad range of
application that is still being explored.
Variants

When I studied this algorithm, it became clear that many people have a different idea of its use. Basically
there are 2 main use cases:

1. We get a neighbor with a small change and accept him with a certain probability.
2. The higher the temperature, the more significant changes w e can make in the neighbor.
Furthermore, the algorithm can vary, for example, in when we change the temperature. Someone changes
the temperature in each iteration, someone lets the algorithm cool down every n-iterations.
No one can simply say how to set the initial temperature, and no one can say how fast to let the temperature
cool down (value of α).

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Informed Search Algorithms

 So far we have talked about the uninformed search algorithms which looked through search space
for all possible solutions of the problem without having any additional knowledge about search
space.
 But 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. This knowledge help agents to explore less to the
search space and find more efficiently the goal node.
 The informed search algorithm is more useful for large search space. Informed search algorithm
uses the idea of heuristic, so it is also called Heuristic search.

Heuristics function:
Heuristic is a function which is used in Informed Search, and it finds the most promising path. 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 estimates how close a state is to the goal. It is represented
by h(n), and it calculates the cost of an optimal path between the pair of states. The value of the heuristic
function is always positive.
Admissibility of the heuristic function is given as:
h(n) <= h*(n)
Here h(n) is heuristic cost, and h*(n) is the estimated cost. Hence heuristic cost should be less than or
equal to the estimated cost.

Pure Heuristic Search:

Pure heuristic search is the simplest form of heuristic search algorithms. It expands nodes based on their
heuristic value h(n). It maintains two lists, OPEN and CLOSED list.
In the CLOSED list, it places those nodes which have already expanded and in the OPEN list, it
places nodes which have yet not been expanded.
On each iteration, each node n with the lowest heuristic value is expanded and generates all its successors
and n is placed to the closed list. The algorithm continues unit a goal state is found.
In the informed search we will discuss two main algorithms which are given below:

1) Best First Search Algorithm(Greedy search)

2) A* Search Algorithm
1) Best-first Search Algorithm (Greedy Search):
 Greedy best-first search algorithm always selects the path which appears best at that moment.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

 It is the combination of depth-first search and breadth-first search algorithms.

 It uses the heuristic function and search. Best-first search allows us to take the advantages of both
algorithms.
 With the help of best-first search, at each step, we can choose the most promising node.
 In the best first search algorithm, we expand the node which is closest to the goal node and the
closest cost is estimated by heuristic function, i.e.
f (n) = h (n).

Were, h (n) = estimated cost from node n to the goal.

g is a measure of the distance/cost to go from the initial node to the current node

h is an estimate of the distance/cost to solution from the current node.

Thus f is an estimate of how long it takes to go from the initial node to the solution.
Best-First Search Works:
 Greedy Best-First Search works by evaluating the cost of each possible path and then
expanding the path with the lowest cost. This process is repeated until the goal is reached.
 The algorithm uses a heuristic function to determine which path is the most promising.
 The heuristic function takes into account the cost of the current path and the estimated cost of
the remaining paths.
 If the cost of the current path is lower than the estimated cost of the remaining paths, then
the current path is chosen. This process is repeated until the goal is reached.
Advantages of Greedy Best-First Search:
1. Simple and Easy to Implement: Greedy Best-First Search is a relatively straightforward algorithm,
making it easy to implement.
2. Fast and Efficient: Greedy Best-First Search is a very fast algorithm, making it ideal for applications
where speed is essential.
3. Low Memory Requirements: Greedy Best-First Search requires only a small amount of memory,
making it suitable for applications with limited memory.
4. Flexible: Greedy Best-First Search can be adapted to different types of problems and can be easily
extended to more complex problems.
5. Efficiency: If the heuristic function used in Greedy Best-First Search is good to estimate, how close a
node is to the solution, this algorithm can be a very efficient and find a solution quickly, even in large
search spaces.

Disadvantages of Greedy Best-First Search:

1. Inaccurate Results: Greedy Best-First Search is not always guaranteed to find the optimal solution, as
it is only concerned with finding the most promising path.
2. Local Optima: Greedy Best-First Search can get stuck in local optima, meaning that the path chosen
may not be the best possible path.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

3. Heuristic Function: Greedy Best-First Search requires a heuristic function in order to work, which
adds complexity to the algorithm.
4. Lack of Completeness: Greedy Best-First Search is not a complete algorithm, meaning it may not
always find a solution if one is exists. This can happen if the algorithm gets stuck in a cycle or if the
search space is a too much complex.
The greedy best first algorithm is implemented by the priority queue.

Example: Consider the below search problem, and we will traverse it using greedy best-first search. At
each iteration, each node is expanded using evaluation function f (n) =h (n), which is given in the below
table.

In this search example, we are using two lists which are OPEN and CLOSED Lists. Following are the
iteration for traversing the above example.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Initialization: Open [A, B], Closed [S]

Iteration 1: Open [A], Closed [S, B] /* Remove the node n=B, from the OPEN list which has the lowest
value of h(n). i.e.= 4,
Iteration 2: Open [E, F, A], Closed [S, B] /* Remove the node n=F, from the OPEN list which has the
: Open [E, A], Closed [S, B, F]?* lowest value of h(n). i.e.= 2,
Iteration 3: Open [I, G, E, A], Closed [S, B, F]

: Open [I, E, A], Closed [S, B, F, G]

Hence the final solution path will be: S----> B----->F----> G
Time Complexity: The worst case time complexity of Greedy best first search is O (b^d).
Space Complexity: The worst case space complexity of Greedy best first search is O (b^d). Where, m is
the maximum depth of the search space.
Complete: Greedy best-first search is also incomplete, even if the given state space is finite.
Optimal: Greedy best first search algorithm is not optimal.

Best first search algorithm:

Step 1: Place the starting node into the OPEN list.
Step 2: If the OPEN list is empty, Stop and return failure.
Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n), and
places it in the CLOSED list.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Step 4: Expand the node n, and generate the successors of node n.

Step 5: Check each successor of node n, and find whether any node is a goal node or
not. If any successor node is goal node, then return success and terminate the search,
else proceed to Step 6.
Step 6: For each successor node, algorithm checks for evaluation function f(n), and
then check if the node has been in either OPEN or CLOSED list. If the node has not
been in both list, then add it to the OPEN list.

Step 7: Return to Step 2.

Advantages:
 Best first search can switch between BFS and DFS by gaining the advantages of both the
algorithms.
 This algorithm is more efficient than BFS and DFS algorithms.

Disadvantages:
 It can behave as an unguided depth-first search in the worst case scenario.
 It can get stuck in a loop as DFS.
 This algorithm is not optimal.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

2.) A* Search Algorithm:

A* search is the most commonly known form of best-first search.

 It uses heuristic function h (n), and cost to reach the node n from the start state g (n). It has combined
features of UCS and greedy best-first search, by which it solve the problem efficiently.
 A* search algorithm finds the shortest path through the search space using the heuristic function.
This search algorithm expands less search tree and provides optimal result faster.
 A* algorithm is similar to UCS except that it uses g (n) +h (n) instead of g (n). Uniform-cost
search (UCS) expands the node with lowest path cost (i.e. with the lowest g (n)), whereas best-
first search (BFS) expand the node with closest to the goal.
 In A* search algorithm, we use search heuristic as well as the cost to reach the node. Hence we
can combine both costs as following, and this sum is called as a fitness number.

At each point in the search space, only those node is expanded which have the lowest value of f(n), and
the algorithm terminates when the goal node is found.

Example:
In this example, we will traverse the given graph using the A* algorithm. The heuristic value of all states
is given in the below table so we will calculate the f(n) of each state using the formula f(n)= g(n) + h(n),
where g(n) is the cost to reach any node from start state. Here we will use OPEN and CLOSED list.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Solution:

1) Initialization: {(S, 5)}

2) Iteration1: {(S--> A, 4(1+3)), (S-->G(10+0), 10)}
3) Iteration2: {(S--> A-->C, 4(1+1+2)), (S--> A-->B, 7(1+2+4)), (S-->G, 10)}
4) Iteration3: {(S--> A-->C--->G, 6(1+1+4+0)), (S--> A-->C--->D, 11), (S--> A-->B, 7), (S-->G,
10)}
5) Iteration 4 will give the final result, as S--->A--->C--->G it provides the optimal path with cost
6.

Algorithm of A* search:

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Step1: Place the starting node in the OPEN list.

Step 2: Check if the OPEN list is empty or not, if the list is empty then return
failure and stops.
Step 3: Select the node from the OPEN list which has the smallest value of
evaluation function (g+h), if node n is goal node then return success and stop,
otherwise
Step 4: Expand node n and generate all of its successors, and put n into the
closed list. For each successor n', check whether n' is already in the OPEN or
CLOSED list, if not then compute evaluation function for n' and place into
Open list.
Step 5: Else if node n' is already in OPEN and CLOSED, then it should be
attached to the back pointer which reflects the lowest g(n') value.
Step 6: Return to Step 2.

Advantages:
1) A* search algorithm is the best algorithm than other search algorithms.
2) A* search algorithm is optimal and complete.
3) This algorithm can solve very complex problems.
Disadvantages:
1) It does not always produce the shortest path as it mostly based on heuristics and approximation.
2) A* search algorithm has some complexity issues.
3) The main drawback of A* is memory requirement as it keeps all generated nodes in the memory,
so it is not practical for various large-scale problems.
Points to remember:
I. A* algorithm returns the path which occurred first, and it does not search for all remaining paths.
II. The efficiency of A* algorithm depends on the quality of heuristic.
III. A* algorithm expands all nodes which satisfy the condition f(n)
Complete: A* algorithm is complete as long as:
I. Branching factor is finite.
II. Cost at every action is fixed.
Optimal: A* search algorithm is optimal if it follows below two conditions:
I. Admissible: the first condition requires for optimality is that h(n) should be an admissible
heuristic for A* tree search. An admissible heuristic is optimistic in nature.
II. Consistency: Second required condition is consistency for only A* graph-search.
If the heuristic function is admissible, then A* tree search will always find the least cost path.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Time Complexity: The time complexity of A* search algorithm depends on heuristic function, and the
number of nodes expanded is exponential to the depth of solution d. So the time complexity is O(b^d),
where b is the branching factor.
Space Complexity : The space complexity of A* search algorithm is O(b^d)
Best-First Search:
Best-First search is a searching algorithm used to find the shortest path which uses distance as a heuristic.
The distance between the starting node and the goal node is taken as heuristics. It defines the evaluation
function for each node n in the graph as f(n) = h(n) where h(n) is heuristics function.
A*Search:
A*search is a searching algorithm used to find the shortest path which calculates the cost of all its
neighboring nodes and selects the minimum cost node. It defines the evaluation function f(n) = g(n) +
h(n) where, h(n) is heuristics function and g(n) is the past knowledge acquired while searching.

SL Parameters Best-First Search A* Search

1 Evaluation Function The evaluation function for best-first The evaluation function for A* search
search is f(n) = h(n). is f(n) = h(n) + g(n).
2. Past Knowledge This search algorithm involves past This search algorithm does not
knowledge. involve past knowledge.
3 Completeness Best-first search is not complete. A* search is complete.

4 Optimal Best-first search is not optimal as the A* search is optimal as the path
path found may not be optimal. found is always optimal
5 Time and Space Its time complexity is O(b^d) and space Its time complexity O(b^d) and space
Complexity complexity can be polynomial. where b complexity is also (b^d)where b is the
is the branching and m is the maximum branching and m is the maximum
depth of the search tree depth of the search tree

6 Memory It requires less memory. It requires more memory.

7 Type of nodes kept It keeps all the fringe or border nodes in It keeps all the nodes in the memory
the memory while searching. while searching.

Beam Search Algorithm

 Beam search is a modification of best-first search that reduces memory requirements and is
often used in machine learning and NLP for problems with vast search spaces.
 It is a heuristic search algorithm that explores a graph by expanding the most promising node
within a limited set.
Heuristic Search:

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Beam search, like other heuristic algorithms, uses a "best guess" or heuristic to guide the search
towards promising solutions, rather than exhaustively exploring every possibility.
Limited Set:
Instead of expanding all possible nodes at each step, beam search maintains a "beam" or a limited set of
the most promising candidates.
Beam Width:
The "beam width" (often denoted as 'k') determines the number of nodes kept in the beam at each step.
Memory Efficiency:
By focusing on a limited set, beam search reduces memory requirements compared to algorithms that
explore all possible paths.
Applications:
Beam search is commonly used in machine learning, particularly in natural language processing (NLP)
and speech recognition, where it helps find the most probable or optimal sequence of words or characters.
How it Works:
(i) Start with a single node (or a set of initial nodes) in the beam.
(ii) Expand each node in the beam, generating its successors.
(iii) Evaluate the successors based on a heuristic function.
(iv) Select the top 'k' successors (based on the heuristic) to form the next beam.
(v) Repeat steps 2-4 until a solution is found or the beam is exhausted.
Relationship to Best-First Search:
1. Beam search can be seen as a modification of best-first search, where the breadth of the search is
limited to the beam width
2. Beam search is a heuristic search algorithm that explores a graph by expanding the most
optimistic node in a limited set. Beam search is an optimization of best-first search that
reduces its memory requirements.
3. Best-first search is a graph search that orders all partial solutions according to some heuristic.
But in beam search, only a predetermined number of best partial solutions are kept as candidates.
Therefore, it is a greedy algorithm.
4. Beam search uses breadth-first search to build its search tree.
At each level of the tree, it generates all successors of the states at the current level, sorting them
in increasing order of heuristic cost. However, it only stores a predetermined number (β), of best states
at each level called the beamwidth. Only those states are expanded next.
The greater the beam width, the fewer states are pruned. No states are pruned with infinite beam
width, and beam search is identical to breadth-first search.
The beamwidth

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Since a goal state could potentially be pruned, beam search sacrifices completeness (the guarantee
that an algorithm will terminate with a solution if one exists).
Beam search is not optimal, which means there is no guarantee that it will find the best solution.

In general, beam search returns the first solution found. Once reaching the configured maximum search
depth (i.e., translation length), the algorithm will evaluate the solutions found during a search at various
depths and return the best one that has the highest probability.
The beam width can either be fixed or variable. One approach that uses a variable beam width
starts with the width at a minimum. If no solution is found, the beam is widened, and the procedure is
repeated.

Components of Beam Search

A beam search takes three components as its input:
1. A problem to be solved,

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

2. A set of heuristic rules for pruning,

3. And a memory with a limited available capacity.

The problem is the problem to be solved, usually represented as a graph, and contains a set of nodes in
which one or more of the nodes represents a goal. The set of heuristic rules are rules specific to the
problem domain and prune unfavorable nodes from memory regarding the problem domain.
The memory is where the "beam" is stored, memory is full, and a node is to be added to the beam, the
most costly node will be deleted, such that the memory limit is not exceeded.
Beam Search Algorithm

The following algorithm for a beam search, as a modified best-first search, is adapted from Zhang's 1999:
beamSearch(problemSet, ruleSet, memorySize)
openMemory = new memory of size memorySize
nodeList = problemSet.listOfNodes
node = root or initial search node
Add node to openMemory;
while (node is not a goal node)
Delete node from openMemory;
Expand node and obtain its children, evaluate those children;
If a child node is pruned according to a rule in ruleSet, delete it;
Place remaining, non-pruned children into openMemory;
If memory is full and has no room for new nodes, remove the worst
node, determined by ruleSet, in openMemory;
node = the least costly node in openMemory;
Drawbacks of Beam Search:
1. In general, the Beam Search Algorithm is not complete. Despite these disadvantages, beam search
has found success in the practical areas of speech recognition, vision, planning, and machine
learning.
2. The main disadvantages of a beam search are that the search may not result in an optimal goal and
may not even reach a goal at all after given unlimited time and memory when there is a path from
the start node to the goal node.
3. The beam search algorithm terminates for two cases: a required goal node is reached, or a goal
node is not reached, and there are no nodes left to be explored.
A more accurate heuristic function and a larger beam width can improve Beam
Search's chances of finding the goal.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Mini-Max Algorithm in Artificial Intelligence

Mini-max algorithm is a recursive or backtracking algorithm which is used in decision-making and
game theory. It provides an optimal move for the player assuming that opponent is also playing
optimally.

 Mini-Max algorithm uses recursion to search through the game-tree.

 Min-Max algorithm is mostly used for game playing in AI. Such as Chess, Checkers, tic -tac-toe,
go, and various tow-players game. This Algorithm computes the minimax decision for the current
state.
 In this algorithm two players play the game, one is called MAX and other is called MIN.
 Both the players fight it as the opponent player gets the minimum benefit while they get the
maximum benefit.
 Both Players of the game are opponent of each other, where MAX will select the maximized
value and MIN will select the minimized value.
 The minimax algorithm performs a depth-first search algorithm for the exploration of the
complete game tree.
 The minimax algorithm proceeds all the way down to the terminal node of the tree, then
backtrack the tree as the recursion.
Working of Min-Max Algorithm:
The working of the minimax algorithm can be easily described using an example. Below we have taken
an example of game-tree which is representing the two-player game.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

In this example,
1. There are two players one is called Maximizer and other is called Minimizer.
2. Maximizer will try to get the Maximum possible score, and Minimizer will try to get the
minimum possible score.
3. This algorithm applies DFS, so in this game-tree, we have to go all the way through the leaves
to reach the terminal nodes.
4. At the terminal node, the terminal values are given so we will compare those value and
backtrack the tree until the initial state occurs.

Following are the main steps involved in solving the two-player game tree:
Step-1: In the first step, the algorithm generates the entire game-tree and apply the utility function to
get the utility values for the terminal states.
In the below tree diagram, let's take A is the initial state of the tree. Suppose maximizer takes first turn
which has worst-case initial value = - infinity, and minimizer will take next turn which has worst-case
initial value = +infinity.

Representation of Worst-Case Scenarios:

 For the maximizer, starting with −∞ means that initially, it assumes the worst possible
value. As it explores possible moves, it will try to increase its score .
 For the minimizer, starting with +∞ means it assumes the worst possible loss. It will try to
reduce the score as much as possible.

Step 2 : Now, first we find the utilities value for the Maximizer, its initial value is -∞, so we will
compare each value in terminal state with initial value of Maximizer and determines the higher
nodes values. It will find the maximum among the all.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

For node D max(-1, -∞) => max(-1,4)= 4

For Node E max(2, -∞) => max(2, 6)= 6
For Node F max(-3, -∞) => max(-3,-5) = -3
For node G max(0, -∞) = max(0, 7) = 7

Step 3 : In the next step, it's a turn for minimizer, so it will compare all nodes value with +∞, and will
find the 3rd layer node values.
For node B= min (4, 6) = 4
For node C= min (-3, 7) = -3

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Step 4: Now it's a turn for Maximizer, and it will again choose the maximum of all nodes value and
find the maximum value for the root node. In this game tree, there are only 4 layers, hence we reach
immediately to the root node, but in real games, there will be more than 4 layers.
For node A max (4, -3) = 4

That was the complete workflow of the minimax two player game.
Properties of Mini-Max algorithm:
Complete- Min-Max algorithm is Complete. It will definitely find a solution (if exist), in the finite
search tree.
Optimal- Min-Max algorithm is optimal if both opponents are playing optimally.
Time complexity - As it performs DFS for the game-tree, so the time complexity of Min-Max algorithm
is O (𝑏 𝑑 ). where b is branching factor of the game-tree, and d is the maximum depth of the tree.
Space Complexity - Space complexity of Mini-max algorithm is also similar to DFS which is O (𝑏 𝑑 ).
Limitation of the minimax Algorithm:
The main drawback of the minimax algorithm is that it gets really slow for complex games such as Chess,
go, etc. This type of games has a huge branching factor, and the player has lots of choices to decide. This
limitation of the minimax algorithm can be improved from alpha-beta pruning which we have discussed
in the next topic.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Alpha-beta pruning
Alpha-beta pruning is an optimization for the minimax algorithm used in game-playing AI,
reducing unnecessary computations by pruning branches in the game tree that cannot influence the final
decision, while maintaining the optimal result.
Here's a more detailed explanation:
Minimax Algorithm:
The minimax algorithm is a decision-making process used in two-player, zero-sum games (like chess)
where one player aims to maximize their score, and the other aims to minimize it. It works by exploring
all possible game states (represented as a tree) and assigning values to the leaf nodes based on potential
outcomes.
Alpha-Beta Pruning:
This technique optimizes the minimax algorithm by pruning branches of the game tree that cannot affect
the final outcome.
How it works:

Alpha: Represents the best (highest) value found so far for the maximizing player (the player trying to
maximize the score).
Beta: Represents the best (lowest) value found so far for the minimizing player (the player trying to
minimize the score).
Pruning: If during the search, the value of a node is found to be worse than the current alpha (for a
maximizing player) or beta (for a minimizing player), that branch and its descendants can be pruned
(skipped) because they cannot influence the optimal outcome.
Benefits:
Reduced Computational Cost: By pruning unnecessary branches, alpha-beta pruning significantly
reduces the number of nodes that need to be evaluated, making the search process faster and more efficient.
Faster Decision-Making: This efficiency is crucial for real-time applications like game-playing AI, where
speed is essential.
Example:
Imagine a game tree where the maximizing player (AI) has two options: A and B. Option A leads to a value
of 5, and option B leads to a value of 2. The minimizing player (human) will choose the option that leads
to the lowest value, which is 2. Alpha-beta pruning would recognize that the branch leading to option B is
not relevant to the maximizing player's decision and can be pruned.
Limitations:
Alpha-beta pruning's efficiency depends on good move ordering (exploring promising moves first). It is
not suitable for games involving chance or incomplete information.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

First-Order Logic in Artificial intelligence

In the topic of Propositional logic, we have seen that how to represent statements using propositional logic.
But unfortunately, in propositional logic, we can only represent the facts, which are either true or false.
PL is not sufficient to represent the complex sentences or natural language statements. The
propositional logic has very limited expressive power. Consider the following sentence, which we cannot
represent using PL logic.
 "Some humans are intelligent", or
 "Sourav likes cricket."

To represent the above statements, PL logic is not sufficient, so we required some more powerful logic,
such as first-order logic.

First-Order logic:
1. First-order logic is another way of knowledge representation in artificial intelligence. It is an
extension to propositional logic.
2. FOL is sufficiently expressive to represent the natural language statements in a concise way.
3. First-order logic is also known as Predicate logic or First-order predicate logic. First-order logic
is a powerful language that develops information about the objects in a more easy way and can
also express the relationship between those objects.
4. First-order logic (like natural language) does not only assume that the world contains facts like
propositional logic but also assumes the following things in the world:
 Objects: A, B, people, numbers, colors, wars, theories, squares, pits ...
 Relations: It can be unary relation such as: red, round, is adjacent, or n-any relation such
as: the sister of, brother of, has color, comes between
 Function: Father of, best friend, third inning of, end of, ......

5. As a natural language, first-order logic also has two main parts:

 Syntax
 Semantics

Syntax of First-Order logic:

The syntax of FOL determines which collection of symbols is a logical expression in first-order logic.
The basic syntactic elements of first-order logic are symbols. We write statements in short-hand notation
in FOL.

Basic Elements of First-order logic:

Following are the basic elements of FOL syntax:

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Constant 1, 2, A, John, Mumbai, cat,....

Variables x, y, z, a, b,....

Predicates Brother, Father, > ,....

Function sqrt, LeftLegOf, ....

Connectives ∧, ∨, ¬, ⇒, ⇔
∧ represents "and", ∨ represents "or", and ¬ represents "not"."⇒" means "implies" or "if...then..."
while " ⇔ " means " if and only if" or "is equivalent to".
P ⇒ Q: If P is true, then Q is true.
P ⇔ Q: P is true if and only if Q is true (or P is equivalent t o Q).

Equality ==

Quantifier ∀, ∃

Atomic sentences:
Atomic sentences are the most basic sentences of first-order logic. These sentences are formed from a
predicate symbol followed by a parenthesis with a sequence of terms.
We can represent atomic sentences as Predicate (term1, term2, ..., term n).
Example: Ravi and Ajay are brothers: => Brothers (Ravi, Ajay).
ABC is a cat: => cat (ABC).

Complex Sentences:
Complex sentences are made by combining atomic sentences using connectives.
First-order logic statements can be divided into two parts:
1. Subject: Subject is the main part of the statement.
2. Predicate: A predicate can be defined as a relation, which binds two atoms together in a
statement.
Consider the statement: "x is an integer.", it consists of two parts, the first part x is the subject of the
statement and second part "is an integer," is known as a predicate.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Quantifiers in First-order logic:

1. A quantifier is a language element which generates quantification, and quantification specifies
the quantity of specimen in the universe of discourse.
2. These are the symbols that permit to determine or identify the range and scope of the variable in
the logical expression. There are two types of quantifier:
a) Universal Quantifier, (for all, everyone, everything)
b) Existential quantifier, (for some, at least one).

Universal Quantifier:
Universal quantifier is a symbol of logical representation, which specifies that the statement within its
range is true for everything or every instance of a particular thing.

The Universal quantifier is represented by a symbol ∀, which resembles an inverted A.

Note: In universal quantifier we use implication “ →".

If x is a variable, then ∀x is read as:

 For all x
 For each x
 For every x.

Example:
All man drink coffee.

Let a variable x which refers to a men so all x can be represented in UOD (Universe of Discourse) as
below:

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

∀x man(x) → drink (x, coffee).

It will be read as: There are all x where x is a man who drink coffee.

Existential Quantifier:
Existential quantifiers are the type of quantifiers, which express that the statement within its scope is true
for at least one instance of something.
It is denoted by the logical operator ∃, which resembles as inverted E. When it is used with a predicate
variable then it is called as an existential quantifier.
Note: In Existential quantifier we always use AND or Conjunction symbol (∧ ).

If x is a variable, then existential quantifier will be ∃x or ∃(x). And it will be read as:

 There exists a 'x.'

 For some 'x.'
 For at least one 'x.'
Example:
Some boys are intelligent.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

∃ x: boys(x) ∧ intelligent(x)
It will be read as: There are some x where x is a boy who is intelligent.

Points to remember:
a) The main connective for universal quantifier ∀ is implication →.
b) The main connective for existential quantifier ∃ is and ∧.

Properties of Quantifiers:
a) In universal quantifier, ∀x is similar to ∀y ∀x.
b) In Existential quantifier, ∃x ∃y is similar to ∃y ∃x.
c) ∃x ∀y is not similar to ∀y ∃x.

Some Examples of FOL using quantifier:

Sure! Here's how we can represent the given sentences in First Order Logic (FOL):

a. All birds fly.

Let:

 Bird(x) : x is a bird
 Flies(x) : x can fly

FOL:

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

∀x (Bird(x) →Flies(x))
b. Every man respects his parent.
Let:

 Man (x): x is a man

 Parent (y,x): y is a parent of x
 Respects (x, y): x respects y

FOL:

∀x (Man(x) →∀y (Parent(y, x) →Respects(x, y)))

c. Some boys play cricket.
Let:

 Boy(x): x is a boy
 PlaysCricket(x): x plays cricket

FOL:

∃x (Boy(x) ∧ PlaysCricket(x))

d. Not all students like both Mathematics and Science.

Let:

 Student(x): x is a student
 LikesMath(x): x likes Mathematics
 LikesScience(x): x likes Science

"Not all" means it is not the case that all students like both:

FOL:

¬∀x (Student(x)→(LikesMath(x)∧LikesScience(x)))

Or equivalently (using De Morgan’s laws):

∃x (Student(x)∧¬(LikesMath(x)∧LikesScience(x)))

e. Only one student failed in Mathematics.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

Let's break down the FOL expression:

∃x (Student(x)∧FailedMath(x) ∧ ∀y ((Student(y)∧FailedMath(y))→y=x))

FOL Statement:

∃x (Student(x) ∧ FailedMath(x)∧∀y ((Student(y)∧FailedMath(y))→y=x

This sentence says:

There exists exactly one student who failed in Mathematics.

Explanation of each part:

1. ∃x
→ There exists some individual x
2. Student(x)∧FailedMath(x)
→ x is a student and x failed in Mathematics
3. ∀y ((Student(y)∧FailedMath(y))→y=x

→ For any individual y, if y is a student and y failed in Mathematics, then y must be the
same as x.

Putting it all together:

 There exists one person x,

 who is a student and failed in Math,
 and any other person y who is also a student and failed in Math must be the same
person as x.

Why this works:

This FOL statement does two things:

1. Existence: It guarantees at least one student failed.

2. Uniqueness: It ensures no one else besides that student failed.

So, it perfectly captures the meaning of "Only one student failed in Mathematics."

1. All birds fly.

In this question the predicate is "fly (bird)."
And since there are all birds who fly so it will be represented as follows.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE

 ARTIFICIAL INTELLIGENCE
Class notes

∀x bird(x) →fly(x).
2. Every man respects his parent.
In this question, the predicate is "respect(x, y)," where x=man, and y= parent.
Since there is every man so will use ∀, and it will be represented as follows:

∀x` man(x) → respects (x, parent).

3. Some boys play cricket.
In this question, the predicate is "play(x, y)," where x= boys, and y= game. Since there are some
boys so we will use ∃, and it will be represented as:
∃x boys(x) → play(x, cricket).

4. Not all students like both Mathematics and Science.

In this question, the predicate is "like(x, y)," where x= student, and y= subject.
Since there are not all students, so we will use ∀ with negation, so following representation for this:
¬∀ (x) [student(x) → like(x, Mathematics) ∧ like(x, Science)].

Free and Bound Variables:

The quantifiers interact with variables which appear in a suitable way. There are two types of
variables in First-order logic which are given below:
Free Variable: A variable is said to be a free variable in a formula if it occurs outside the scope of the
quantifier.
Example: ∀x ∃(y)[P (x, y, z)], where z is a free variable.

Learn more
Bound Variable: A variable is said to be a bound variable in a formula if it occurs within the scope of the
quantifier.
Example: ∀x [A (x) B( y)], here x and y are the bound variables.

Created By Mr. Sougata Dey, Assistant Professor, IT Department, MCKVIE