I'd be interesting to dive into bounds and good properties for sets of landmarks.
I imagine that if,
- Every node is at least X cost/distance away from a landmark
- Landmarks are no closer than Y cost/distance from each other
You can start promising a lot about the size of your open set on any execution.
A* on h* (perfect heuristic) takes O(l) where l is the length of the solution (could expand exactly l nodes, but solving/guessing ties incorrectly might bump this to a multiple around the avg edges per vertex).
I imagine that having good bounds mean you'll take no longer than a certain amount of expansions/depth before you lock-into the railway that h* provides (and you need some extra work to get off it too).
Comments
Damn, isn't A* fun and intuitive?
I'd be interesting to dive into bounds and good properties for sets of landmarks.
I imagine that if, - Every node is at least X cost/distance away from a landmark - Landmarks are no closer than Y cost/distance from each other
You can start promising a lot about the size of your open set on any execution.
A* on h* (perfect heuristic) takes O(l) where l is the length of the solution (could expand exactly l nodes, but solving/guessing ties incorrectly might bump this to a multiple around the avg edges per vertex). I imagine that having good bounds mean you'll take no longer than a certain amount of expansions/depth before you lock-into the railway that h* provides (and you need some extra work to get off it too).