Questions tagged [breadth-first-search]

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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
48 views

Does Breadth-First Graph Search need to store all all unique generated states?

I am reading Artificial Intelligence: A Modern Approach by Russel & Norvig. As I understood it, a breadth-first graph search stores explored states instead of explored nodes (where "nodes&...
ddk's user avatar
  • 1
0 votes
1 answer
46 views

Unable to understand Figure 3.13 Artificial Intelligence: a Moder Approach

I'm currently studying the functionality of BFS and the AIMA book shows . I am unable to replicate them using some trivial calculations. For example, if the BFS generates $10^6$ nodes per second and I ...
GABRIEL ÁNGEL CANALS SALLERAS's user avatar
0 votes
1 answer
202 views

What does the branching factor mean in the time complexity of Breadth-First Search (BFS)

Can someone explain where my math is off here? I am confused on the b - Branching Factor and how to calculate the worst-case scenario when running BFS. In a worst-case scenario BFS would have to hit ...
ImposterX1's user avatar
0 votes
0 answers
49 views

What is the theory behind rejecting too good heuristics in search problems?

Currently I have found that there is an article in which a search problem is posed and to solve it a heuristic is proposed which, in essence, is the solution of the problem itself. I seem to remember ...
Angelo's user avatar
  • 211
2 votes
2 answers
978 views

How do the BFS and DFS search algorithms choose between nodes with the "same priority"?

I am currently taking an Artificial Intelligence course and learning about DFS and BFS. If we take the following example: From my understanding, the BFS algorithm will explore the first level ...
Sergio's user avatar
  • 123
1 vote
0 answers
169 views

What would happen if we set the evaluation function in the best-first search algorithm as the cost of paths taken to new nodes?

I am reading Artificial Intelligence: A Modern Approach. In Chapter 3, Section 3.3.1, The best-first search algorithm is introduced. We learn that in each iteration, this algorithm chooses which node ...
Hamed's user avatar
  • 21
1 vote
2 answers
2k 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*?
JackoJackie's user avatar
1 vote
1 answer
338 views

A way to leverage machine learning to reduce DFS/BFS search time on a tree graph?

I'm not very knowledgeable in this field but I'm wondering if any research or information already exists for the following situation: I have some data that may or may not look similar to each other. ...
JungleBird's user avatar
2 votes
0 answers
622 views

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

In Artificial 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 ...
Gu Liqi's user avatar
  • 21
1 vote
1 answer
1k 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 ...
user avatar
2 votes
1 answer
6k 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)?
user avatar
1 vote
0 answers
76 views

2 Partition Problem

I want to solve the two partition problem (https://en.wikipedia.org/wiki/Partition_problem) using an uninformed search algorithm (BFS or uniform cost). The states can be represented by three sets S1,...
hyuj's user avatar
  • 131
3 votes
1 answer
5k 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?
Alaz Sengul's user avatar
1 vote
1 answer
308 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 ...
Tim's user avatar
  • 11
2 votes
1 answer
4k 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.
Samia Afzal's user avatar
2 votes
1 answer
7k 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?
Marosh Fatima's user avatar
4 votes
1 answer
216 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 importance of heuristics in it. George Katona (an early psychologist) published in the ...
GundamOfOasis's user avatar
10 votes
5 answers
8k 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 ...
user avatar
1 vote
0 answers
224 views

How can we find the number of node expansions performed by BFS in this hexagonal map?

An agent aims to find a path on a hexagonal map, with an initial state $s_0$ in the center and goal state $s^*$ at the bottom as depicted below. The map is parametrized by the distance $n \geq 1$ ...
akano1's user avatar
  • 111
5 votes
1 answer
3k 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 ...
xava's user avatar
  • 423