0
$\begingroup$

In the below diagram, each node takes up a space of 2KB. I need to find the total memory consumed to reach the goal : I

I know that the equation for BFS is

b1 + b2 + ...... + (bd+1 - b)

Where b is the branching factor and d the depth

But how do I calculate the branching factor in the below diagram, where the branches are uneven?

Also, is the depth on A node 0 or 1?

State Space

$\endgroup$
0
$\begingroup$

In the case of the above diagram, as you mention, there is no constant branching factor. This means that we cannot solve for the number of nodes explored using the formula you give above.

Instead, we must use knowledge of how BFS works in order to calculate which nodes were visited before Node I was found. In BFS, nodes adjacent to the current node are marked, and then placed in a queue. The next element in the queue is visited (and removed from the queue), and this process repeats. Use this process to figure out which nodes are visited before Node I, and then charge a cost of 2kB for visiting each node.

$\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.