When searching over a graph expressed as a uniform, 8-connected grid using the A* algorithm, is there any way to give a rough approximate of the number nodes expanded? I appreciate this is a somewhat complex problem, and am not expecting to make startling accurate predictions.
The information we have available is:
- Start and goal vertices
- Graph/grid configuration - vertex occupancy and connection information
- Heuristic and cost functions used
Initial idea
We could use a log of previous searches between macro regions, and thus obtain a mean region-region node expansion count. However, it would be preferable to have a heuristic that does not depend on historical data; or to have a slightly more refined version of the above-mentioned approach.