CODEWITHSUNDEEP
artificial-intelligencepath-findingheuristicspacman
Quinty
Quinty

Reputation: 199

How can I tell if a particular heuristic is admissible, and why mine is not?

The definition of an admissible heuristic is one that "does not overestimate the path of a particular goal". I am attempting to write a Pac-Man heuristic for finding the fastest method to eat dots, some of which are randomly scattered across the grid. However it is failing my admissibility test. Here are the steps of my algorithm:

sum = 0, list = grid.getListofDots()
1. Find nearest dot from starting position (or previous dot that was removed) using manhattan distance
2. add to sum
3. Remove dot from list of possible dots
4. repeat steps 1 - 3 until list is empty
5. return the sum

Since I'm using manhattan distance, shouldn't this be admissible? If not, are there any suggestions or other approaches to make this algorithm admissible?

Upvotes: 1

Views: 1605

Answers (1)

manlio
manlio

Reputation: 18902

As said your heuristics isn't admissible. Another example is:

Pacman heuristics

Your cost is 9 but the best path has cost 6.

A very, very simple admissible heuristics is:

number_of_remaining_dots

but it isn't very tight. A small improvement is:

manhattan_distance_to_nearest_dot + dots_left_out

Other possibilities are:

distance_to_nearest_dot   // Found via Breadth-first search

or

manhattan_distance_to_farthest_dot

Upvotes: 2

Related Questions