# Tag Info

### 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
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

### 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

### 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
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

### 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
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