CODEWITHSUNDEEP
algorithmtime-complexitybreadth-first-searchspace-complexity
Nico
Nico

Reputation: 3489

Time and Space Complexity for Breadth First Search

I just wanted to check if my understanding of the algorithm and calculations given in Russell and Norvig are correct or not.

I am using Missionaries and Cannibals as a problem to test the time and space complexity. Calculating depth is not that big of a deal. I always find the solution at depth 11. What I can't wrap my head around is the branching factor.

Russell and Norvig page 82 says:

"There will be O(b^(d-1)) nodes in the explored set and O(b^d) nodes in the frontier..."

My program shows 8502 nodes in the explored set and 14006 nodes in the frontier.

Here's the way my thought process is going: If I take the number of nodes and take the d root according to Russell and Norvig, I should get what the branching factor is. Now I have no idea if what I am thinking is correct or not. I just came up with it.

So I take the 10th (d-1) root of 8502 and get 2.47 (approximately) and I take the 11th (d) root of 14006 and get 2.39 (approximately). So my conclusion is that the branching factor b is roughly 2.43.

Am I at all hitting the mark or do I have it completely wrong? This is one of those things that I'm just winging right now. But would love to know if I am wrong or right.

Upvotes: 1

Views: 1352

Answers (1)

user2566092
user2566092

Reputation: 4661

Your estimation of the branching factor based on the explored set and the frontier set is essentially correct. For small depth, the estimation of the branching factor is more legitimate for the frontier set than the explored set, because the explored set includes all vertices visited in the past which is more like 1 + b + ... + b^(d-1) rather than just b^(d-1). Note that as the explored set grows, you will have more and more neighbor vertices that have been already explored, so the approximation b^d for the frontier set will become less and less good as the depth increases. In the extreme case, when you have explored all vertices you will have that the frontier set contains no vertices, so you will approximate b^d as 0. But anyway, your estimation procedures look good and give highly consistent results between the frontier set and the explored set. You should probably use the frontier set alone to give the estimate of the branching factor.

Upvotes: 1

Related Questions