# Heuristic Search by Kainat

Views:

Category: Education

## Presentation Description

No description available.

## Presentation Transcript

### 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 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.