0
$\begingroup$

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.

  • 0
    A slightly cheaper alternative could be f(h,c,ratio_n) = pow(h,c*ratio_n) where `h` is the heuristic function, and `ratio_n` is the occupied:unoccupied vertex ratio on the whole graph.2012-07-24

0 Answers 0