Heuristic Search by Kainat

Heuristic SearchArtificial Intelligenceby KAINAT BAIGBCS VI semester (Batch: 2008-2010) : 

Heuristic SearchArtificial Intelligenceby KAINAT BAIGBCS VI semester (Batch: 2008-2010)

Heuristic Search : 

Heuristic Search The heuristic search technique is basically the hierarchy of following searches... Best-first search Greedy best-first search A* search Admissible Heuristics Hill-climbing search Simulated annealing search Genetic algorithms ...are all too slow for most real world problems

Heuristic Search : 

Heuristic Search The meaning of heuristic is a guess which is best, not exact. The heuristic tells us approximately how far the state is from the goal state. Heuristics are employed in two cases. A problem may not have an exact solution because of its inherent ambiguities. e.g. medical diagnosis It would take too long to find an exact solution e.g. chess

Slide 4: 

Application of AI using Heuristics Game playing and theorem proving Othello Chess checker Expert Systems

Analysis of the Heuristic Function : 

Analysis of the Heuristic Function In developing a good evaluation function for the states in a search space, you are interested in two things: g (n): How far is state n from the start state? h (n): How far current node from goal? g (n); is important because you often want to find the shortest path (depth count) h (n); Evaluation function. This gives us the following evaluation function: F (n) = g (n) + h (n)

Admissible heuristics : 

Admissible heuristics A heuristic search is admissible if it is guaranteed to find the shortest path to a goal. H1: No of tiles out of space H2: the sum of distances of tiles from their goal position, this called as “ Manhatten Distance” or “Block Distance”. Q) What is heuristic? Define admissible heuristic with example.

Admissible heuristics : 

Admissible heuristics In this case, only “8” is misplaced, so the H1 evaluates to 1. H1= 1 In other words, the heuristic is telling us, that it thinks a solution might be available in just 1 more move Current State > Goal State >

Admissible heuristics : 

Admissible heuristics 3 3 8 8 1 1 2 spaces 3 spaces 3 spaces Current State > Goal State > In this case, only the “3”, “8” and “1” tiles are misplaced, by 2, 3, and 3 squares respectively, so the heuristic function evaluates to 8. H2= 2 + 3 + 3 = 8 Total = 8

Q) How a good heuristic is useful in problem solving? : 

Q) How a good heuristic is useful in problem solving? Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to come to an optimal solution as rapidly as possible. Part of this method is using a "rule of thumb ", an educated guess, an intuitive judgment, or common sense. A heuristic is a general way of solving a problem. Or simply put the heuristic method of problem solving is a rule of thumb. Heuristic programs do not always reach the very best result but usually produce good results within a reasonable amount of search time. Specific heuristics are used in specialized areas, often-specific subject domains or professions. There are three common methods in heuristic problem solving. First, the most powerful general heuristic is to form a sub-goal to reduce the discrepancy between your present state and your ultimate goal state. Do something to get a little closer to the end goal. Problems defy one-shot solutions. They must be broken down into smaller parts. Example Here are a few other commonly used heuristics, If you are having difficulty understanding a problem, try drawing a picture. If you can't find a solution, try assuming that you have a solution and seeing what you can derive from that ("working backward"). If the problem is abstract, try examining a concrete example. A)