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, ...
John Doucette's user avatar
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 ...
Dennis Soemers's user avatar
  • 10.2k
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/...
Nathan S.'s user avatar
  • 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 ...
Dennis Soemers's user avatar
  • 10.2k
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,...
Cort Ammon's user avatar
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 ...
John Doucette's user avatar
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 ...
John Doucette's user avatar
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, ...
nbro's user avatar
  • 40.1k
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 ...
nbro's user avatar
  • 40.1k
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 ...
nbro's user avatar
  • 40.1k
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 ...
pi-tau's user avatar
  • 692
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 ...
user253751's user avatar
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 ...
Djib2011's user avatar
  • 3,183
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 ...
nbro's user avatar
  • 40.1k
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 ...
Douglas Daseeco's user avatar
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 ...
nbro's user avatar
  • 40.1k
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