Answers.Body: <p>As you found <span class="math-container">$N$</span> is the number of nodes that are expanded. The cost of expansion of each node is equal to the number of children of that node. Hence, we use <span class="math-container">$b^*$</span> for each node. In other words, the total number of nodes that are involved in the expansion process is <span class="math-container">$N \times b^*$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-24T17:03:19.697Z
Answers.Text: @ OmG - Why not ${N}$ since you agreed that the cost solely depends on ${N}$?
Answers.UserDisplayName: KGhatak
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-24T17:27:17.493Z
Answers.Text: @KGhatak because the total number of expanded node is $N \times b^*$.
Answers.UserDisplayName: OmG
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-25T04:36:33.777Z
Answers.Text: @ OmG - Not sure if this is the right understanding. Can you provide some reference for it! Just think, we calculated expected ONLY when we don't know for sure. If we know actual N, there is no need to estimate/guess (aka Expected value of) N. What say!
Answers.UserDisplayName: KGhatak
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-25T10:22:08.267Z
Answers.Text: @KGhatak Unfortunately I don't know which part is confusing for you. In the search, we expand $N$ nodes, and each node has $b^*$ children at most. Hence,  the complexity is related to $N$ and $b^*$. Now, suppose we do not apply $b^*$ in the complexity, and another algorithm try to search and expand $N$ nodes to find the solution, but the branching factor of the current algorithm would be $2^{b^*}$! Which of them will be a better algorithm in terms of complexity?
Answers.UserDisplayName: OmG
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-25T18:26:08.593Z
Answers.Text: @ OmG - Let me put it in a different way. Two algorithms, say 1 and 2, try to solve a problem. Their respective values are ${N_1}, {b_1^*}, {N_2}$, and ${b_2^*}$ such that ${N_1b_1^*}={N_2b_2^*}$. Which algorithm is efficient given ${N_1>N_2}$. Would you pls explain!
Answers.UserDisplayName: KGhatak
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-24T15:04:53.853Z
Answers.LastActivityDate: 2019-11-24T17:28:18.690Z
Answers.LastEditDate: 2019-11-24T17:28:18.690Z
Answers.UserDisplayName: OmG
Answers.Body: <p>I also walked into that trap the first few times. The difference is the following:</p>
  <ul>
  <li><span class="math-container">$N$</span> is the number of <strong>expanded</strong> nodes</li>
  <li><span class="math-container">$b^*$</span> is the effective branching factor
  <ul>
  <li><span class="math-container">$b^*$</span> depends on the depth <span class="math-container">$d$</span> of the goal and the number of <strong>generated</strong> nodes, lets call that <span class="math-container">$M$</span></li>
  <li><span class="math-container">$b^*$</span> is the solution to <span class="math-container">$M+1=1+b^*+(b^*)^2+(b^*)^3+...+(b^*)^d$</span></li>
  </ul>
  </li>
  </ul>
  <p>So, you could argue that instead of comparing <span class="math-container">$b_1^*$</span> and <span class="math-container">$b_2^*$</span> of two algorithms, you can also directly compare <span class="math-container">$M_1$</span> and <span class="math-container">$M_2$</span>, because <span class="math-container">$b_1^*&gt;b_2^*\Leftrightarrow M_1&gt;M_2$</span>.</p>
  <p>But you can imagine an algorithm <span class="math-container">$A_2$</span> that <strong>expands fewer nodes</strong> than <span class="math-container">$A_1$</span> (so <span class="math-container">$N_1&gt;N_2$</span>), but also different nodes so that it <strong>generates more nodes</strong> (so <span class="math-container">$M_1&lt;M_2$</span>).
  Since the cost is defined by the number of generated nodes, comparing <span class="math-container">$N$</span> might give the wrong result.</p>
  <p>The effective branching factor is more general than the number of generated nodes, because you can average <span class="math-container">$b^*$</span> for one algorithm over many search problems, but averaging over the number of nodes (which might differ greatly) is not possible or rather nonsensical.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-25T13:18:39.080Z
Answers.Text: Averaging over different sizes of the “same” search problem (e.g., N-queens with different Ns) seems to be the motivation. Otherwise, the number of generated nodes are a superior measure.
Answers.UserDisplayName: HappyFace
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-25T13:20:18.287Z
Answers.Text: Why is it M+1 in the formula? (Instead of the plain M)
Answers.UserDisplayName: HappyFace
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-25T20:49:32.957Z
Answers.Text: @HappyFace The "+1" is the root node which is not generated by the search algorithm. It already exists at the beginning. Technically, the "1+" on the right side is also the root node and could be omitted, but with "1+" the right side becomes a [geometric series](https://en.wikipedia.org/wiki/Geometric_series#Closed-form_formula) and can be simplified
Answers.UserDisplayName: Sentry
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-19T17:17:29.560Z
Answers.LastActivityDate: 2021-12-19T17:17:29.560Z
Answers.UserDisplayName: Sentry
Body: <p>For search algorithms with heuristic functions, the performance of heuristic functions are measured by the <em>effective branching factor</em> <span class="math-container">${b^*}$</span>, which involves the total number of nodes expanded <span class="math-container">${N}$</span> and the depth of the solution <span class="math-container">${d}$</span>.</p>
  <p>I'm not able to find out how different values of <span class="math-container">${d}$</span> affect the performance keeping the same <span class="math-container">${N}$</span>. Put another way, why not use just the <span class="math-container">${N}$</span> as the performance measure instead of <span class="math-container">${b^*}$</span>?</p>
  
Tags: <search><performance><branching-factors><heuristic-functions><informed-search>
Title: Why is the effective branching factor used for measuring performance of a heuristic function?
UserDisplayName: KGhatak
ThreadText: # Why is the effective branching factor used for measuring performance of a heuristic function?
  
  (Asked by: username_0 on 2019-11-24)
  
  For search algorithms with heuristic functions, the performance of heuristic functions are measured by the *effective branching factor* ${b^\*}$, which involves the total number of nodes expanded ${N}$ and the depth of the solution ${d}$.
  
  I'm not able to find out how different values of ${d}$ affect the performance keeping the same ${N}$. Put another way, why not use just the ${N}$ as the performance measure instead of ${b^\*}$?
  
  **Tags:** search, performance, branching-factors, heuristic-functions, informed-search
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2021-12-19. Score: 2 | Accepted answer
  
  I also walked into that trap the first few times. The difference is the following:
  
  * $N$ is the number of **expanded** nodes
  * $b^\*$ is the effective branching factor
    + $b^\*$ depends on the depth $d$ of the goal and the number of **generated** nodes, lets call that $M$
    + $b^\*$ is the solution to $M+1=1+b^\*+(b^\*)^2+(b^\*)^3+...+(b^\*)^d$
  
  So, you could argue that instead of comparing $b\_1^\*$ and $b\_2^\*$ of two algorithms, you can also directly compare $M\_1$ and $M\_2$, because $b\_1^\*>b\_2^\*\Leftrightarrow M\_1>M\_2$.
  
  But you can imagine an algorithm $A\_2$ that **expands fewer nodes** than $A\_1$ (so $N\_1>N\_2$), but also different nodes so that it **generates more nodes** (so $M\_1<M\_2$).
  Since the cost is defined by the number of generated nodes, comparing $N$ might give the wrong result.
  
  The effective branching factor is more general than the number of generated nodes, because you can average $b^\*$ for one algorithm over many search problems, but averaging over the number of nodes (which might differ greatly) is not possible or rather nonsensical.
  
  > **Comments:**
  > **username_3**: Averaging over different sizes of the “same” search problem (e.g., N-queens with different Ns) seems to be the motivation. Otherwise, the number of generated nodes are a superior measure.  
  > **username_3**: Why is it M+1 in the formula? (Instead of the plain M)  
  > **username_2**: @username_3 The "+1" is the root node which is not generated by the search algorithm. It already exists at the beginning. Technically, the "1+" on the right side is also the root node and could be omitted, but with "1+" the right side becomes a [geometric series](https://en.wikipedia.org/wiki/Geometric_series#Closed-form_formula) and can be simplified  
  
  ---
  
  ### Answer by username_1 on 2019-11-24. Score: 1
  
  As you found $N$ is the number of nodes that are expanded. The cost of expansion of each node is equal to the number of children of that node. Hence, we use $b^\*$ for each node. In other words, the total number of nodes that are involved in the expansion process is $N \times b^\*$.
  
  > **Comments:**
  > **username_0**: @ OmG - Why not ${N}$ since you agreed that the cost solely depends on ${N}$?  
  > **username_1**: @username_0 because the total number of expanded node is $N \times b^*$.  
  > **username_0**: @ OmG - Not sure if this is the right understanding. Can you provide some reference for it! Just think, we calculated expected ONLY when we don't know for sure. If we know actual N, there is no need to estimate/guess (aka Expected value of) N. What say!  
  > **username_1**: @username_0 Unfortunately I don't know which part is confusing for you. In the search, we expand $N$ nodes, and each node has $b^*$ children at most. Hence,  the complexity is related to $N$ and $b^*$. Now, suppose we do not apply $b^*$ in the complexity, and another algorithm try to search and expand $N$ nodes to find the solution, but the branching factor of the current algorithm would be $2^{b^*}$! Which of them will be a better algorithm in terms of complexity?  
  > **username_0**: @ OmG - Let me put it in a different way. Two algorithms, say 1 and 2, try to solve a problem. Their respective values are ${N_1}, {b_1^*}, {N_2}$, and ${b_2^*}$ such that ${N_1b_1^*}={N_2b_2^*}$. Which algorithm is efficient given ${N_1>N_2}$. Would you pls explain!  
  
  ---
  
  