Answers.Body: <p>This is well covered in the corresponding chapters of <a href="http://aima.cs.berkeley.edu/" rel="nofollow noreferrer">Russell &amp; Norvig</a> (Ch. 3 &amp; 4). It also depends on the <a href="https://rads.stackoverflow.com/amzn/click/0136042597" rel="nofollow noreferrer">distinction</a> between TREE-SEARCH and GRAPH-SEARCH.</p>
  
  <p>First, note that Breadth-first search also can't handle cost functions that vary between nodes! Breath-first search only cares about the number of moves needed to reach a state, not the total cost of getting there, so if some states are cheaper on a per-move basis, it's not optimal.</p>
  
  <p>Ok, back to the question: basically, the statement you reference applies to Breadth-first search run on a GRAPH-SEARCH problem. In this kind of problem, it is possible to loop back to an earlier state from a later state (like in chess, where you may move your king back and forth). </p>
  
  <p>If the costs for moving between two states are negative, but constant across all the possible moves, then Breadth-first search will <em>not</em> chose to loop between them forever, since it always expands the <em>nearest</em> node to the start by total number of moves, not the <em>cheapest</em> node. Since you could always add one more loop, to make a path shorter, breadth-first search will not find the shortest path (by cost), but will find the shortest path by number of moves instead.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-08T15:28:16.810Z
Answers.LastActivityDate: 2018-08-08T15:28:16.810Z
Answers.UserDisplayName: John Doucette
Body: <p>I am learning about searching strategies in AI and I was reading that breadth-first search is only optimal when the cost solution is a non-decreasing function? I am not really sure what this refers to since decreasing search cost should be our goal. Am I missing something?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-05-03T18:57:17.633Z
Comments.Text: Welcome to AI!  This question and answer might be helpful: https://cs.stackexchange.com/q/16758/57340
Comments.UserDisplayName: DukeZhou
Tags: <search><breadth-first-search>
Title: Why is breadth-first search only optimal when the cost solution is a non-decreasing function?
UserDisplayName: xava
ThreadText: # Why is breadth-first search only optimal when the cost solution is a non-decreasing function?
  
  (Asked by: username_0 on 2018-05-03)
  
  I am learning about searching strategies in AI and I was reading that breadth-first search is only optimal when the cost solution is a non-decreasing function? I am not really sure what this refers to since decreasing search cost should be our goal. Am I missing something?
  
  **Tags:** search, breadth-first-search
  > **Comments:**
  > **username_1**: Welcome to AI!  This question and answer might be helpful: https://cs.stackexchange.com/q/16758/57340  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2018-08-08. Score: 2
  
  This is well covered in the corresponding chapters of [Russell & Norvig](http://aima.cs.berkeley.edu/) (Ch. 3 & 4). It also depends on the [distinction](https://rads.stackoverflow.com/amzn/click/0136042597) between TREE-SEARCH and GRAPH-SEARCH.
  
  First, note that Breadth-first search also can't handle cost functions that vary between nodes! Breath-first search only cares about the number of moves needed to reach a state, not the total cost of getting there, so if some states are cheaper on a per-move basis, it's not optimal.
  
  Ok, back to the question: basically, the statement you reference applies to Breadth-first search run on a GRAPH-SEARCH problem. In this kind of problem, it is possible to loop back to an earlier state from a later state (like in chess, where you may move your king back and forth).
  
  If the costs for moving between two states are negative, but constant across all the possible moves, then Breadth-first search will *not* chose to loop between them forever, since it always expands the *nearest* node to the start by total number of moves, not the *cheapest* node. Since you could always add one more loop, to make a path shorter, breadth-first search will not find the shortest path (by cost), but will find the shortest path by number of moves instead.
  
  
  ---
  
  