Questions tagged [depth-first-search]

For questions related to the depth-first search algorithm, in the context of artificial intelligence.

Filter by
Sorted by
Tagged with
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 ...
himari's user avatar
  • 93
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
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 ...
Hang Chen's user avatar
  • 133
3 votes
1 answer
730 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 ...
user153245's user avatar
3 votes
1 answer
412 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 ...
Tom Dwan's user avatar
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 ...
Sergio's user avatar
  • 123
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
1 vote
1 answer
480 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, ...
Gerhardus Carinus's user avatar
1 vote
1 answer
95 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 ...
Zaratruta's user avatar
  • 111
1 vote
1 answer
494 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 ...
astraltrinity's user avatar
1 vote
1 answer
352 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
1 vote
0 answers
3k 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?
Abbas Ali's user avatar
  • 566
0 votes
0 answers
50 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