For questions concerning the breadth-first search (BFS) algorithm, which is an algorithm for traversing or searching tree or graph data structures. BFS starts at the root of the tree (or graph), then explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

13 questions
Filter by
Sorted by
Tagged with
4k views

### How do I keep track of already visited states in breadth-first search?

I was trying to implement the breadth-first search (BFS) algorithm for the sliding blocks puzzle (number type). Now, the main thing I noticed is that, if you have a $4 \times 4$ board, the number of ...
176 views

### How do I train a bot to solve Katona style problems?

Cognitive psychology is researched since the 1940s. The idea was to understand human problem solving and the importants of heuristics in it. George Katona (an early psychologist) published in the ...
829 views

### Why is breadth-first search only optimal when the cost solution is a non-decreasing function?

I am learning about searching strategies in AI and I was reading that breadth-first search is only optimal when the cost solution is a non-decreasing function? I am not really sure what this refers to ...
1k views

### Why does the adversarial search minimax algorithm use Depth-First Search (DFS) instead of Breadth-First Search (BFS)?

I understand that the actual algorithm calls for using Depth-First Search, but is there a functionality reason for using it over another search algorithm like Breadth-First Search?
2k views

### Why do we use a last-in-first-out queue in depth-first search?

Why do we use a last-in-first-out (LIFO) queue in the depth-first search algorithm? In the breadth-first search algorithm, we use a first-in-first-out (FIFO) queue, so I am confused.
2k views

### What is the difference between the breadth-first search and recursive best-first search?

What is the difference between the breadth-first search and recursive best-first search? How can I describe the key difference between them?
37 views

### Why do we use the tree-search version of breadth-first search or A*?

In Artiﬁcial Intelligence A Modern Approach, search algorithms are divided into tree-search version and graph-search version, where the graph-search version keeps an extra explored set to avoid ...
62 views

### Is there any situation in which breadth-first search is preferable over A*?

Is there any situation in which breadth-first search is preferable over A*?
111 views

### How do I model the blocked N queens problem as a search problem?

The blocked N-queens is a variant of the N-queens problem. In the blocked N-queens problem, we also have a NxN chess board and N queens. Each square can hold at most one queen. Some squares on the ...
156 views

### What is the space complexity of bidirectional search?

Is the space complexity of the bidirectional search, where the breadth-first search is used for both the forward and backward search, $O(b^{d/2})$, where $b$ is the branching factor and $d$ the length ...
449 views

### What is the space complexity of breadth-first search?

When using the breadth-first search algorithm, is the space complexity $O(b^d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?