For questions related to the depth-first search algorithm, in the context of artificial intelligence.
Questions tagged [depth-first-search]
12 questions
9
votes
2 answers
Why is depth-first search an artificial intelligence algorithm?
I'm new to the artificial intelligence field. In our first chapters, there is one topic called "problem-solving by searching". After searching for it on the internet, I found the depth-first search algorithm. The algorithm is easy to understand, but…
himari
- 93
- 5
3
votes
1 answer
Does depth-first search always stop when it has found the leftmost solution?
I'm a fresh learner of AI. I was told that depth-first search is not an optimal searching algorithm since "it finds the 'leftmost' solution, regardless of depth or cost". Therefore, does it mean that in practice, when we implement DFS, we should…
Hang
- 133
- 2
3
votes
1 answer
How DFS may expand the same state many times via different paths in an acyclic state space?
I am reading the book titled Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig (4th edition) and came across this sentence about depth-first search (page 79, line 12):
For acyclic state spaces it may end up expanding the…
user153245
- 123
- 8
3
votes
1 answer
Why does our AI play worse at even levels of depth?
We are building an AI to play a board game. Leaving aside the implementation, we noticed that it plays worse when we set an even (2,4,6,...) level of depth. We use a minimax depth-first strategy.
Do you have any ideas why it behaves like that?
Edit:…
Tom Dwan
- 33
- 3
3
votes
1 answer
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
- 33
- 1
- 5
2
votes
1 answer
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
- 23
- 1
- 4
2
votes
2 answers
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 containing $B$ and $C$, then the second level containing…
Sergio
- 123
- 5
1
vote
0 answers
How to improve the efficiency of the backtracking search in CSPs?
Backtracking search is the basic uninformed search algorithm for constraint satisfaction problems (CSPs). How could we improve the efficiency of the backtracking search in CSPs?
Abbas Ali
- 566
- 3
- 10
- 17
1
vote
1 answer
How to find the order in which DFS algorithm will inspect the nodes?
I have been taking Artificial Intelligence course in College. I came upon this problem. Now here I have to find the order in which DFS algorithm inspects the nodes and what is the path from Start to Goal State. And wherever this contention between…
astraltrinity
- 13
- 3
1
vote
1 answer
How do I create the search tree for DFS applied to a grid map?
I have been working through some search tree problems and came across this one:
Assume that that the algorithm has a closed list and that nodes are added to the frontier in the following order: Up, Right, Down, Left. For example, if node J is…
Gerhardus Carinus
- 83
- 5
1
vote
1 answer
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. Each represents a node that represents a vector of…
JungleBird
- 11
- 2
0
votes
0 answers
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 that in search problems based on heuristics (e.g.…
Angelo
- 201
- 2
- 16