2
$\begingroup$

Im currently enrolled in an AI course and we are starting with state space search problems. My professor always seems to ask, given a certain problem, what is the estimate size of the state space? It's been 3 years since ive taken a course in discrete math which is the type of question I am asking.

How can I use things like branch factor and depth to estimate state space?

Improve this question
$\endgroup$
1
  • $\begingroup$ Try drawing particular examples and see what you get. For example, if the branch factor is 2 then you have a binary tree. How many nodes does a binary tree of depth $d$ contain? And so on. Give it a few hours. $\endgroup$
    – Yuval Filmus
    Feb 17, 2017 at 8:17

1 Answer 1

Reset to default
0
$\begingroup$

So lets take an 8 queens problem. Intially the size of state is 64C8 where 64 is the number of squares in a chess board and 8 is the number of queens that can be placed.

Now lets say, you can only put one queen in each column so that's only 8 squares available. This reduces the branching factor from 64 to 8. Now the size of state is 8C8 only.

Now lets say, you can only use 2 queens instead of 8. This reduced the depth from 8 to 2. So in this case instead of being 8 queens , now it's going to be a 2 queens problem. So that changes the size of state from 8C8 to 8C2. Cheers man.

Improve this answer
$\endgroup$

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.