CODEWITHSUNDEEP
algorithma-starheuristics
Ashwin
Ashwin

Reputation: 13517

Why is this manhattan heuristic inadmissble?

In this article, which explains the A* algorithm, it says that for that for the given problem (finding shortest distance between two points where there is a wall as an obstacle), the Manhattan distance is not admissible. See this
Why is that? Does it overestimate the distance in any case? If yes, when?

Upvotes: 1

Views: 351

Answers (1)

mcdowella
mcdowella

Reputation: 19601

Here is a chunk from aStarLibrary.bb (following links from your link)

;Figure out its G cost If Abs(a-parentXval) = 1 And Abs(b-parentYVal) = 1 Then addedGCost = 14 ;cost of going to diagonal squares
Else
addedGCost = 10 ;cost of going to non-diagonal squares
End If Gcost(a,b) = Gcost(parentXval,parentYVal)+addedGCost

    ;Figure out its H and F costs and parent
    Hcost(openList(m)) = 10*(Abs(a - targetx) + Abs(b - targety)) ; record the H cost of the new square

The heuristic (Hcost) for a move from (0, 0) to (1,1) will be 10 * (1 + 1) = 20. The GCost (cost of a move) treats this a single diagonal move of cost 14. So yes, it is an over-estimate.

Upvotes: 3

Related Questions