Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Artificial Intelligence for NTA UGC NET
Syllabus Discussion and Analysis
Syllabus of Artificial Intelligence specifically for NTA and NET exams
...
The syllabus for NTA and
NET exams is already available on their website, so you may wonder why these notes are
beneficial
...

The Importance of Smart Work
When preparing for competitive exams, it's important to do both hard work and smart work
...
In these notes, we will
be discussing the main topics taken directly from the syllabus
...
You should focus
on the topics with the highest probability and not skip them
...
However, some students only study for exams and purchase the standard book for AI,
which is 'Artificial Intelligence' by Rich and Knight
...
It is important to note that some topics need to be studied
in depth for better understanding and knowledge
...
It covers
topics like Heuristic Search and A*
...

Algorithm Overview
Let's start by discussing the best first algorithm
...
These are the main topics
that we will cover
...

DFS and BFS
Lastly, we will touch upon DFS and BFS algorithms
...

When preparing for exams, it is important to focus on certain topics that are likely to appear in
the test
...

These questions are logical and can be easily solved with practice
...

● Other topics: Genetic algorithms and Single
...
It's
important to understand these learning strategies
...

Knowledge Representation
Knowledge representation is an important concept in machine learning
...

This section covers the types of agents and their properties, including how they use current and
past history
...

For knowledge representation, NLP, and planning, I would give them one star
...
Specifically, in knowledge
representation, you should focus on the approaches to representing knowledge, such as
predicate logic
...


What is Artificial Intelligence
Let me provide examples of AI that you use on a daily basis
...

During World War II, the first computer was created with the main purpose of breaking German
communication
...
In 1950, Turing
published a paper titled, "Can Machines Think?" which posed the question of whether machines
could think like humans
...
We want to
create machines that can behave, think, and work like humans
...

Examples of AI in Your Daily Life
One example of AI is the Google Assistant or Siri Alexa on your smartphone
...
Google handles exabytes and petabytes of data,
yet it can give you an answer almost instantaneously thanks to AI algorithms
...
You simply enter your destination,
and the car will take you there without the need for a driver
...
The car uses AI to learn and adapt, just
like a human driver does
...
As humans, we learn, analyze,
and make decisions based on our perceptions
...
The aim of AI is to break
down the barrier of intelligence between humans and robots and provide machines with the
ability to make decisions by themselves
...
While we cannot guarantee whether the decisions made by machines will be
good or bad, the goal is to empower machines with decision-making powers
...
To illustrate this, let's take a look at Netflix and YouTube
...
All of this
is possible thanks to artificial intelligence analyzing your data and influencing your decisions
...
As they browse through
the options, they select cheese bursts
...
This is just another example of how AI is being used to analyze and
personalize information for individuals
...
The person may not even know their
cholesterol value is high or low, but they receive a message warning them not to order pizza
...
If they continue to ignore the warnings
and order pizza again, an expert system powered by artificial intelligence may deactivate certain
options, such as cheese burst, from their profile
...

Artificial Intelligence and Human Behavior
Major companies today are already working on artificial intelligence and have developed
machines that work based on human behavior
...
For example, if someone needs to score over 40% to pass a test and person
A scores 60%, we reason that person A has passed the test
...

● Problem Solving: Machines should be able to solve problems on their own, making
decisions based on their own thought processes
...

Perception in Machines
Machines, like humans, should be able to perceive their surroundings before making decisions
...


What is State Space Search
Focusing on State Space Searching, a major application of Artificial Intelligence in problem
solving
...

This included solving games such as tic tac toe, water jug problem, 8 queen problem, chess,
and Go
...

State space searching is a vital aspect of problem solving in Artificial Intelligence
...

State Space in Artificial Intelligence
State space refers to the total number of states in which a problem can go
...
This
representation helps in analyzing the problem and taking steps to achieve the goal state
...
The set of actions, denoted as 'a,' refers to all possible
actions that can be taken to reach the goal state
...
It involves a 3x3
board with 9 spaces
...
To solve the puzzle, the machine or agent must be told the problem clearly, including
the set of states, start state, and goal state
...
The start state of
the problem is represented as follows:
● 123
● 456
● 78_
The goal state is:
● 123
● 456
● 78_
Defining the goal state is important for the search algorithm to know where to stop searching
...

To properly play this game, you must know and follow all the rules
...
Instead, you can
replace the empty space with the numbers on the left or right of it
...
This means that my new
state is an intermediate state where I have moved the space upward, resulting in 3 coming to
this position while the other spaces remain the same
...

● Upward action: 3 moves up, others remain the same
● Downward action: 7 moves up, others remain the same
Regardless of the action chosen, the concept remains the same
...


Uninformed Vs Informed Search
In artificial intelligence, searching can be done with or without information
...
Informed searching, on the other hand,
uses heuristic information to guide the search process
...
The search process involves checking if the current state is the goal
state, and if not, exploring all possible states from the current state
...
Uninformed searching is time-consuming, especially when the
state space grows exponentially
...
Heuristics are
assumptions or rules of thumb that help to estimate the distance from the current state to the
goal state
...
Informed searching can reduce the search space and time complexity, making
it more efficient than uninformed searching
...
With uninformed searching, the algorithm explores all possible routes between cities,
which can be time-consuming for large numbers of cities
...

If you use uninformed searching, you go through each lane in Rome using brute force method
and check if it is your goal state
...
This method is quick but compromises
with optimality
...
Heuristic searching can solve
problems in polynomial time but may not provide an optimal solution
...


Breadth First Search | Uninformed Search
Breadth search technique in Artificial Intelligence
...

Uninformed Search Technique
BFS comes under the uninformed search technique, which can also be referred to as the blind
or brute force method
...
In contrast, heuristic techniques involve estimating the cost to reach the goal state
from a particular state
...

FIFO and Queue Data Structure

BFS works on the principle of FIFO (First In First Out) and uses the queue data structure
...

If we apply BFS on the above tree diagram, we will use the queue data structure
...
Then, we remove "a" from the head and insert its
child nodes, "b" and "c", into the tail of the queue
...

Conclusion
BFS is a fundamental search technique in AI that uses the FIFO principle and the queue data
structure
...

BFS in Graphs and Trees
In BFS, you will be given a graph or a tree and you may be asked if it is a proper BFS or not
...
For example, if we remove element A from the
queue, it means that A has taken us ahead to a certain number of places
...
The order in which these elements are written does not matter
...
However, there
is a particular pattern that you can follow to make the process easier
...

● Firstly, we start with a node A and add it to a queue
...

● We add B, C, and D to the queue
...
We add E and F
to the queue
...
We add G and H
to the queue
...

This process continues until we have searched all the nodes in our graph
...
This
follows the rule of first in, first out (FIFO)
...

Unlike Depth First Search (DFS), it goes level by level instead of going in depth
...

This means that BFS covers all nodes at a given depth before moving on to the next level
...
We then
remove A from the queue and add its children D and E to the queue
...
We then remove D and add its child I to the queue
...
Finally, we remove H from the queue
...

● The shallowest node is the nearest node at a given level
...

By understanding these key points, we can effectively use BFS to traverse trees or graphs
...
We inserted J and K from the tail
...

Now we will remove F
...

Study Hacks for AI
Here are some tips for studying AI:
● Break down complex topics into smaller, more manageable parts
...

● Practice coding regularly to solidify your understanding of algorithms and programming
languages
...

Remember to take breaks and prioritize self-care to avoid burnout
...
We will cover all the important
points and keywords about DFS that are crucial for competitive exams like NTA NET and
university-level exams
...
It works like a brute force method or blind search and moves ahead with present
knowledge only
...

Data Structure Used by DFS
DFS uses a stack data structure, which is last in first out based
...

DFS Logic and Concept
DFS works on the logic of the deepest node
...
It will first go in deep, and if it does not get the goal state, it will backtrack and go in
another direction
...

DFS will move in one direction completely and go in deep till the last leaf node
...

Completeness of DFS
DFS is incomplete, which means that it may not find a solution even if one exists
...

Difference between BFS and DFS
BFS is a complete algorithm, meaning it covers all levels one after the other
...
In such cases, it may get stuck in a permanent loop or keep moving in one direction,
making it incomplete
...
On the other hand, BFS always gives an optimal solution if all costs are similar
...
However, in AI, time complexity is written as O(b^d),
where b is the branching factor, and d is the depth
...

Both BFS and DFS are uninformed search techniques that work only on present knowledge and
do not consider heuristic or estimated values
...
This technique is an extension of Breadth
First Search and Depth First Search, with two simultaneous searches from initial to goal and
backwards from goal to initial
...
So, let's get started!
What is Bidirectional Search?
Bidirectional Search is a special kind of technique that searches from both the initial and goal
nodes
...
However, in Bidirectional Search, we start the search from both node 1 and node 9
simultaneously
...

Think of it like meeting a friend
...

Alternatively, you both can start your journey at the same time and meet at a midpoint
...

Time and Space Complexity
The time complexity of BFS or DFS is O(b^d), where b is the branching factor and d is the depth
of the search
...
This is
because we are searching from both ends simultaneously, and we only need to search to half

the depth to meet in the middle
...

The space complexity of Bidirectional Search is the same as BFS or DFS, which is O(b^d)
...

Understanding the Bidirectional Search Algorithm
In the worst-case scenario, the time complexity of the Bidirectional Search algorithm is O(b^d),
which is the same as BFS or DFS
...

● If you are using BFS, it is always complete
...

The Depth First Search algorithm generally works on one side
...
The complexity of
DFS is O(b^d)
...
In bidirectional
search, BFS is used to ensure completeness and get an optimal solution
...


8-Puzzle Problem
Going to discuss how to solve the 8 puzzle problem using uninformed search or blind search
...
This algorithm explores
all the search spaces and covers all the nodes in the search tree
...
It covers all
the nodes in level 1, then level 2, and so on until it reaches the goal state
...
The start state is either a picture
or a set of randomized numbers that represent the puzzle
...

The legal moves in the puzzle are up, down, left, and right
...

Understanding Left and Right Movement in a Tile Puzzle
In a tile puzzle, left and right movements refer to the empty spaces or tiles that can be moved in
those directions
...
Let's use the following example:
● Start State: an arrangement of tiles with one empty space
● Empty Space: the tile that can be moved
So, in this puzzle, the player must move the empty tile left, right, up, or down to reach the end
state
...
Moving left is
not an option
...
Here's how it will look:
● 1
● 2

● 3
● 4
Here are some instructions:
● Move the number 6 right
● Move the number 7 right
● Move the number 5 right
● Move the number 8 right
● Moving left is not an option
● If you move up, it will form the pattern 2,3 1
In mathematics, the values 4, 6, and 7 can be arranged in the same way as 5 and 8
...
Therefore, if we move a
value down, it will be arranged in the following order: 1, 2, 3, 7, and 4
...
In this scenario, the agent will form three states in the next
level - 6, 5, and 8
...
The agent will explore all three states in
depth 1, as it must cover all nodes in its search
...


What is Heuristic in AI | Uses
In this, we will discuss what heuristic is, why we use it, and how to calculate the heuristic value
in artificial intelligence
...
In uninformed search, we do blind search and
explore all state spaces of the problem, which can lead to exponential time complexity
...

What is Heuristic in Artificial Intelligence?
Heuristic is a technique designed to solve a problem quickly by making assumptions or
guessing a quick solution
...
Similarly, in artificial intelligence, we use heuristic
to find good solutions quickly without exploring all possible solutions
...
To avoid this, we use heuristic functions or heuristic
values, which help us find good solutions quickly without exploring all possible solutions
...

How to Calculate Heuristic Value in Artificial Intelligence?
There are different methods to calculate heuristic values, such as Euclidean distance, which is
also known as straight line distance
...
Heuristic values help us find good solutions quickly, but optimal solutions
are not guaranteed
...
This can be done by
finding the coordinates of the two points and using the formula:
distance = square root of (x2-x1)^2 + (y2-y1)^2
Using this method, we can determine the minimum distance to the destination
...

Another approach is to use the Manhattan distance, which calculates the vertical and horizontal
distance between two points
...

We can calculate the distance for each tile by finding how many movements are required to get
it to its correct position in the goal state
...

● Calculate the sum of the distances of the tiles from their correct positions
...
However, it's important to note that heuristic methods don't
guarantee the optimal solution, but only a good solution
...
While heuristic methods do not guarantee the optimal
solution, they do provide a good solution in a shorter amount of time compared to blind search
or brute force methods
...
However, it is important to note that these methods may still
have a worst-case scenario of non-polynomial time
...

Heuristic is a method of problem-solving that uses practical approaches to find a solution
...

To calculate heuristic value in the 8 puzzle problem, we use the concept of the number of
misplaced tiles
...
You need not count the space
...
So, the value of
h for this state is 2
...

When considering movement in a particular situation, there are three possibilities: moving up,
left, or right
...


Using Heuristics to Solve a Puzzle
If we move the puzzle piece down, the space will go down and 7 will come up
...
This will create three states in blind
search
...
We calculate the heuristic value of each state by
counting how many tiles are misplaced based on the goal state
...
The heuristic value is 4
...
The heuristic value is 4
...
The heuristic value is 2
...

The concept of heuristic is to find a quick answer by exploring the minimum value
...
Therefore, there is no need to explore other paths
...

There are four choices to explore, up, down, left, and right
...
Moving left, however, will not benefit as it will only lead back to the parent state
...
Moving down results in the state 1 2 3 4 5 6 7 8
...
The heuristic value of the resulting state after moving up is 2, with two tiles not
in their correct positions
...
Therefore, moving down has the minimum heuristic
value and is the best path to explore
...
In a blind
search, you explore all the depths, but with heuristics, you only explore a state that is most likely
to lead to the solution
...
For instance, if we have a puzzle with tiles numbered from 1 to 8, and we
want to find the misplaced tile, we look for the minimum value
...

Exploring States
When exploring states, we must keep in mind the goal state
...
For instance, if we have a puzzle with a goal state of 1 2 3 4 5 6 7 8 and
we explore the state 1 2 3 4 5 6 7 8, we have achieved the goal state, and there is no need to
explore further
...
Informed Heuristics
In uninformed heuristics, we explore all the depths with a branch factor of b and a depth of d,
while in informed heuristics, we only explore the most likely state to lead to the solution
...
However, there is no guarantee that we will get an optimal solution
...


Generate and Test Search
This heuristic technique is a part of informed search techniques and is essential for competitive
exams, college, or university level exams
...

● Generate and Test is the simplest method among all other methods of heuristic search,
such as Best First Search, Hill Climbing, and A* Algorithm
...

● In normal life, we use Generate and Test in two modules: generate and test
...

● The test module picks up these generated solutions and tests them against the goal
state
...
Otherwise, it is dropped
...
We generate
solutions until we find the right one or get closer to the solution
...

The basic concept of generate and test is to keep on generating new solutions until a good
solution is found
...
In order for a
generator to be good, it must have the following properties:
● Complete: It covers all possible states and will definitely give an optimal solution
...

● Informed: It uses heuristic techniques to quickly find solutions based on knowledge of
the local domain
...
However, using informed search
techniques can reduce the time complexity and generate solutions faster
...
Therefore, it is important to use informed search
techniques to reduce the number of states and save time
...
Heuristic search involves using knowledge about the problem and the domain in
order to guide the search for a solution
...
This means that if we generate 5 solutions per minute,
we can find the answer in less than 2 days, instead of the 10 weeks it would take with an
uninformed search
...
The effectiveness of the heuristic search depends on the
quality of the heuristic used
...

● BFS comes under the informed search technique, and we use the heuristic method in
this
...

● The algorithm of BFS works by using a priority queue called 'open' containing the initial
state
...

● The goal state is reached when the node state matches the goal state, and we return the
path from the initial to that node
...

Using this information, we can determine the heuristic value of each node and prioritize them in
the open queue accordingly
...
For example, if
we have points B, C, and D all with coordinates on the G axis, we can calculate the distance
between them using the Euclidean formula:
d = √((x2-x1)² + (y2-y1)²)
● B to G: Let's say B has coordinates (2, 7) and G has coordinates (6, 7)
...
We can plug
these values into the formula along with G's coordinates and get:
● d = √((6-5)² + (7-9)²) = √(5) = 2
...
We can
plug these values into the formula along with G's coordinates and get:
d = √((6-1)² + (7-3)²) = √(65) = 8
...
236, and between D
and G is 8
...

Best First Search Algorithm
When working with the best first search algorithm, we need to consider the heuristic value as
the main focus
...
Therefore, we must concentrate only on the heuristic
value
...

The first node is removed, and all successors of the node are generated and put into the queue
according to their f value (heuristic value)
...

If the open queue is empty, then the search has failed
...

Best Heuristic Algorithm
The Best Heuristic Algorithm is a simple concept that involves calculating distance or cost
...
Let's start
from point A and look for its connections
...
This value can help determine the most efficient route to take
...

Starting from Point A
When starting from point A, it is important to consider the path that will lead to the goal state
...

Node Expansion and Heuristic Values
To reach the goal state, we need to expand nodes and calculate heuristic values
...

● The cost to go from B to G is 32
...

● From node D, we can go to the goal state with a cost of 35
...

So, the current node is A and we need to add B and C into the OPEN list
...

Beam Search Algorithm takes care of space complexity and is based on heuristics
...

Let's consider an example:
● Starting state: A

●
●
●

Goal state: G
Choices from A: B, C, D
Heuristic values:
● B: 32
● C: 25
● D: 35
In Breadth First Search, we choose the node with the minimum heuristic value
...
In
this case, the minimum value is C, which takes us to the goal state at minimum cost
...

Priority Queue
In order to maintain a priority queue, we keep B and D in memory and sort them to determine
which is the minimum value
...
From these, C is
the minimum value, so we remove it from the open list
...

Sorting Algorithm
To remove items from the open list, we use a sorting algorithm to determine the minimum value
...

The best first search algorithm involves exploring nodes and keeping them in memory for future
use
...
The algorithm then sorts the remaining nodes in a priority queue based on their cost
and explores the one with the lowest cost
...
For example, if the beam value is 2, only the best two nodes will
be kept in the queue for exploration
...
Therefore, backtracking may be necessary to explore other paths
...
In beam search, we
remove all but the top k best options at each level of the search tree
...

How it Works
Let's consider an example where we have a starting node and a branching factor of 2
...
However, in beam search, we only keep the top 2
best nodes and remove the others
...

As we continue to explore further states, we again only keep the top 2 best nodes and remove
the others
...

Benefits

The benefits of beam search are twofold
...
Secondly, it reduces the time complexity of the sorting process
as the number of nodes to sort is reduced
...
It is important to note that there can be some problems with beam
search if the beam value is not chosen correctly
...
While it may provide a good solution,
there is no guarantee of always providing an optimal one
...
If the beam
value is set to 1, it becomes the hill climbing method
...


Hill Climbing Algorithm
Going to discuss the Simple Hill Climbing Algorithm, which is a local search algorithm that has
knowledge of its local domain and does not have any knowledge of the global problem
...
It does not do backtracking if it is not getting any best move
...

It then finds the best move from all the branches based on their heuristic value and explores it
ahead
...
The algorithm
keeps on going until it finds a better state
...

Example
Let's say we have an initial state and three states ahead of it
...
We forget the other two branches as they are not
the best move
...
If we do not find any better state,
then we cannot backtrack
...

Hill Climbing Problem
In the Hill Climbing problem, you keep climbing until you reach a point where your leg is stable
...
So, you stop there, and that
is the best path for you
...
In this
problem, the starting state is different from the goal state
...

Heuristic Value
You have three options to move from the starting state
...
Then, you have to choose the state that has the lowest heuristic value
...
You need to keep repeating this process until you reach the goal state
...
This means
that you are climbing the mountain blindfolded
...
If
you were not blindfolded, you would be able to see the whole domain, and you would know that
there are other mountains to climb
...

Understanding Local Maximum Problem in Hill Climbing Algorithm
Hill climbing algorithm is used to solve optimization problems by iteratively moving towards a
higher value or better solution
...

To understand this problem, consider the diagram below
...
It explores the neighboring points with heuristic values of 4, 5, and 6
...

Now, if the algorithm explores the next state from point 4 and reaches point 5, its heuristic value
increases and becomes the new current state
...

Hence, it stops and cannot reach the globally maximum point, which is point 9
...
It can also lead to a
plateau or a flat maximum
...

Hill Climbing in AI
Hill climbing is a problem-solving technique used in artificial intelligence
...
However, it faces some problems like
plateau, flat maximum, and ridge
...
This is called a plateau or flat
maximum problem
...

Ridge
Ridge occurs when there are multiple values, and you are moving in one direction
...
This is a special case of local maximum
...
Beam
search is a technique that can be used to overcome the limitations of hill climbing
...
You only need to focus on the best move and ignore the
others
...
It's important to keep moving forward and making the best decisions to
reach the optimal solution
...
In informed search, we have prior knowledge of the problem domain and
its statements, which we call heuristic values
...
Unlike uninformed or blind search techniques like DFS and BFS, where we
traverse the tree without any knowledge of the goal state, A* algorithm takes the goal state into
consideration while searching
...
Here, f(n) represents the cost, g(n) is the actual start node, and h(n) is the
estimated cost from node n to the goal node
...
The actual cost of the
path from start to intermediate node n is denoted by s to n, which is the g(n) value
...

Introduction to Admissible Algorithm
Admissible algorithm guarantees the optimal solution and works towards finding the shortest
path
...
A directed graph is used to represent the nodes, where the start node
is 's' and the goal state is 'g'
...
The heuristic value is an estimation of the value and is calculated using the best
search algorithm
...

Finding the Optimal Path
To find the optimal path, we start with the start node 's' and calculate the cost of moving to its
adjacent nodes, i
...
, b and c
...
For example, the cost of moving from s to b is 16 (4+12), and the cost of moving from s to
c is 14 (3+11)
...
e
...

Summary
● Admissible algorithm guarantees the optimal solution
...

● To find the optimal path, we start with the start node and calculate the cost of moving to
its adjacent nodes
...

A* Algorithm
A* algorithm is a search algorithm that finds the shortest path between the initial and goal state
...


Understanding the A* Algorithm
A* algorithm evaluates each node by combining the cost to reach the node (g) and the cost to
get from the node to the goal (h)
...

Let's consider an example: F and E are the initial and goal state, respectively
...
The total cost becomes 9+11=20
...
The total cost becomes 20
...

The algorithm chooses the path with the lowest cost, which is SCDE with a total cost of 16
...
The time complexity of A* The
algorithm is b^d, where b is the branch factor and d is the depth
...

Time and Space Complexity of A* Algorithm
The time complexity of A* algorithm is order of v+c, where v is the number of nodes and c is the
number of edges
...

Admissibility of A* Algorithm
A* algorithm is admissible, which means that it never overestimates the cost of reaching the
goal
...


Underestimation & Overestimation of A*
Going to discuss A* admissible and the funda of over and underestimation
...

A* is a popular algorithm used for pathfinding and graph traversal
...
In A*, we use heuristic values to estimate the cost of moving from a
starting node to a goal node
...
If our estimation is less than the actual value, it is called underestimation
...

For instance, let's say you want to purchase a laptop, and the actual and optimal price of that
laptop is 30,000
...
In this case, it is an
overestimation
...

Now, let's move to the graph
...
The intermediate nodes
are denoted as a and b
...

Let's take the case of overestimation
...

We took h(a) as 80 and h(b) as 70
...
We get f(a) as 280 and f(b) as 270
...
Let's say we choose B, which means we will reach the goal state G
...
This is the
cost to reach the goal state, which is 250 in this case
...
The heuristic value for the goal state is 0
...

In the second case, we need to make sure that the heuristic value is an underestimation of the
actual cost
...
Using the same formula, we can find f(a) and
f(b), which are 230 and 220, respectively
...
Then, we calculate the cost to reach
the goal state G from point B, which is the sum of the cost to reach G from B and the heuristic
value of G
...

If the cost to reach the goal state from point A is less than the cost from point B, we select A as
the next point to expand
...
We continue this process until we reach the
goal state and get the optimal solution
...
Overestimation may not always lead to the optimal solution
...
Similarly, in A*, we may expand other
points to find a better solution
...


AO* algorithm
Going to discuss the AO* algorithm which is based on the AND/OR graph and works on the
principle of problem decomposition
...

AND/OR Graph
The AND/OR graph is a specialized graph used to represent problems
...
In this graph, we have hyperedges
that represent multiple conditions that must be satisfied to reach a solution
...

Difference between AO* and A*
Both AO* and A* are informed search techniques that use heuristic values to find solutions
...

A* works on underestimation, while AO* does not have this guarantee
...

When estimating values, we often use heuristic values such as 10 and 12
...
This is just one
example of how we can use estimation in problem-solving
...

F nodes
...
The
concept of B and C is that B has a value of six
...

AO* Algorithm for Optimal Solution

In AO* algorithm, the cost of each node is considered to be one
...
Then we add 2 to this value since we are
reaching the end, which gives us a total cost of 20
...
Since 11 is a smaller value, we choose to
go towards D
...
Since both ends are normal, the cost of
going to E and F is 8+1+1=10
...
Thus, the
total cost of this path is 11
...
For
example, if we explore the path after C, it is possible to find a path with a lower cost
...

Similarly, the cost of B changes to 3 (2+1)
...
Thus, the new heuristic value of B is 3 and the new heuristic value of C is 2
...
However, this path can only be
found if all solution paths are explored
...
However, it is important to explore all possible paths to ensure that the optimal
solution is found
...
Use a new
node instead of f, let's say j
...
The new estimated value is seven, and the total cost comes to nine
...
The new heuristic value of a becomes eight, but since seven is
less, we explore it
...
The heuristic value of g is two, so the new
value becomes three
...

The new heuristic value of c becomes two
...
The new heuristic value of d becomes one, and j is solved, so d is also solved
...
This means
that the new heuristic value for C is 2 and for D it is 1
...
Adding 2 and 1, we get a new heuristic value of 3 for A
...


Introduction to Game Playing
Going to discuss game playing and its interesting aspects
...

When it comes to searching algorithms, we rely on rational thinking and logical reasoning to try
and outsmart our opponent
...
Of course, our opponent is also trying to
beat us using the same set of rules
...
The outcome can be either a win, loss, or a
draw
...


The study of multi-agent environments has been a high priority for AI researchers
...
However, it's important to note
that popular games like PUBG and GTA are not the focus of AI research
...

However, this discussion is focused on games that require intelligence and logic, with clearly
defined rules to follow
...
However, it is important to note that games that
heavily rely on luck, such as dice games, should not be considered for evaluation purposes
...

Card games may also have an element of luck, but they can still be used for evaluation as long
as the focus is on the decision-making process and strategy employed by the players
...

Backtracking Algorithm
One of the most important things to know about Minimax Algorithm is that it's a backtracking
algorithm
...

Why Not Breadth-First Search?
A common question is why we don't use the Breadth-First Search algorithm in game playing
...
If we used BFS technique,
it would run in level order and allow players to undo and play moves elsewhere, which is not
allowed in game playing
...
In order
to achieve this, we have to use the concept of a backtracking algorithm and the best move
strategy
...

Minimax Algorithm
The minimax algorithm is used for game playing and it involves two players, the max player and
the min player
...
The first
turn is always of the max player who tries to maximize their utility or the points they will get after
winning
...

Understanding Utility in Game Theory
Utility in game theory refers to the points earned by winning or losing a game
...
In this scenario, the player taking the
minimum value will try to minimize your utility by selecting the worst move for you, which, in turn,
is the best move for them
...
It's
crucial to note that what may be the best move for Max may not be the best move for you
...
This is a critical aspect of game theory that players need to keep
in mind
...
He must choose one of
those options
...
We will play this game in a
typical manner, where we take turns selecting our moves
...

● Max's options: B or C
● If Max chooses B, it will be Min's turn
● We will take turns making moves
● Our move will be the last at this level
When playing a game, it is important to consider the utility or potential profit of each move
...

However, it is important to remember that the opponent's moves cannot be predicted, so one
must choose their own strategy carefully
...
It is important to
choose the maximum value between available options
...

Ultimately, the goal is to reach the terminal with the highest utility possible
...
The two possible values are -1 and 8
...

● Node E: Min's turn to move
...
Min will choose the
minimum value, which is -1
...


Alpha beta pruning
Going to discuss all the important points about Alpha-Beta Pruning, which are beneficial for your
competitive exams as well as for your college or university exams
...
The time complexity and
performance of the minimax algorithm are calculated in B raised to power D, where B is the
branching factor and D is the depth of the game tree
...
The time
complexity we get is the order of B raised to power D
...
If we have already
found the best path, we prune all the remaining paths
...
We consider Alpha for the Max nodes and Beta for the Min nodes
...
If we have already found a
path, we prune all the remaining paths
...

When playing a game where players choose paths, the Alpha-Beta Pruning method can help
determine the best choices without exploring all nodes
...
Above it is a Min node where the beta value will be calculated
...

● Max chooses path
● Min chooses path
● Max chooses path
● Min chooses path
● Terminal nodes have utility values
To find the values of alpha and beta, use the given values and avoid exploring unnecessary
nodes
...

Alpha on Max
You can write these things before:
● As on the left most side at terminal
● We have value 3
● We will fix beta's value 3
But Min value of this node, we don't know that
...
Obviously, if we get 3 values of this beta
then the min value of this node either will be 3 (we have 3 already) or will be less than 3
...
It has a value of 4
...
Now we know that this node's min
value is 3
...
Now this node has a value of 3
...

Fixing the Value of Beta
We need to fix the value of beta, which can either be 3 or less than 3
...

Similarly, we take alpha's value in an increasing way, but we don't have to use minus infinity or
plus infinity
...
We can take the Max value of Alpha as 3 and assume the
Max value of this node to be 3 as well
...

● If a node's value is less than or equal to alpha, it means that the minimum value is
already determined and there is no need to explore further
...

● Consider the example where we have to find a path in the search tree that leads to the
maximum value
...
Similarly, if we reach a node whose value is 2, we fix
beta's value to 2 because the minimum value of this node will either be 2 or less than 2
...
Since the path
to alpha guarantees a minimum value of 3, there is no need to explore the path to beta,
and we can prune it
...
The minimum value for this node at the
min level will either be 7 or less than 7
...

Now, as we have fixed our value, we take it above and fix the alpha's value as 7
...
We do not know yet, but the minimum
value will be 7 for sure
...
So, this node's minimum value will
either be 3 or less than 3
...


Knowledge Representation and Reasoning
Introduction to Knowledge Representation and Reasoning in AI
In this topic, we will be discussing knowledge representation and reasoning in artificial
intelligence
...
We need to provide
human knowledge to the computer in a machine understandable form to make AI systems truly
intelligent
...
Objects refer to the several objects that surround
humans, and information regarding the object is a type of knowledge
...

Performance deals with how humans and other things perform certain actions in different
situations
...
Lastly, knowledge base contains a group of information
regarding any discipline
...


Declarative knowledge represents the non-facts objects about the world, while procedural
knowledge is more complex and deals with how the objects behave and act
...
Lastly, structural knowledge establishes the
relationship between objects and provides solutions to real-life problems
...


Propositional Logic
Going to discuss Propositional Logic and its important points
...
So, let's dive in and learn more about
Propositional Logic
...
But why do we need
Knowledge Representation? The answer is simple: we want to make our machines intelligent,
and knowledge is one of the key factors in building intelligence
...
Propositional Logic is a tool
that helps us do that
...
Human beings acquire
knowledge from childhood and store it in our minds, allowing us to use it when needed
...

Propositional Logic
Propositional Logic involves representing knowledge through sentences or propositions
...

If we were to talk about a statement in English, "The sky is blue" would be a simple statement
...
However, statements can also be written in
mathematical form such as "1 + 1 = 2"
...

Propositional Logic
Propositional logic involves reasoning and making arguments based on statements
...
A proposition cannot be both true
and false at the same time
...
Similarly, "New Delhi is the capital of India" is a true proposition
...
For example, the
statement "Some students are intelligent" can be true or false depending on the context
...
When it comes to programming, languages like C use functions like print f
to output data
...
Syntax errors occur when the code is not written according to the rules and
syntax of the programming language
...

In the given example, if you write "print f f f hello" instead of "print f 'hello'", it will result in a
syntax error
...


Introduction to Intelligent Agents and their
types
Going to discuss what an agent is and how we can build intelligent agents
...

What is an Agent?
An agent can be anything - a human being, a machine, a robot, or a program
...
An agent is defined by the operations it performs
...
For example, a doctor treating a patient
...
For example, an ATM dispensing cash
...
For example, a robot performing surgery
...
For example, a chatbot answering customer queries
...

Agent Operations
The first operation performed by agents is sensing from the environment, also known as
perceiving
...
This perception
can be current or historical, meaning it can be something sensed in the present or something
saved from the past
...

Agent Programs
Agent programs compare current perceptions with past ones and make decisions based on
similarities
...
The programs
also help agents perform these actions through the use of actuators, which work based on
effectors
...

When we use our legs or our mouth, we are performing actions that are called effectors
...
In essence, an agent perceives or

senses its environment, makes a decision, and performs an action based on that decision
...

To illustrate this model, let's consider a human being leaving for the office
...
Based on this perception, the person makes a
decision and takes an action, such as bringing an umbrella or wearing a coat
...
This sensory input is processed by agent
programs in our minds, which help us make decisions based on our perceptions
...

Decision-making and Actions
When faced with a decision, such as whether to carry an umbrella, we use our agent programs
to determine the appropriate action
...
Our effectors, or physical body parts, carry out this action
...
This same process is what we hope to replicate in artificial intelligence
and robotics
...
The goal of an agent is to achieve high performance,
meaning that it should be able to make optimized decisions based on the information it receives
...
The same concept can be implemented in machines and robots
...
We call these machines and robots as agents
...
This means that the agent should be able
to make optimized decisions based on the information it receives
...


Simple Reflex Agent
The concept of a simple reflex agent is similar to the reflex action of human beings
...
It happens suddenly,
which is a reflex
...

Properties of Simple Reflex Agent
● Acts only on the basis of current perception
● Performs an action based on current situation
● Ignores the rest of the percept history
● Has a knowledge base

The simple reflex agent makes a decision and performs an action based solely on the current
perception
...

Percept history refers to our past experiences and perceptions
...

Obviously, we will have to perform some calculations
...

A simple reflex agent acts spontaneously without taking any time to perform its action
...

Main Points:
● If-Then rules are condition statements
● If-Then rule means "if this, then this"
● You have to give a condition for it to work
These rules are important keywords that come up frequently
...

When it comes to agents, they only work in fully observable environments
...
If the agent lacks information on certain
states, it won't be able to function properly
...


Model Based Reflex Agent
Going to discuss model based reflex agents and their application in real life situations
...
However, model based reflex agents take into
account the environment's dynamics and utilize a model to make more informed decisions
...
The model is the knowledge base,
created through past experiences and perceptions of the environment, similar to how the human
brain creates a knowledge base from learned information
...

New Points in Perception
● Perception from the environment
● Partially observable environment
● Agent does not have full knowledge of environment
These points differ from the simple reflex, where the environment was fully observable and the
agent had full knowledge of the environment
...


Meet the self-driving car, an advanced agent that is equipped with high-level and ultrasonic
sensors to navigate the road
...

Model-based Reflex Agent in a Partially Observable Environment
A model-based reflex agent works in a partially observable environment, where it cannot
observe the complete environment and can only observe certain points
...

However, it can perceive or sense something from the environment, analyze the current state of
the environment, and save that current state
...

This helps with memory retention and recall
...
This is an expansion on our previous post about model-based reflex agents
...
However, the key difference is that goal-based agents also have a
specific goal they are trying to achieve
...

Real-Life Examples of Goal-Based Agents
One example of a goal-based agent is a self-driving car
...
The car uses its sensors and a model of the
world to determine the best route to take and how to navigate traffic
...
The goal of a personal assistant is to
provide information and complete tasks for the user
...

Code Example
def goal_based_agent(goal): while not goal
...
get_best_action(goal)
perform_action(action)
This is a simplified example of a goal-based agent
...

When an AI system processes data through its sensors and knowledge base, it uses past
experiences to make decisions
...

Supervised Learning
Supervised learning is a type of machine learning where the input and output are known
beforehand
...
This is similar to how humans learn - by analyzing the current scenario and
using past history to achieve a known goal
...
This technique is reliant on two important factors: searching and
planning
...

Planning for a Bike Trip to Leh & Ladakh
Planning is essential to reach a goal state
...
The end goal is reaching Ladakh, starting from Delhi
...

● Ensure the bike is in good condition and serviced
...

● Plan for stops and accommodations along the way
...

Maybe you got there by bike, bus, or some other means of transportation
...


Utility Based Agents
Focus on Actions, Not the Goal State
It's easy to assume that the goal state is the ultimate focus of any task
...
This can help you
avoid confusion and distractions
...
However, it is
important to note that the goal state exists in the mind of the utility agent
...

When it comes to reaching a destination, the focus should be on utility
...
The utility function is used to measure
whether the agent is in a happy or unhappy state
...
This is similar to how happiness or
unhappiness is measured in human beings
...
Let's take a
real-life example where we are traveling from source to destination in a car, covering a distance
of 300-400 kilometers
...

However, we tend to follow the shortest path by default
...
However,
unforeseen events like traffic or protests can cause delays
...
In such a scenario,
the agent will take action to address the situation
...
For example:
● It may reroute to an alternate path to avoid traffic
● It may adjust the speed to ensure safe and efficient travel
● It may seek alternative means of transportation, such as public transit or ride-sharing
Ultimately, the goal is to reach the destination as quickly and safely as possible, even in the face
of unexpected challenges
...
The main focus of this approach is utility, which refers to the
usefulness or benefit of a decision
...
The utility function
is therefore crucial in determining the success of a decision
...
Fuzzy logic is a fascinating topic in artificial logic
...

What is Fuzzy Logic?
Fuzzy logic is a superset of boolean logic, which is the conventional method of representation
...
We are talking about either yes or no, and there is nothing
in between
...
However, in fuzzy
logic, we need to represent things in a continuous way
...
For example,
"I ate food today" can be represented as either "yes" or "no" (1 or 0)
...

● Boolean logic: "I ate food today" = 1 (true) or 0 (false)
● Fuzzy logic: "I ate food today" = 0
...
2 (mostly false)
With fuzzy logic, we can represent the degree of certainty or uncertainty in a statement, rather
than just a binary true or false value
...
For example,
instead of saying "I ate the food" or "I didn't eat the food," we might say something like "I ate a
lot of food
...

Today, I had a small meal and slept for an extended time
...

It is challenging to determine the intensity or level of these occurrences using boolean logic
...

Rather than relying solely on discrete values, fuzzy logic allows for more nuanced
decision-making
...
Some people may
find that six is too many, while others may feel unsatisfied with only ten
...


Various Operations in Fuzzy Logic with
Example
Operations in Fuzzy Logic
Gate Smashers welcomes you to a discussion on various operations in fuzzy logic
...

● Fuzzy AND operation: It is similar to the boolean AND operation, but it uses a minimum
function to evaluate the output
...

● Fuzzy OR operation: It is similar to the boolean OR operation, but it uses a maximum
function to evaluate the output
...

● Fuzzy NOT operation: It is used to find the complement of the input
...

These operations are useful in decision-making processes where we need to consider uncertain
or imprecise information
...
These exams often include questions related to this topic, which are generally easy
...
Understanding the operations is simple and once you learn how to solve
them, you'll be able to answer these questions with ease
...
Let's take a look at two common ones:
● Union: This operation combines two sets into one, without any duplicates
...

Complement, Bold Union, and Bold Intersection
In set theory, complement refers to the set of all elements in a universal set that are not in a
given set
...
For example, if the universal set is
the set of integers and A is the set of even integers, then AC is the set of odd integers
...
Bold
union, denoted by A ∪ B, is the set of all elements that are in A or in B or in both
...

● Complement: AC = {x | x is in the universal set and x is not in A}
● Bold union: A ∪ B = {x | x is in A or x is in B}

● Bold intersection: A ∩ B = {x | x is in A and x is in B}
These operations can be used to perform various set operations, such as finding the difference
between two sets, finding the intersection of multiple sets, and more
...
This is the
set that contains all the elements that we're interested in
...

In this case, our universal set contains the numbers 5 and 10
...
So, {5, 10} is the same as {10, 5}
...
So, if we have the sets {1, 2, 3} and {3, 2, 1}, they are equal because they contain the
same elements, even though the order is different
...
It is a
preferable topic for research and has various applications that we use on a daily basis
...
They are
designed to recognize patterns and make predictions based on data
...
They are widely used in machine learning and deep learning applications
...
In the context of
technology, artificial neural networks are used to process and analyze complex data sets
...

The Internet is a global network of computers and other electronic devices connected together
through various communication protocols
...

Users can access the Internet from their personal computers or mobile devices, using a variety
of technologies such as Wi-Fi, cellular networks, and satellite connections
...

Interconnected Neurons in the Human Brain

The human brain is made up of gazillions of interconnected neurons, forming a vast network
that enables the sharing and processing of information and data
...

In the human brain, learning algorithms play a crucial role in processing data quickly and
generating output
...
Scientists aim to replicate this process in machines through the use of artificial
neural networks
...
While there are no biological neurons in these networks,
they can still learn and improve over time
...

Essentially, a neural network is:
● A network of nodes or "neurons" that are connected to one another
...

● The network is designed to learn and improve over time through training and adjusting
weights and biases
...
In this
article, we will discuss NLP in detail with examples that can help you in various settings such as
competitive exams, college/university-level exams, and job interviews
...
Human beings communicate with each other using their natural language,
such as English, Hindi, Punjabi, and others
...

Why is NLP important?
● NLP enables machines to understand and interpret human language, which is essential
for various applications such as chatbots, virtual assistants, and voice recognition
systems
...

● NLP can be used for translation services, making it easier for people to communicate
with each other across different languages
...

● Voice assistants like Siri and Alexa that can perform various tasks based on voice
commands
...

In order for communication to be effective, there needs to be understanding between parties
...


Human behavior is intelligent in the way we communicate through natural language, and we
want computers to be able to replicate this
...
This is where Natural Language
Processing (NLP) comes in
...
Major IT
companies such as Google and Amazon are investing heavily in speech recognition
technology
...

Currently, the functionality may not work with all languages
...

Speech Recognition and Sentiment Analysis
Speech recognition is the process of interpreting and understanding spoken language, and
providing a valid response
...
These techniques are widely
used, particularly on social media platforms such as Facebook and Twitter
...
In addition, sentiment analysis can also be useful during elections
...
Python and
Tensorflow can be used for this in R programming
...

Supervised Learning
This is a type of machine learning where the algorithm is trained on a labeled dataset
...
The algorithm
learns to map the input to the output based on the labeled dataset and then uses this mapping
to predict the output for new inputs
...

Unsupervised Learning
In unsupervised learning, the algorithm is trained on an unlabeled dataset
...

Examples of unsupervised learning include clustering, anomaly detection, and dimensionality
reduction
...
The
algorithm then learns to map inputs to outputs based on this training data
...

Introduction to Unsupervised Learning

Unsupervised learning, on the other hand, involves training an algorithm on an unlabeled
dataset
...
Unsupervised learning is
useful for tasks such as clustering, anomaly detection, and dimensionality reduction
...
The agent receives feedback in the form of rewards or
penalties based on its actions, and the goal is to learn a policy that maximizes the long-term
reward
...

Types of Machine Learning
There are three main types of machine learning: supervised, unsupervised, and reinforcement
learning
...

Supervised Learning
Supervised learning is a type of machine learning where the model is trained on labeled data
...
This type of
learning is used for tasks like classification and regression
...
This
data is referred to as "supervised" because there is a teacher or supervisor giving instructions
...

We can create a model and input new data to check if it produces a valid output
...
Exit polls are
essentially training data where feedback is collected from various categories of people such as
youngsters, kids, and elders
...
It serves as input that is
used to generate an output
...
They input all possible outcomes into the
training data, including which candidates are likely to win or lose
...

Learning Algorithms
● Naive Bayes algorithm is used in supervised learning, where input and output are
already known
...


Genetic Algorithm
Genetic algorithm, including its important points, starting with the person who first proposed the
concept
...
Holland's work focused on the study of genes and their
role in the evolution of species
...
This process is similar
to the genetic algorithm used in artificial intelligence and machine learning where multiple
solutions are present, but the best ones are selected and used for further development
...
This can be compared to the process of parents giving birth to a child,
where the best traits are inherited and combined to create the optimal offspring
...
When it gives birth to its next generation, they will have even more special
characteristics
...
Normal algorithms take input
and generate an output, but that is not the case here
...
This is where population comes
into play
...
These complex problems are referred to as NP-Hard problems,
such as the traveling salesman problem and 0-1 Knapsack problem
...

The Genetic Algorithm in a Nutshell
The genetic algorithm is a method of finding the best solution from a given population or search
space
...
The best individuals from a
group will survive, and this process is repeated to find the optimal solution
...
CSP is a type of mathematical problem that
involves finding a solution to a set of constraints
...

What is the Constraint Satisfaction Problem?
CSP is a type of problem that involves finding a solution to a set of constraints
...
The goal of the problem
is to find a solution that satisfies all of the given constraints
...

● It is used in scheduling problems, such as employee scheduling or production
scheduling
...

CSP Algorithms
There are several algorithms that can be used to solve CSP problems
...
It
is widely used in the field of artificial intelligence and computer science
...

Understanding Constraint Satisfaction Problem (CSP)
In this article, we will be discussing the important points related to CSP, which can be beneficial
for your college/university exams or competitive exams
...

CSP refers to the problem of finding a solution to a set of constraints, where each constraint
represents a restriction on the possible values of the variables involved
...

In problem solving, we can use either uninformed or informed search techniques to explore
state space and move through different states
...
However, constraint
satisfaction problems require a different approach to representation
...

Let's take a look at some examples of problems that require a different representation method:
● Job scheduling problems
● Sudoku puzzles
● N-queens problem
Sudoku Game and Map Coloring
Sudoku game and map coloring are two examples of problems that involve coloring
...

On the other hand, map coloring involves coloring the regions of a map in such a way that no
two adjacent regions have the same color
...

Graph Coloring
Both Sudoku and map coloring problems can be modeled as instances of the graph coloring
problem
...
The goal is to assign colors to the nodes in such a way that no two adjacent
nodes have the same color
...

Algorithmic Approaches
● Backtracking: One of the most common approaches to solving the graph coloring
problem is backtracking
...
In the case of graph
coloring, backtracking involves trying out different color assignments to the nodes until a
valid coloring is found
...
The greedy algorithm works by selecting the node with the highest degree
(i
...
, the node with the most edges) and assigning it a color that is different from the
colors of its neighboring nodes
...

● Exact Algorithms: In some cases, exact algorithms can be used to solve the graph
coloring problem
...

Conclusion
Sudoku and map coloring are two examples of problems that involve coloring
...
There are several algorithmic
approaches to solving the graph coloring problem, including backtracking, greedy algorithms,
and exact algorithms
...
Similarly, CSP is also utilized for solving cryptarithmetic problems
...
For example, the
variable V1 has a domain of D1, which can be a real number while another variable may have a
domain of a natural number
...
We will also
provide an interesting example to help you understand better
...
These are problems where we need to find a
solution that satisfies a set of constraints
...

How to Solve CSP Problems?
There are various algorithms that can be used to solve CSP problems
...
It is a recursive algorithm that tries out different solutions and
backtracks when it encounters a solution that violates the constraints
...

An Example
Let's consider a simple CSP problem where we need to color a map with four colors such that
no two adjacent regions have the same color
...

So, this is how CSP problems can be solved using algorithms
...
Good luck!
In computer science, we use a method called backtracking algorithm to solve problems
...
To explain this, let's take the example of a constraint graph
that needs to be colored
...
To solve this problem, we can use the backtracking algorithm with intelligent
backtracking
...

In this graph, the variables are constantly changing, so it's important to understand the
fundamentals before diving into the specifics
...

Study Hack: Memorizing Numbers
If you struggle with memorizing numbers, there are a few tricks that can help
...
" With this method, you assign a specific shape to each
number (for example, 1 is a straight line, 2 is a curve, 3 is a loop, etc
...

Another method is called the "number rhyme system
...
Then, you create a mental
image of the number by visualizing the corresponding rhyme
...
For example, if you
need to remember the number 5247, you could create an acronym like "5 squirrels, 2 birds, 4
apples, 7 cats
...
"
Overall, finding a method that works for you and practicing regularly can make a big difference
in your ability to memorize numbers
...

Domain

The domain refers to a specific set of values or inputs for a particular function or system
...

In graph theory, we often need to assign colors to vertices
...
We need to assign a color to each vertex, but the
color can be any of these 3 colors:
● Red
● Green
● Blue
This is known as a 3-coloring of the vertices
...
It
involves dividing the problem into smaller subproblems, or branches, and then exploring each
branch individually to find the best solution
...
This node is then divided into smaller subproblems, or child nodes, which are explored
one at a time
...
If the child node has the potential for a better solution, it is added
to a priority queue
...

This process continues until all possible branches have been explored and a final solution is
found
...

Problem Generation
When generating a problem, we also generate its subprograms and sub-solutions
...

Calculation of Minimum Value
After conducting research, we have determined that the minimum value of the given equation is:
INSERT FORMULA HERE
Once we have calculated this value, we can then proceed to find further sub-solutions based on
it
...

Code Example
INSERT CODE EXAMPLE HERE

We utilize various methods to solve problems efficiently:
● Greedy algorithms
● Heuristic methods
● Divide-and-conquer approach
Branch & Bound Algorithm
Branch & Bound is a category of algorithms that involves extending the problem into
sub-problems
...
The term 'bound'
refers to ignoring partial solutions that cannot be better than the current best solution
...


0/1 Knapsack using Branch and Bound
Firstly, let's understand what the Branch & Bound algorithm is and how it works
...
If you are not familiar with
it, please check out that topic for a detailed explanation
...
For the 0/1 Knapsack problem specifically, we have
a bag with a certain capacity and we need to fit items into it according to their weights
...

Now, before we begin, it's important to note that the 0/1 Knapsack problem means that either an
item will be completely filled in the bag or not at all
...

Solving with Branch & Bound
First, we need to create a stage and space diagram
...
We are given 4 items with their
corresponding weights and profits
...
If we
insert the first item, we get a profit of 30 and it weighs 5
...
Next, we insert the second item, which gives us a profit of 28 and weighs 7
...

We will continue this process, creating nodes for each possible combination of items, and
calculating their profits until we have explored all possible paths
...

Knapsack Problem Solution Exploration
The knapsack problem requires finding the optimal set of items to add to a knapsack with limited
capacity in order to maximize profit
...
The current solution provides a profit of 58
...
If we insert item number one, we get the same solution of minus
58
...

● If we choose to insert item number one, we have two possibilities for item number two:
either we take it or not
...
If we do not take
it, we get a profit of thirty
...
Then, we can insert item number three with a profit of twenty and
remaining capacity of four
...
The profit in this case is forty-eight
...
We then have two possibilities for item number three: either we take it or
not
...
If we do not take it, we can insert
item number four with a profit of twenty-four and remaining capacity of two
...

Thus, the optimal solution is to take item number one, not take item number two or three, and
insert item number four with a profit of twenty-four and remaining capacity of two for a total profit
of minus seventy-four
...
Let's explore it further
...
If we take item 4, then we won't take item 3, so the profit will
be -74
...
However, our
capacity is 12, so we need to consider the profit and capacity both
...

● We can take item 4 and not take item 3, which will result in a profit of -74
...

So, the final solution is to take all items from 1 to 4, which will result in a profit of -74
...
If all other values are better than minus seventy-four,
you can ignore that large value and any other branches that do not lead to better solutions
...
In essence, this is the story of how to do pruning and
ignoring
...




---