Answers.Body: <p>First, note that the verb <strong>to expand</strong> has a specific meaning in this context: when you expand a node/state <span class="math-container">$s$</span>, you try each action <span class="math-container">$a_1, \dots, a_n$</span> available from <span class="math-container">$s$</span>, and each of these actions <span class="math-container">$a_i$</span> leads to another state.</p>
  <p>Second, if the graph is a DAG, then the edges have a direction and there are no cycles; so, if you follow the edges, you will never get back to a node that you have already been at. However, this is not sufficient to understand that statement and why or when it is true.</p>
  <p>Third, that statement is true only if you use the <a href="https://ai.stackexchange.com/a/9554/2444"><strong>tree search</strong></a> version of the depth-first search, i.e. you don't keep track of the nodes that you have already <em>explored</em>. In other words, you don't use <a href="https://ai.stackexchange.com/a/9554/2444"><strong>graph search</strong></a>, which is a tree search but that keeps track of the already expanded nodes in a set called the <strong>explored set</strong> (or <em>closed list</em>), so that to avoid expanding them again. So, here, if you explored a node/state <span class="math-container">$s$</span>, you added it to the <em>explored set</em>, so you won't expand it again.</p>
  <p>So, why is it possible to expand a node more than once in the tree search version of DFS? Well, you don't keep track of the nodes that you already expanded, so if you encounter it again from another path, you may expand it again. Given that it's a DAG (and assuming it's finite), then you will eventually try all possible paths, so you will find the goal.</p>
  <p>Now, here's an example of when you expand a node more than once in the tree search version of DFS.</p>
  <p>Let's say we have this search space, where you start at <span class="math-container">$A$</span> and the goal is <span class="math-container">$E$</span>.</p>
  <pre><code>A -&gt; B -&gt; C -&gt; D
  A -&gt; C -&gt; D  
  A -&gt; E
  </code></pre>
  <p>If the nodes are at the same depth, let's assume that you expand them alphabetically; so, in the search space above, you expand first <span class="math-container">$B$</span> and then <span class="math-container">$C$</span>, because <span class="math-container">$B$</span> comes before <span class="math-container">$C$</span> (in the English alphabet).</p>
  <p>Now, note that we can go directly to <span class="math-container">$C$</span> from <span class="math-container">$A$</span> or we can go to <span class="math-container">$C$</span> by first going to <span class="math-container">$B$</span>. <span class="math-container">$C$</span> has a child. When you expand <span class="math-container">$C$</span>, basically, you try the possible actions from <span class="math-container">$C$</span>. In this case, there's only one action, i.e. going to <span class="math-container">$D$</span>.</p>
  <p>So, without keeping track that you expanded <span class="math-container">$C$</span>, when you got there from <span class="math-container">$B$</span>, after you backtracked from <span class="math-container">$D$</span> the first time, you will try again to expand <span class="math-container">$C$</span>. In the graph search, this would not be possible because, the first time we expand <span class="math-container">$C$</span>, we add it to the <strong>explored set</strong>, so we don't expand it again.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-30T10:22:30.980Z
Answers.Text: The explored set could be some internal flag in every node. Look at garbage collection algorithms. Read the [GC handbook](https://gchandbook.org/)
Answers.UserDisplayName: Basile Starynkevitch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-08T07:15:07.947Z
Answers.Text: Thank you for your reply. I did not consider directed state space graphs at all. In addition, it can not be inferred from the context of that section of the book. So, can we conclude that the statement is correct only in directed graphs and not in general?
Answers.UserDisplayName: user153245
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-08T12:54:13.593Z
Answers.Text: @user153245 I didn't think about the case of undirected graphs. I'm also not sure how you would define cycles in an undirected graph, as every edge is a cycle (in a way), but, of course, this is probably not the definition of a cycle in an undirected graph. In the context of undirected graphs, you probably need also to keep track of the edges that you already visited.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-07T17:25:43.293Z
Answers.LastActivityDate: 2021-11-07T17:30:46.210Z
Answers.LastEditDate: 2021-11-07T17:30:46.210Z
Answers.UserDisplayName: nbro
Body: <p>I am reading the book titled <a href="http://aima.cs.berkeley.edu/" rel="nofollow noreferrer">Artificial Intelligence: A Modern Approach</a> by <em>Stuart Russell and Peter Norvig</em> (4th edition) and came across this sentence about depth-first search (page 79, line 12):</p>
  <blockquote>
  <p>For acyclic state spaces it may end up expanding the same state many
  times via different paths, but will (eventually) systematically
  explore the entire space.</p>
  </blockquote>
  <p>My question is: how this is possible? Can you please show me some examples?</p>
  
Tags: <search><state-spaces><norvig-russell><depth-first-search><state-space-search>
Title: How DFS may expand the same state many times via different paths in an acyclic state space?
UserDisplayName: user153245
ThreadText: # How DFS may expand the same state many times via different paths in an acyclic state space?
  
  (Asked by: username_0 on 2021-11-07)
  
  I am reading the book titled [Artificial Intelligence: A Modern Approach](http://aima.cs.berkeley.edu/) 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 same state many
  > times via different paths, but will (eventually) systematically
  > explore the entire space.
  
  My question is: how this is possible? Can you please show me some examples?
  
  **Tags:** search, state-spaces, norvig-russell, depth-first-search, state-space-search
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-11-07. Score: 1 | Accepted answer
  
  First, note that the verb to expand has a specific meaning in this context: when you expand a node/state $s$, you try each action $a_1, \dots, a_n$ available from $s$, and each of these actions $a_i$ leads to another state.
  Second, if the graph is a DAG, then the edges have a direction and there are no cycles; so, if you follow the edges, you will never get back to a node that you have already been at. However, this is not sufficient to understand that statement and why or when it is true.
  Third, that statement is true only if you use the tree search version of the depth-first search, i.e. you don't keep track of the nodes that you have already explored. In other words, you don't use graph search, which is a tree search but that keeps track of the already expanded nodes in a set called the explored set (or closed list), so that to avoid expanding them again. So, here, if you explored a node/state $s$, you added it to the explored set, so you won't expand it again.
  So, why is it possible to expand a node more than once in the tree search version of DFS? Well, you don't keep track of the nodes that you already expanded, so if you encounter it again from another path, you may expand it again. Given that it's a DAG (and assuming it's finite), then you will eventually try all possible paths, so you will find the goal.
  Now, here's an example of when you expand a node more than once in the tree search version of DFS.
  Let's say we have this search space, where you start at $A$ and the goal is $E$.
  A -> B -> C -> D
  A -> C -> D  
  A -> E
  
  If the nodes are at the same depth, let's assume that you expand them alphabetically; so, in the search space above, you expand first $B$ and then $C$, because $B$ comes before $C$ (in the English alphabet).
  Now, note that we can go directly to $C$ from $A$ or we can go to $C$ by first going to $B$. $C$ has a child. When you expand $C$, basically, you try the possible actions from $C$. In this case, there's only one action, i.e. going to $D$.
  So, without keeping track that you expanded $C$, when you got there from $B$, after you backtracked from $D$ the first time, you will try again to expand $C$. In the graph search, this would not be possible because, the first time we expand $C$, we add it to the explored set, so we don't expand it again.
  
  > **Comments:**
  > **username_0**: Thank you for your reply. I did not consider directed state space graphs at all. In addition, it can not be inferred from the context of that section of the book. So, can we conclude that the statement is correct only in directed graphs and not in general?  
  > **username_1**: @user153245 I didn't think about the case of undirected graphs. I'm also not sure how you would define cycles in an undirected graph, as every edge is a cycle (in a way), but, of course, this is probably not the definition of a cycle in an undirected graph. In the context of undirected graphs, you probably need also to keep track of the edges that you already visited.  
  > **username_2**: The explored set could be some internal flag in every node. Look at garbage collection algorithms. Read the [GC handbook](https://gchandbook.org/)  
  
  ---
  
  