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.

Filter by
Sorted by
Tagged with
6 votes
2 answers
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? ...
Data's user avatar
  • 161
5 votes
1 answer
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 ...
Artery's user avatar
  • 153
4 votes
1 answer
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 ...
Christopher King's user avatar
3 votes
2 answers
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}$ ...
KGhatak's user avatar
  • 165
2 votes
1 answer
190 views

How to deal with huge branching factors in real-time?

Some time ago playing chess was challenging for algorithms, then Go game which is vastly more complex than compared to chess. How about playing RTS game which have enormous branching factors limited ...
kenorb's user avatar
  • 10.5k
2 votes
1 answer
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)?
user avatar
1 vote
1 answer
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 ...
Inertial Ignorance's user avatar
1 vote
0 answers
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 ...
Baffo rasta's user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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)?
user avatar
1 vote
0 answers
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 ...
TurbulentWinds's user avatar
1 vote
0 answers
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$ ...
akano1's user avatar
  • 111