Answers.Body: <p>The only general situation that comes to my mind where BFS could be preferred over A* is when your graph is unweighted and the heuristic function is <span class="math-container">$h(n) = 0, \forall n \in V$</span>. However, in that case, A* (<a href="https://ai.stackexchange.com/a/9183/2444">which is equivalent to UCS</a>) behaves like BFS (except for the goal test: <a href="https://cs.calvin.edu/courses/cs/344/kvlinden/resources/AIMA-3rd-edition.pdf#page=104" rel="nofollow noreferrer">see section 3.4.2 of this book</a>), i.e. it will first expand nodes at level <span class="math-container">$l$</span>, then at level <span class="math-container">$l+1$</span>, etc., this is because nodes at level <span class="math-container">$l+1$</span> are farther away from the initial node than nodes at level <span class="math-container">$l$</span>, i.e. <span class="math-container">$f(n') = g(n') &gt; f(n) = g(n)$</span>, for all <span class="math-container">$n' \in V_{l+1}$</span> and <span class="math-container">$n \in V_{l}$</span>, where <span class="math-container">$g(n)$</span> is the cost of the shortest path from the initial node to <span class="math-container">$n$</span> and <span class="math-container">$V_{l}$</span> is the subset of nodes of the search space that belong to level/layer <span class="math-container">$l$</span> of the search tree.</p>
  <p>So, if you think that your goal is close to the initial node in terms of levels/layers and each node has a small branching factor (i.e. not many children), then BFS may be a good idea (but you could also use A*).</p>
  <p>BFS can also be used as a sub-routine in other algorithms, such as <a href="https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm" rel="nofollow noreferrer">the Ford–Fulkerson algorithm</a>. So, in these cases, BFS may also be preferable.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-20T11:26:22.430Z
Answers.LastActivityDate: 2021-02-20T12:31:06.957Z
Answers.LastEditDate: 2021-02-20T12:31:06.957Z
Answers.UserDisplayName: nbro
Answers.Body: <p>There is an inherent <strong>assumption</strong> in heuristic search that the heuristic function points you in the right direction.</p>
  <p>A* largely depends on how good the heuristic function is. Two nice properties for the heuristic function are for it to be admissible and <strong>consistent</strong>. If the latter stands, I can't think of any case where BFS would outperform A*. However, this property doesn't stand in every case.</p>
  <p>If you select a <strong>misleading</strong> heuristic function (i.e. a function that points you in the <strong>wrong direction</strong>) then BFS should outperform A*.</p>
  <hr />
  <p>I drew a dumb example to illustrate my point. You want to reach from the Initial State (IS) to the Goal State (GS). The shade of green indicates the value of the heuristic (the greener the better).</p>
  <p><img src="https://i.sstatic.net/rhjOM.png" alt="" /></p>
  <p>In the third case, where you have a misleading heuristic, A* would tend to explore areas near the top right first, then it would go down towards the GS. This case is actually worse than having no heuristic and using a BFS.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T18:47:58.450Z
Answers.Text: I just want to point out that having "no heuristic" would be like having a heuristic $h(n) = 0$, for all $n$, which is an admissible heuristic, so, in that case, A* should also be optimal and, as I say in my answer, it should behave like BFS, although I didn't try it out (with an example to confirm it) and some details may be different.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T13:04:34.973Z
Answers.LastActivityDate: 2021-02-25T13:04:34.973Z
Answers.UserDisplayName: Djib2011
Body: <p>Is there any situation in which breadth-first search is preferable over A*?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-20T10:21:11.450Z
Comments.Text: Could you please add more context? Why are you interested in this question?
Comments.UserDisplayName: nbro
Tags: <comparison><search><a-star><breadth-first-search>
Title: Is there any situation in which breadth-first search is preferable over A*?
UserDisplayName: JackoJackie
ThreadText: # Is there any situation in which breadth-first search is preferable over A*?
  
  (Asked by: username_0 on 2021-02-20)
  
  Is there any situation in which breadth-first search is preferable over A\*?
  
  **Tags:** comparison, search, a-star, breadth-first-search
  > **Comments:**
  > **username_1**: Could you please add more context? Why are you interested in this question?  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2021-02-20. Score: 2
  
  The only general situation that comes to my mind where BFS could be preferred over A\* is when your graph is unweighted and the heuristic function is $h(n) = 0, \forall n \in V$. However, in that case, A\* ([which is equivalent to UCS](https://ai.stackexchange.com/a/9183/2444)) behaves like BFS (except for the goal test: [see section 3.4.2 of this book](https://cs.calvin.edu/courses/cs/344/kvlinden/resources/AIMA-3rd-edition.pdf#page=104)), i.e. it will first expand nodes at level $l$, then at level $l+1$, etc., this is because nodes at level $l+1$ are farther away from the initial node than nodes at level $l$, i.e. $f(n') = g(n') > f(n) = g(n)$, for all $n' \in V\_{l+1}$ and $n \in V\_{l}$, where $g(n)$ is the cost of the shortest path from the initial node to $n$ and $V\_{l}$ is the subset of nodes of the search space that belong to level/layer $l$ of the search tree.
  
  So, if you think that your goal is close to the initial node in terms of levels/layers and each node has a small branching factor (i.e. not many children), then BFS may be a good idea (but you could also use A\*).
  
  BFS can also be used as a sub-routine in other algorithms, such as [the Ford–Fulkerson algorithm](https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm). So, in these cases, BFS may also be preferable.
  
  
  ---
  
  ### Answer by username_2 on 2021-02-25. Score: 1
  
  There is an inherent **assumption** in heuristic search that the heuristic function points you in the right direction.
  
  A\* largely depends on how good the heuristic function is. Two nice properties for the heuristic function are for it to be admissible and **consistent**. If the latter stands, I can't think of any case where BFS would outperform A\*. However, this property doesn't stand in every case.
  
  If you select a **misleading** heuristic function (i.e. a function that points you in the **wrong direction**) then BFS should outperform A\*.
  
  ---
  
  I drew a dumb example to illustrate my point. You want to reach from the Initial State (IS) to the Goal State (GS). The shade of green indicates the value of the heuristic (the greener the better).
  
  ![](https://i.sstatic.net/rhjOM.png)
  
  In the third case, where you have a misleading heuristic, A\* would tend to explore areas near the top right first, then it would go down towards the GS. This case is actually worse than having no heuristic and using a BFS.
  
  > **Comments:**
  > **username_1**: I just want to point out that having "no heuristic" would be like having a heuristic $h(n) = 0$, for all $n$, which is an admissible heuristic, so, in that case, A* should also be optimal and, as I say in my answer, it should behave like BFS, although I didn't try it out (with an example to confirm it) and some details may be different.  
  
  ---
  
  