2

sites like GoogleMaps have an option to not only find the shortest path on the road from city A to city B, but also the path that will take least time (different roads have different speed limits).

To find a shortest path from A to B, the heuristic is straighforward - it's simply the Euclidean distance (let's assume the map isn't too big) between the currently observed node and B.

What if we're interested in shortest time AND take the speed limit for a particular edge into consideration?

My guess is that the weights of particular nodes will be representing time taken to get there and the heuristic would be

(double) Euclidean_distance(node,B)/maximum_speedlimit_in_country

Is my guess correct or am I missing something?

Thank you in advance.

Improve this question

1 Answer 1

Reset to default
1

I'm not 100% sure if that's actually what they use, but your heuristic seems admissible to me since it isn't overestimating the cost at any node (so, paths found using the heuristic will be optimal).

Improve this answer
4
  • The logic of ''seems optimal to me since it isn't overestimating the cost at any node'' doesn't sound right to me. A heuristic cost of 0 for every node also doesn't overestimate any cost, but it certainly isn't optimal (or even any kind of useful). Besides, it's very difficult to ever justify calling any heuristic optimal, unless it's the ''heuristic'' consisting of pre-computing and storing in memory the true shortest path cost, but that's not feasible for large maps. Ultimately I do agree with your answer though, that this heuristic seems like a reasonable guess.
    – Dennis Soemers
    Commented Mar 20, 2017 at 11:30
  • A* heuristics are optimal if they are admissible, which means paths using them are optimal. They aren't necessarily the most useful. I meant this heuristic would be valid and give the shortest path. The requirement for admissibility is that the distance to the goal is never overestimated. Refer to en.m.wikipedia.org/wiki/Admissible_heuristic - the introductory section, and the section on search algorithms.
    – Anish Goyal
    Commented Mar 20, 2017 at 13:58
  • 1
    No, the A* search algorithm is optimal (in that it find an optimal solution if one exists) if the heuristic is admissible. But the heuristic itself isn't optimal. I don't really think there's even a definition of an ''optimal heuristic''. I'd take it to mean that a heuristic function is optimal if and only if there exists no other function that is gives scores that are closer to the truth. So, the only optimal heuristic function would be the one that memorizes all true shortest path costs. That's just my interpretation though, I don't think the ''optimal heuristic'' actually exists.
    – Dennis Soemers
    Commented Mar 20, 2017 at 14:34
  • 1
    @Dennis, that's what I meant, although I see how that could've been awkwardly worded. Note that I said "paths using them are optimal". Nonetheless, I updated the original answer to reflect this.
    – Anish Goyal
    Commented Mar 20, 2017 at 14:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.