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
3
votes
1answer
37 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 and came across this sentence about depth-first search: For acyclic state spaces it may end ...
1
vote
2answers
35 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 ...
1
vote
1answer
72 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, ...
1
vote
1answer
105 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. ...
0
votes
0answers
56 views

How can I translate this deep-first search pseudocode into JavaScript?

In the paper Using Cyclic Scheduling to Generate Believable Behavior in Games, Richard Zhao and Duane Szafron describe a tool that is able to generate schedules for NPCs. The tool The tool offers a ...
9
votes
2answers
1k 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 ...
3
votes
1answer
92 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 ...
3
votes
1answer
2k 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?
2
votes
1answer
3k 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.
2
votes
0answers
1k 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?
3
votes
1answer
387 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 ...