Search heuristics are important in improving the efficiency of a search problem. This post will describe what heuristics are and why they are used in artificial intelligence applications. I will cover some of the standard topics in heuristics which are admissible and consistent heuristics.
What are heuristics?
Heuristics can be said to be estimates of how far the goal state is. Heuristics basically predict how far the goal state maybe or how much it will cost to get to the goal state from a particular node. Now the question that arises is, when we know the cost of getting to the goal state from every node why do we have to search at all? We don’t know the cost of getting to the goal state, we have an estimate or prediction for it which may or may not be correct.
Let us take an example to demonstrate how we can estimate costs of reaching a goal state. Consider the maze below:
Let the opening at the left of the maze be the start state, and the one at the top be the goal state. We consider the maze to be split into blocks having (x,y) co-ordinates, with the width of a path being 1 block. It is quite difficult for us to say how many steps a person may have to move to get to the goal state, since we will have to solve the search problem to find that. It makes no sense to solve a search problem to find out a heuristic, since heuristics are meant for the efficient solving of search problems.
Now imagine the maze without any walls or obstacles. What would be the shortest path then? It would be a steps to the right and b steps to the top. This is called the Manhattan distance between two points and can be used as a heuristic for the given maze. Another obvious heuristic is the Euclidean distance between the two points.
It can also be clearly seen that heuristics don’t give the actual cost of the path. In this particular example, if we use the Euclidean distance as a heuristic, there are points that are far from the goal state as compared to the start state, but the actual cost of getting to the goal state from these points is smaller than the actual cost from the start state.
Admissible Heuristics
A heuristic is said to be admissible if the value of the heuristic is always smaller than or equal to the actual cost of getting to the goal state.
Consistent Heuristics
A heuristic is said to be consistent if the heuristic value for every edge is smaller than or equal to the actual cost of the edge. The heuristic value for an edge might be defined as h(AB) = h(A) – h(B). The heuristic of an edge AB is the heuristic value at A minus the heuristic value at B.
It is an obvious statement to say that if a heuristic is consistent then it is also admissible.
It is an obvious statement to say that if a heuristic is consistent then it is also admissible.
Let us take the following diagram as an example for admissible and consistent heuristics:
Clearly h1 is an admissible heuristic. But it is not consistent since the heuristic value for edge SA is 2 whereas the true value is 1. Also h2 is both admissible as well as consistent.
Virtual event platforms will automatically track user behavior in ways that reveal true engagement levels and As hybrid and other in-person event formats begin to return. party invitation email and online event registration and payment
ReplyDeleteJoin for the top Artificial Intelligence Training in Hyderabad. In AI Patasala, aspirants can avail the benefits of demonstration sessions of the AI Program.
ReplyDeleteArtificial Intelligence Course Hyderabad
Artificial Intelligence – Search Heuristics >>>>> Download Now
ReplyDelete>>>>> Download Full
Artificial Intelligence – Search Heuristics >>>>> Download LINK
>>>>> Download Now
Artificial Intelligence – Search Heuristics >>>>> Download Full
>>>>> Download LINK cq
Artificial Intelligence – Search Heuristics >>>>> Download Now
ReplyDelete>>>>> Download Full
Artificial Intelligence – Search Heuristics >>>>> Download LINK
>>>>> Download Now
Artificial Intelligence – Search Heuristics >>>>> Download Full
>>>>> Download LINK 1i