Questions tagged [breadth-first-search]

Use for questions concerning Breadth-First Search (BFS)

Filter by
Sorted by
Tagged with
2
votes
1answer
63 views

Understanding the proof that A* search is optimal

I don't understand the proof that $A^*$ is optimal. The proof is by contradiction: Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume $...
0
votes
1answer
51 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 ...
1
vote
2answers
338 views

Difference between Graph Search and Tree Search

First of all, there is a lot of misunderstanding about the Graph search and Tree search. The difference between these two is not about Graph and Tree. They have two different algorithms. You can find ...
0
votes
1answer
375 views

Breadth first search VS recursive best first search?

What is the difference between breadth first search and recursive best first search ? How can I describe the key difference between them?
4
votes
1answer
157 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 ...
9
votes
7answers
2k views

Keeping track of visited states in Breadth-first Search

So I was trying to implement BFS on a Sliding Blocks puzzle (number type). Now the main thing I noticed that is if you have a 4*4 board the number of states can be ...