CODEWITHSUNDEEP
pythonartificial-intelligenceheuristicsplanning
Daki Withanage
Daki Withanage

Reputation: 53

Is squared Euclidien distance a admissible heuristic?

enter image description here

I have a grid such as shown in the picture. So far I have implemented below functions as my heuristic functions. So the goal of this game is to collect all the numbers placed on this grid. Starting point A.

  1. Manhattan distance and then take the maximum of it to calculate the heuristic.
    distance = abs(A_x-x_i)+abs(A_y-y_i)
    if distance > manhMax:
       manhMax = distance
  1. Summation of all the Manhattan distances to numbers placed. (This I presume is not admissible since it over estimate the distance to reach the goal-correct me if I am wrong)

My question is, first method expand states more than what I need and the second method is not admissible. I am implementing my own heuristic at the moment.

I came up with the idea, calculating squared Euclidean distance between distance between distances from A to 2 and then to 1 and then to 3 and 0. There is no order as such to collect the numbers. However the problem is just Euclidean distance expand too many states though it is admissible. Could you help me with a suitable distance or method to achieve my task.

Thank you!

Upvotes: 2

Views: 721

Answers (1)

Prune
Prune

Reputation: 77847

I suspect you're having trouble interpreting your approach, because this problem does not have the simple, single-goal paradigm used to define "admissible". Rather, you have a small TSP (Traveling Salesman Problem), in which you can collect the items in any of 4! orders. You didn't describe which distance you used in your approach, but no simplistic computation will do. Adding all 10 distances (for n=5 nodes; 5x4 / 2) is simply over-spending, as you will traverse only 4 of those edges. Similarly, adding the distances from A to each of the items is wrong.

Instead, you need to use the heuristic on each edge of the path, add then generate the heuristic estimate for the four-edge path under consideration. For this treatment, Euclidean distance is admissible -- but its square is not: it seriously overestimates, and is in the wrong units (area, rather than distance). Manhattan distance will likely be better for you.

Note that you have a problem case in this example, as edge 3-0 will be underestimated by a factor of 4 to 5, depending on your heuristic.

Upvotes: 1

Related Questions