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,037
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 ...
- 9,794
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/...
- 361
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
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 ...
- 9,794
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, ...
- 37k
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,037
1
vote
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 ...
- 37k
1
vote
How do the BFS and DFS search algorithms choose between nodes with the "same priority"?
Either one. The BFS algorithm and DFS algorithm do not specify.
Typically, it's programmed as left-to-right, just because that's the way programmers think about trees. It doesn't have to be.
Note that ...
- 659
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,143
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,375
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 ...
- 37k
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 ...
1
vote
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,037
Only top scored, non community-wiki answers of a minimum length are eligible