Why is breadth-first search only optimal when the cost solution is a non-decreasing function?

Question

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?

Answer 1

This is well covered in the corresponding chapters of Russell & Norvig (Ch. 3 & 4). It also depends on the distinction 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.