Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Would using Markov Chains be helpful? – Johannes Kloos Jul 24 '12 at 15:24
To clarify: Consider each graph expansion as a state, the expansion of a single node as an edge from the unexpanded to the expanded graph and give probabilities according to the heuristic and cost functions. Then we can use Markov chain methods to calculate the average number of explored notes in the final states of that Markov chain. – Johannes Kloos Jul 24 '12 at 15:29
I am not really too familiar with that system being a programmer... (but apparently I should be! ;) Roughly how would it be applied, and is it feasible for an online algorithm? – Martin Källman Jul 24 '12 at 15:29
Sounds interesting! I wonder if it will actually prove to be slower than the actual A* search, though? – Martin Källman Jul 24 '12 at 15:31
The thing is that the Markov chain would have a largish state space, so I don't think this would work really well for an on-line algorithm. Maybe you could use the rate of decrease of the cost function as a crude estimate? – Johannes Kloos Jul 24 '12 at 17:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.