CODEWITHSUNDEEP
algorithmpath-findinga-starheuristics
OscarCampo
OscarCampo

Reputation: 45

How to design a cost function and a heuristic function that finds the FASTEST route using an A* pathfinding algorithm?

I am currently making a road network pathfinding program that I want to be able to find the shortest route (by distance) as well as the fastest route (time) using A* pathfinding.

For the SHORTEST route, I am using the (length of a road) as the cost and I'm using euclidean distance from the neighboring node to the end node as the heuristic. This works fine.

However, when trying to find the FASTEST route (by time), I am assuming that cars will travel at the speed limit constantly so I am using the (length of the road / speed limit of the road) as the cost. For the heuristic, I am using Euclidean distance from the neighbouring node to the end node, divided by the speed limit of the road used to get to that neighboring node. This seems to work fine however when I use the SHORTEST path algorithm between that same start and end points, I will often get a faster travel time, which is not what I want.

I understand that my cost and heuristic need to be of the same degree, and that the heuristic function needs to be consistent and admissable. I am unsure whether I am designing the cost and heuristic for finding the fastest route correctly though. If I'm not along the right idea already, how would I go about finding the fastest path?

Edit: SOLVED

Upvotes: 2

Views: 1237

Answers (1)

OscarCampo
OscarCampo

Reputation: 45

Using straight line distance to the goal node / highest speed limit of any road in the network as the heuristic means the estimated cost (time) will never overestimate the true cost of the path. The problem in my code was that my original heuristic was overestimating. The suggestion by @btilly fixed the problem as the heuristic is admissible and will underestimate the cost.

Upvotes: 2

Related Questions