What is Heuristic in AI | Why we use Heuristic | How to Calculate Heuristic | Must Watch

Summary

In this video, the concept of heuristic functions in artificial intelligence is explored, explaining their role in making educated guesses to find quick solutions. The script delves into why heuristics are used, particularly in solving complex problems with exponential time complexity, such as in puzzles like the 8 puzzle, and games like chess. It also covers various methods to calculate heuristic values, including Euclidean and Manhattan distances, and the number of misplaced tiles, emphasizing that while heuristics ensure good solutions, they do not guarantee optimal ones. The video is a guide for those interested in AI search techniques, aiming to convert NP problems into more manageable polynomial time solutions.

Takeaways

• 🧠 **Heuristic Definition**: A heuristic in AI is a technique for making educated guesses or finding quick solutions to problems.
• 🔍 **Purpose of Heuristics**: Heuristics are used to simplify the search process in AI by making assumptions to find solutions more efficiently.
• 🔄 **Problem with Uninformed Search**: Uninformed search methods can lead to exponential time complexity, making them impractical for large problems.
• 📈 **Exponential Growth Issue**: The time complexity in problems like the 8-puzzle grows exponentially, leading to a vast search space with billions of possible states.
• 🏹 **Heuristic Advantage**: Heuristics can help in quickly finding good solutions by guiding the search towards more promising paths based on heuristic values.
• 🎯 **Non-Optimality of Heuristics**: While heuristics guarantee good solutions, they do not always ensure the optimal solution due to their nature of making assumptions.
• 🛣️ **Heuristic Methods**: Methods like Euclidean distance, Manhattan distance, and counting misplaced tiles are used to calculate heuristic values.
• 📚 **Euclidean Distance**: The straight-line distance between points, used as a heuristic to estimate the minimum distance to the goal.
• 🚶 **Manhattan Distance**: A heuristic used in grid-based problems like the 8-puzzle, calculating the sum of the horizontal and vertical distances to the goal.
• 🔢 **Misplaced Tiles Count**: A heuristic method that counts the number of tiles not in their goal positions to estimate the distance to the solution.
• 🔧 **Heuristic Use Cases**: Heuristics are particularly useful when a quick solution is needed, and when converting NP problems into more manageable polynomial time complexity.
• 🛠️ **Informed Search Techniques**: Heuristics are a part of informed search techniques, which use additional information, like heuristic values, to guide the search process.

Q & A

What is a heuristic function in artificial intelligence?

A heuristic function in AI is a technique designed to solve a problem quickly by making assumptions and finding a quick solution or a 'rule of thumb' to guide the search towards a good solution, although it may not always be the optimal one.

Why are heuristic values used in artificial intelligence?

Heuristic values are used to reduce the time complexity of solving problems, especially in cases where the search space is exponentially large, by guiding the search towards promising paths and avoiding blind search through all possible states.

What is the difference between informed and uninformed search in AI?

Informed search uses heuristic information to guide the search process, making it more efficient, while uninformed search, also known as blind search, explores all possible states without any guidance, which can be time-consuming and inefficient for large search spaces.

What is the time complexity of an uninformed search in the worst case for an 8 puzzle problem?

The worst-case time complexity for an uninformed search in an 8 puzzle problem is O(b^d), where b is the branching factor and d is the depth of the search space, approximately 3^20 states.

What is the significance of heuristic functions in solving NP problems?

Heuristic functions help in solving NP (non-polynomial) problems by reducing the search time from exponential to polynomial, thus providing quick solutions, although not necessarily the optimal ones.

How does a heuristic function differ from a greedy method?

While both heuristic functions and greedy methods aim to find good solutions quickly, heuristic functions provide a way to estimate the cost to reach the goal state and guide the search, whereas greedy methods simply choose the most promising option at each step without considering the overall path.

What is Euclidean distance and how is it used in calculating heuristic values?

Euclidean distance is the straight-line distance between two points in a plane, calculated using the formula \(\sqrt{(X2 - X1)^2 + (Y2 - Y1)^2}\). It is used in heuristic calculations to estimate the minimum distance to the goal state.

What is Manhattan distance and how does it relate to the 8 puzzle problem?

Manhattan distance is the sum of the absolute differences of their Cartesian coordinates, representing the distance a person would travel on a grid of streets (like in Manhattan). It is used in the 8 puzzle problem to calculate the heuristic value based on the number of moves needed to align tiles vertically or horizontally to their correct positions.

What is the concept of 'misplaced tiles' in the context of the 8 puzzle problem?

In the context of the 8 puzzle problem, 'misplaced tiles' refers to the count of tiles that are not in their correct positions in the goal state. This count is used as a heuristic to estimate how far the current state is from the goal state.

Why might a heuristic not always guarantee an optimal solution?

A heuristic does not always guarantee an optimal solution because it is based on assumptions and estimations that simplify the search process. There may be scenarios or obstacles not accounted for in the heuristic that could lead to a suboptimal path being chosen.

What are some common informed search techniques that use heuristic values?

Some common informed search techniques that use heuristic values include Heuristic DFS, Heuristic BFS, Hill Climbing, and the A* algorithm, which are designed to find good solutions more efficiently than uninformed search methods.

Outlines

00:00

🧠 Introduction to Heuristics in AI

This paragraph introduces the concept of heuristics in artificial intelligence, explaining it as a method to make quick assumptions or find a quick solution to a problem. The speaker uses the analogy of solving mathematical problems with assumptions to illustrate the point. Heuristics are presented as a technique to solve problems efficiently, especially in the context of AI where the search space can grow exponentially. The paragraph also touches on the limitations of blind search methods and the exponential time complexity they can incur, such as in the 8-puzzle and chess, highlighting the need for heuristics to find good solutions more quickly, even if they may not always be optimal.

05:06

🛠 Heuristic Functions and Informed Search Techniques

The second paragraph delves into the use of heuristic functions and values in informed search techniques, which guide the search process towards a good solution more quickly. It explains that heuristic values are not guaranteed to find the optimal solution but are useful for finding good solutions in a reasonable time frame. The paragraph introduces different methods for calculating heuristic values, such as Euclidean distance, Manhattan distance, and the number of misplaced tiles, using examples like the 8-puzzle to illustrate how these methods work. It emphasizes the efficiency of these methods in reducing the search space and improving the time complexity compared to blind search.

10:07

🚀 Applications and Limitations of Heuristics

The final paragraph discusses the practical applications of heuristics, explaining why they are used and their limitations. It points out that heuristics are particularly useful when a quick solution is needed and when attempting to solve non-polynomial problems in polynomial time. The speaker uses real-life scenarios to illustrate that while heuristics can guide towards a good solution, they do not always guarantee the optimal one due to unforeseen obstacles. The paragraph concludes by emphasizing the role of heuristics in informed search algorithms like A* and other optimization techniques, acknowledging their importance in finding good solutions efficiently.

Keywords

💡Heuristic function

A heuristic function is a method used in artificial intelligence to estimate the cost or effort required to reach a goal state from a given state. It plays a crucial role in informed search algorithms, helping to guide the search towards the most promising paths. In the video, the heuristic function is discussed as a means to quickly find a solution to a problem, often sacrificing the guarantee of finding the optimal solution for the sake of efficiency.

💡Heuristic value

The heuristic value represents an estimate of the distance or cost from the current state to the goal state in a problem-solving context. It is used to prioritize different paths or states in search algorithms. The script explains that heuristic values help in making assumptions and quick decisions, as seen in the examples of the 8 puzzle and the discussion of different methods to calculate heuristic values.

💡Artificial Intelligence (AI)

Artificial Intelligence refers to the simulation of human intelligence in machines that are programmed to think like humans and mimic their actions. The video's theme revolves around the use of heuristics in AI, particularly in problem-solving scenarios where AI must make decisions or find solutions efficiently. AI is the broader field within which heuristic functions and values are applied.

💡Uninformed search

Uninformed search, also known as blind search, is a search method that explores possible solutions without any domain-specific knowledge. The script mentions uninformed search in the context of exploring all possible states in a problem space, which can lead to exponential time complexity, highlighting the inefficiency compared to informed search methods that use heuristics.

💡Informed search

Informed search is a type of search algorithm that uses additional information, such as heuristic values, to guide the search process towards the goal more efficiently. The video explains that informed search techniques, aided by heuristic values, can significantly reduce the time complexity compared to uninformed search, making them suitable for solving complex problems more quickly.

💡Euclidean distance

Euclidean distance is a measure of the straight-line distance between two points in Euclidean space. In the context of the video, it is used as a method to calculate the heuristic value by estimating the direct distance from the current state to the goal state. The script provides an example of how Euclidean distance can be used to quickly determine the path of least resistance in problem-solving.

💡Manhattan distance

Manhattan distance is the distance between two points in a grid-based system, based on the sum of the absolute differences of their Cartesian coordinates. The video script uses the Manhattan distance as an example of how to calculate the heuristic value for the 8 puzzle problem, emphasizing its use in estimating the minimum number of moves to reach the goal state.

💡Misplaced tiles

In the context of the 8 puzzle problem discussed in the video, misplaced tiles refer to the tiles that are not in their correct positions in the goal state. The number of misplaced tiles is used as a heuristic to estimate the effort required to solve the puzzle, with fewer misplaced tiles indicating a closer proximity to the goal state.

💡NP problems

NP, short for Non-deterministic Polynomial time, refers to a class of problems in computational complexity theory that are at least as hard as the hardest problems in NP. The script mentions NP problems to illustrate the challenges of finding optimal solutions in polynomial time, and how heuristics can be used to find good solutions more quickly, even if they are not guaranteed to be optimal.

💡A* algorithm

The A* algorithm is a popular informed search algorithm that combines the benefits of Dijkstra's algorithm (for finding the shortest path) with a heuristic to estimate the cost to the goal. The video script highlights the A* algorithm as an important technique that utilizes heuristic functions to efficiently navigate through large search spaces and find solutions in a more time-effective manner.

Highlights

Heuristic functions in AI are used to make assumptions and find quick solutions.

In mathematics, heuristics can simplify problem-solving by making initial assumptions, like setting variables to 100.

Heuristics in AI are techniques designed for quick problem-solving, contrasting with uninformed search methods.

Uninformed search can lead to exponential time complexity, making it inefficient for large problems like the 8-puzzle.

The 8-puzzle problem illustrates the exponential growth of search space, with up to 3^20 possible states.

For larger puzzles like the 15-puzzle, the search space can reach up to 10^13 states, showing the scalability issue.

In chess, the search space can grow up to 35^80 due to a high branch factor and depth, highlighting the need for heuristics.

Heuristic functions help in finding good solutions quickly without guaranteeing the optimal solution.

Heuristics reduce time complexity by guiding the search towards paths with the best heuristic values.

Informed search techniques use heuristic values as a guide to efficiently navigate the search space.

Heuristic values can be calculated using methods like Euclidean distance, Manhattan distance, and counting misplaced tiles.

Euclidean distance is used to calculate the straight-line distance between nodes in a search space.

Manhattan distance calculates the sum of the absolute differences in each dimension, useful in grid-based puzzles.

Counting misplaced tiles is a method to estimate the distance to the goal state by counting incorrectly positioned elements.

Heuristics provide a good solution but do not guarantee the optimal solution due to the potential presence of obstacles.

Heuristics are particularly useful when a quick solution is needed, and the conversion from NP to polynomial time is desired.

Informed search algorithms like A* utilize heuristics to improve search efficiency over uninformed or brute force methods.

Transcripts

Hello friends, welcome to Gate Smashers

In today's video we are going to discuss

What is heuristic function

Heuristic value in artificial intelligence

Why we use heuristic

And how to calculate the heuristic value

In artificial intelligence you will get many topics

Where we use heuristic values and heuristic functions

So guys in this video we are going to discuss all 3 points

What why and how

So guys quickly like the video

And subscribe the channel if you have still not done

Please press the bell button

So that you can get all the latest notifications

So first of all we will start with what is heuristic in artificial intelligence

Simple meaning of heuristic is

Making assumption for anything

That means we are trying to guess or we are trying to find a quick solution

If talk other then artificial intelligence

As we solve questions in normal mathematics

That cost price is given to you

Or the cost price is twice the selling price

These type of questions comes or many times question comes like

This is the simple interest then find out what will be the principal amount

If this much time is given to you

So generally how do we solve these type of questions

What we do to solve these questions

Let X=100

That means let cost price be this

Or let principle be this

So it is actually helping us

To find out the answer quickly

You can do it without that also

But somewhere it is helping us in finding the answers quickly

So in artificial intelligence we use heuristic

So it is a technique designed to solve a problem quickly

As we discuss about informed and uninformed search in last video

So what are we in telling in uninformed

We are doing blind search

We are going in all the state spaces of the problem

And the state which match is our goal state

Then our search will stop

But due to that what is the problem

Our problem what is given actually in the question

That problem is growing exponentially time

Our time can be exponential time

If we talk about 8 puzzle problem

Simple about 8 puzzle problem also

So if you do it in blind search way

Then in worst case how much actually it can go

Time complexity is O(b^d)

In case of uninformed

Or 3^20

Approximate 3^20

Search space is possible

If you will search and compare these many states

Then obviously time complexity will increase

Because around 3- 3.4 billion state are created

If instead of 8 puzzle you take 15 puzzle

Although in 15 puzzle you have only 4 moves

Up down left and right

Even after that 10^13 search space are possible

And if you take 24 puzzle

Then in that 10^24 states are possible

So if such a huge number is there

So somewhere a time complexity is growing exponential time

In case you are taking some big game

If you are taking chess then the branch factor in chess

The value of b can be up to 35

And the value of d can grow up to 80 or 90

Then 35^80

That is a very huge number

So if you want to calculate these values

What do we call these type of problems

NP that is non polynomial problem

And obviously in non polynomial over time complexity is exponential

In this we have one advantage

It will definitely give optimal solution

So I want that this much time should not be used

We want to find out a quick solution

Or we also call it as rule of thumb

That means that we are finding out a solution

With a greedy method

We are finding the best method

So due to that my time

That time is reduced

Because this finds out with which way?

It finds out that you have multiple solutions

Instead of exploring all the solutions

The one which is the best whoes heuristic value is the best

You go on that method

That means if we have these much solutions

Let's say it's heuristic value is 10

And its heuristic value is 15

Then the value which is less

Generally if we talk in the way of distance or time

Then we generally talk that the lower number is best for us

Then lower the number if its cost is less

Then what we will do we will move towards this side

That means we will not explore this side

In worst case it is possible that I have to do on this side also

But generally what we do

Because heuristic functions

That gives us guarantee that it will provide us good solutions

But optimal solution may come or may not come

This is not guaranteed

It can come also and it may not come also

Wherever we want to solve non polynomial problem in polynomial time

We want to solve it quickly

Over there we use heuristic functions

Or heuristic value

And generally over here all the informed search techniques

In that we say what is the meaning of informed search

We have a guide

We have an information

What is the information actually

Heuristic value

This is the concept actually

Why do we use euro stock value so that we can find out quickly

We know that good solution will come

But optimal solution can come and even it cannot come

And how do we calculate

That how do we calculate heuristic value

There are different methods for it

Like one method is

Euclidean distance

That is called a straight line distance if you want to find out

Let's say if you have One node

You have a start node

Let's say this is your goal state

You consider it as a city

If this is your start state

This is your goal state

Let's say to go till goal state

You have these 3 different states

Other than these there can be other also

What you want to reach at goal state

In minimum cost

If you want to reach earliest

Then obviously how will you find out

What is the best method for you

That you find out the distance

It is called a straight line distance

Which we call as Euclidian distance

So what we do to find this out

This is X1 and Y1

These are its coordinates X2 and Y2

Then we will do ((X2 - X1)^2 +(Y2-Y1)^2)^2

Show over here we are taking square root of whole

So if you find out the distance

Obviously you will come to know that this is the minimum distance

Because this distance you can come to know by seeing only that it is more

But this distance will be less

So obviously instead of exploring them

You will directly go in this path

So you don't have to explore multiple path

But in blind search you have to go over here also

Over here also over here also

So obviously your complexity will go on increasing

Or we use Manhattan distance

We use Manhattan distance basically if we want to find out vertical and horizontal distance

Like if you take example of 8 puzzle problem

In 8 puzzle problem let's say we have

Start state is given

Goal state is given

This is our start state

And lets say this is our goal state

In goal state we want 1 2 3

4 5 6

7 8

And this is empty

And lets say you take start state as 1

3 2

5 6 4

8

7

Anything

Your start state can be any

So if you want to go from start state to goal state

So as I told in 8 puzzle

If you do blind search

Then there are 3^20 possible search space

Then you will get an final optimal answer

And you will achieve goal state

But if we want to calculate heuristic value over here

Then I can find it out with the help of Manhattan distance

What is the meaning of Manhattan distance

That you calculate the distance

For example one is there is one on its right position

According to the goal state

It is on the right position

So that means how many movements you will have to do

Vertically or horizontally how many movements you have

You don't have to do any movement

One is at its place

Look at 2

Actually 2 should be over here

Because it is over here in the goal state

But 2 is over here

So if you will move this one left side

Then obviously it will come on it's right position

That means how much distance you have to cover? 1

In the same way let's say 3

3 is over here but you want it should reach over here

This is your goal state

So obviously if we will move one

Then it will reach at its right position

Look at 4

4 is over here

And in this case it is over here

So if you will move this two position left

If you move it horizontally 2 towards left

Then it will reach at its right position

So its distances 2

5 is on the right position so zero

Sixes over here for that you will have to do 2 right

So add 2 in this

Plus 7

For 7 you will have to move 2

8

8 is already on the right position

So this will be your Manhattan distance

So now multiple states when you will explore this

When you will move this empty space towards up on the left side

The multiple branches that will be formed

You find out from that multiple branches whose heuristic value

Whose Manhattan distance is less so you follow that path

This is one of your method

Or we can also use one more method in this

If you calculate number of misplaced tiles

Let's say over here 1 is at its right position? Yes

2 is there? No it not

So 1 will come

You have to find the number of misplaced tiles

So look over here is 3 at its right position ? No

Is 2 is not at its right position, so 2

1 is at its right position so it is okay

4 is at it's right position? No

3

5 is there? Yes

6 is at right position? No

4 are there

7

7 is at right position? No

5 are there

8 is on right position? Yes it is at right position

That means total misplaced tiles are 5

When you will convert it into branches and make multiple branches

Then you find the misplaced

In which there are less number of misplaced

You explored that path

So that in less time and cost

You will get your solution

There are multiple ways it depends on the solution

Like we can use Elucedian distance

We can use Manhattan distance

Or we can use number of misplaced tiles

So with these methods we are making an assumption

We are calculating heuristic values

Or you can say that like rule of thumb

That I will go towards this way

Because it is taking me to the minimum path

But I want to tell last point over here

We have discussed what is this why we use and how

But always remember in heuristic

It always gives the guarantee

To find the good solution

But it does not give the guarantee

To find the optimal solution

Blind search will give optimal

Greedy will give you optimal or not it is not guaranteed

Yes it gives guarantee of good solution

See with a simple example

As we had calculated Eucledian distance over here

Obviously you will follow this path only

Because the distance of this as compared to all the other is less

But if you consider this in real life scenario

You are going from one place to another

Then there will be very rare chances that you will get a straight line

Or you will get state path

Let's say you started following this path

And in future you came to know

That over here mountain is there

Let's suppose if there is any obstacle over here

Mountain is there so obviously what will happen

You will go over here and follow the path this way

So what is better it is possible that this path

Or this path can take you in minimum distance

These are the methods

That is why it does not give guarantee to find optimal

Yes it gives guarantee of good solution

So mainly when is heuristic used

Or why should we use

When we want the solution quickly

When we want to convert it from NP to polynomial time

Yes in worst case this can also go to non polynomial

But in normal average or best case

It will perform better

Better in terms of time as compared to the blind search

Or what we call as brute force method

Or which we called as uninformed search

So informed search we use heuristic

In which heuristic DFS heuristic BFS hill climbing is there

A* algorithm which is very important

We discuss all these algorithms

Thank you