16
votes
How do I keep track of already visited states in breadth-first search?
Dennis Soemers' answer is correct: you should use a HashSet or a similar structure to keep track of visited states in BFS Graph Search.
However, it doesn't quite answer your question. You're right, ...
- 9,392
8
votes
Accepted
How do I keep track of already visited states in breadth-first search?
You can use a set (in the mathematical sense of the word, i.e. a collection that cannot contain duplicates) to store states that you have already seen. The ...
- 10.5k
8
votes
How do I keep track of already visited states in breadth-first search?
While the answers given are generally true, a BFS in the 15-puzzle is not only quite feasible, it was done in 2005! The paper that describes the approach can be found here:
http://www.aaai.org/Papers/...
- 371
3
votes
Accepted
Why does the adversarial search minimax algorithm use Depth-First Search (DFS) instead of Breadth-First Search (BFS)?
The primary reason is that Breadth-First Search requires much more memory (and this probably also makes it a little bit slower in practice, due to time required to allocate memory, jumping around in ...
- 10.5k
3
votes
How do I keep track of already visited states in breadth-first search?
Ironically the answer is "use whatever system you want." A hashSet is a good idea. However, it turns out that your concerns over memory usage are unfounded. BFS is so bad at these sorts of problems,...
- 131
2
votes
Why is breadth-first search only optimal when the cost solution is a non-decreasing function?
This is well covered in the corresponding chapters of Russell & Norvig (Ch. 3 & 4). It also depends on the distinction between TREE-SEARCH and GRAPH-SEARCH.
First, note that Breadth-first ...
- 9,392
2
votes
Accepted
How do I train a bot to solve Katona style problems?
Your intuition is right: this is fundamentally a problem for combinatorial search.
You're also right that problems are created by the fact that not every move is valid at state. To fix this, you need ...
- 9,392
2
votes
Is there any situation in which breadth-first search is preferable over A*?
The only general situation that comes to my mind where BFS could be preferred over A* is when your graph is unweighted and the heuristic function is $h(n) = 0, \forall n \in V$. However, in that case, ...
- 41.4k
2
votes
Accepted
How do the BFS and DFS search algorithms choose between nodes with the "same priority"?
BFS and DFS are usually applied to unweighted graphs (or, equivalently, to graphs where the edges have all the same weights). In this case, BFS is optimal, i.e., assuming a finite branching factor, it ...
- 41.4k
1
vote
Does Breadth-First Graph Search need to store all all unique generated states?
States are represented by nodes in the graph. In other words, a state is a node in the graph. So, I don't think there's any difference, but some authors maybe make a difference (e.g. because you don't ...
- 41.4k
1
vote
Unable to understand Figure 3.13 Artificial Intelligence: a Modern Approach
The table's "Nodes" column uses rough approximations, as do most of the values in the table, because it is trying to give an intuition about scaling, and not accurate predictive values for ...
- 33.3k
1
vote
Accepted
What does the branching factor mean in the time complexity of Breadth-First Search (BFS)
Math is just fine. Its all about the definition of $\mathrm{O}(\cdot)$. Checkout the wiki page about Big-O Notation.
Basically, your function $T(b) = 1 + b + b^{2} + \cdots + b^{d}$ belongs to the ...
- 915
1
vote
Is there any situation in which breadth-first search is preferable over A*?
There is an inherent assumption in heuristic search that the heuristic function points you in the right direction.
A* largely depends on how good the heuristic function is. Two nice properties for the ...
- 3,213
1
vote
Accepted
What is the space complexity of breadth-first search?
The space complexity of the breadth-first search algorithm is $O(b^d$) in the worst case, and it corresponds to the largest possible number of nodes that may be stored in the frontier at once, where ...
- 41.4k
1
vote
How do I keep track of already visited states in breadth-first search?
Approaches to the Game
It is true that the board has $16!$ possible states. It is also true that using a hash set is what students learn in a first year algorithms courses to avoid redundancy and ...
- 7,513
1
vote
How do I model the blocked N queens problem as a search problem?
In general, the process of modelling a problem as a search problem consists in creating a graph which contains nodes, which represent the possible states in your problem, and edges, which represent ...
- 41.4k
1
vote
Accepted
Why do we use a last-in-first-out queue in depth-first search?
We use the LIFO queue, i.e. stack, for implementation of the depth-first search algorithm because depth-first search always expands the deepest node in the current frontier of the search tree.
Norvig ...
1
vote
Accepted
What is the difference between the breadth-first search and recursive best-first search?
According to this article
Breadth First Search (BFS) searches breadth-wise in the problem space. Breadth-First search is like traversing a tree where each node is a state which may a be a potential ...
Only top scored, non community-wiki answers of a minimum length are eligible