With reference to the Heuristics section of Classical planning in Artificial Intelligence: A Modern Approach by Russell and Norvig, there is a question: consider an air cargo problem with 10 airports, 50 planes, and 200 pieces of cargo. Each plane can be at one of 10 airports and each package can be either in one of the planes or unloaded at one of the airports. So there are 5010 × 20050+10 ≈ 10155 states.

I think it should be 1050 + (50+10)200 (each of the 50 planes can be in any of 10 places; each of the 200 packages can be in any of the 50 planes or unloaded at any of the 10 airports).

What is the actual number of states?


You're both wrong. It should be $10^{50} \times (10+50)^{200}$. If you have $k$ objects, and there are $n$ possible places for each, there are $n^k$ possible combinations of ways for where to put each of them.

This probably doesn't really change the main point that I suspect the AI book was making: there are a lot of possible states, far too many to iterate over one by one.

| cite | improve this answer | |
  • $\begingroup$ Then my point was correct :) $\endgroup$ – Achyuta Aich Nov 4 '15 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.