Questions tagged [depth-first-search]
For questions related to the depth-first search algorithm, in the context of artificial intelligence.
13 questions
1
vote
1
answer
312
views
Why the space complexity of depth-first search is O(bm)?
In "Artificial Intelligence: A Modern Approach", the authors say that the space complexity of depth-first search is proportional to O(bm), considering b as the branching factor and m the ...
- 111
0
votes
0
answers
71
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 ...
- 211
1
vote
1
answer
575
views
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 ...
3
votes
1
answer
852
views
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 ...
- 185
2
votes
2
answers
1k
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 ...
- 123
1
vote
1
answer
601
views
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, ...
2
votes
1
answer
418
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. ...
- 21
9
votes
2
answers
2k
views
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 ...
- 93
3
votes
1
answer
464
views
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 ...
- 33
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?
- 33
3
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.
- 33
1
vote
0
answers
4k
views
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?
- 566
3
votes
1
answer
1k
views
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 ...
- 133