Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
