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
1
vote
0
answers
137
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
1
answer
2k
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 ...
user42125
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)?
user42125
1
vote
1
answer
3k
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)?
user42125
1
vote
0
answers
42
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 ...
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}$ ...
- 165
5
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 ...
- 271
1
vote
1
answer
736
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
0
answers
262
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$ ...
- 121
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? ...
- 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 ...
- 153
2
votes
1
answer
205
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 ...
- 10.5k