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, ...
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 ...
user avatar
  • 9,379
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/...
user avatar
  • 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,...
user avatar
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 ...
user avatar
  • 9,379
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, ...
user avatar
  • 33.8k
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 ...
user avatar
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 ...
user avatar
  • 33.8k
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 ...
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 ...
user avatar
  • 3,093
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 ...
user avatar
  • 33.8k
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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible