4 ms·
> Along the way I learned the hard way that the heuristic in a* algorithm should never return higher value than the minimal value that that will be actually ass
by Doctor_Fegg 5y ago
> Along the way I learned the hard way that the heuristic in a* algorithm should never return higher value than the minimal value that that will be actually assigned to the path to destination. That is, if you want algorithm to result in optimal path.
That's true, but if you don't mind sacrificing a bit of optimality, then overstating the heuristic can speed up the calculation. This is called "overdo" in 'Fast shortest path computation in time-dependent traffic networks' (Lefebvre and Balmer).
- yxhuvud 5y agoOverstating the heuristic was sadly not an option here though, as sacrificing optimality doesn't give the right answer.
- snovv_crash 5y agoEven cooler, the ratio you overstate the heuristic by is the ratio of how close your result is guaranteed to be to the optimal result. It's a really nice performance slider to have on problems that don't require optimal results (ie. most engineering problems).
- taneq 5y agoYou're not wrong, that's really cool. Thanks!