# Questions tagged [branching-factors]

For questions about the branching factor of a tree's (or graph's) node, i.e. the number of children of that node (or its outdegree). The time and space complexity of many traditional search algorithms, such as A* or depth-first search, is often given as a function of the branching factor.

12 questions
Filter by
Sorted by
Tagged with
1 vote
123 views

### Is N the total number of nodes in the frontier plus the number of nodes in the explored list?

I'm studying fundamentals of AI from the classic Russell-Norvig book (3rd edition). I have a small doubt about the effective branching factor, which is defined as follows (section 3.6.1, p. 103): One ...
• 111
1 vote
1k views

### What is the space complexity of bidirectional search?

Is the space complexity of the bidirectional search, where the breadth-first search is used for both the forward and backward search, $O(b^{d/2})$, where $b$ is the branching factor and $d$ the length ...
6k views

### What is the space complexity of breadth-first search?

When using the breadth-first search algorithm, is the space complexity $O(b^d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?
1 vote
2k views

### What is the space complexity of iterative deepening search?

When using iterative deepening, is the space complexity, $O(d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?
1 vote
38 views

### Maximum Single Ply Branching Factor for Legal Checkers Boards

I am writing a checkers move generation function in C that will be extended to Python. It is much easier to handle the possible boards in a fixed size array to pass back to Python. Basically, I build ...
2k views

### Why is the effective branching factor used for measuring performance of a heuristic function?

For search algorithms with heuristic functions, the performance of heuristic functions are measured by the effective branching factor ${b^*}$, which involves the total number of nodes expanded ${N}$ ...
• 165
1k views

### Which algorithms can we use on games with high branching factors (e.g. Connect6)?

Connect6 is an example of a game with a very high branching factor. It is about 45 thousand, dwarfing even the impressive Go. Which algorithms can we use on games with such high branching factors? I ...
1 vote
660 views

### Why was Go a harder game for an AI to master than Chess?

AI became superior to the best human players in chess around 20 years ago (when the 2nd Deep Blue match concluded). However, it took until 2016 for an AI to beat the Go world chess champion, and this ...
1 vote
225 views

### How can we find the number of node expansions performed by BFS in this hexagonal map?

An agent aims to find a path on a hexagonal map, with an initial state $s_0$ in the center and goal state $s^*$ at the bottom as depicted below. The map is parametrized by the distance $n \geq 1$ ...
• 111
2k views

### Are leaf nodes included in the calculation of average branching factor for search trees?

In the search tree below, there are 11 nodes, 5 of which are leaves. There are 10 branches. Is the average branching factor given by 10/6, or 10/11? Are leaves included in the calculation? ...
• 161
2k views

### Is the 'direction' considered, when determining the branching factor in bidirectional search?

If I am correct, the branching factor is the maximum number of successors of any node. When I am applying bidirectional search to a transition graph like this one below If 11 is the goal state and I ...
• 153