Artificial Intelligence: Condition for BFS being optimal

Problem Detail: 

It is said in the book Artificial Intelligence: A Modern Approach for finding a solution on a tree using BFS that:

breadth-first search is optimal if the path cost is a nondecreasing function of the depth of the node. The most common such scenario is that all actions have the same cost.

From that I understand that if the path cost is non decreasing function of depth, the BFS algorithm returns an optimal solution, i.e., the only condition is the cost function being nondecreasing. But I think the only way for BFS to be optimal is the scenario in which all the path costs are identical, therefore a node found in a certain level is necessarily the optimal solution, as, if they exist, the others are. Therefore I think for BFS to be optimal, cost function should be non decreasing AND the costs of nodes should be identical. However, the book says only one of the conditions (former one) makes BFS optimal.

Is there a situation in which the costs are not identical, the cost function is nondecreasing and the solution returned by BFS is guaranteed to be optimal?

Asked By : Varaquilex

Answered By : Carlos Linares López

¡Nice question really!

The book is right and it just suffices for the path cost to be a nondecreasing function of the depth of the node ---though an additional note should be posted, see below. This directly implies that it is not necessary for nodes in the same level to have the same cost. Truth, however, is that it is hard to find such an example because the most obvious one consists just of considering all grounded actions to have the same cost.

Thus, let me try to start with the first statement (that it just suffices for the path cost to be a nondecreasing function of the depth of the node) with a theoretical example. Let $c(n,n')$ denote the cost of traversing the edge from node $n$ to node $n'$ and let us define it as:

$$ c(n,n')=2^{g^*(s,n)} $$

where $g^*(s,n)$ is the minimum number of actions required to reach node $n$ from the start node $s$. I am certainly defining the cost of the edge as a function of the depth of the source node but it seems to be that this is absolutely okay with the statement in the book. Think of this as an attractive force exercised from the start state $s$ so that the farer you get, the more costly it is to progress. This function is clearly non-decreasing as it progresses as follows: 1, 2, 4, 8, ..., the total cost paths progressing as: 1, 3, 7, 15, ...

Now, let me show that Breadth First Search would certainly find an optimal solution. I will make it by induction:

Base case: the queue is seeded with the start state $s$. In the first iteration of BFS it is extracted from the queue and its children are generated, all of them with cost $2^0=1$. These nodes have been certainly reached through an optimal path so this satisfies the base case.

Induction step: let us assume that all nodes of depth $(d-1)$ have been already generated through optimal paths with a path cost $\sum\limits_{i=0}^{d-2}2^i=2^{d-1}-1$. In the induction step all nodes generated at depth $(d-1)$ are expanded to generate nodes at depth $d$ from the start state $s$. Obviously, all these nodes are generated through optimal paths as well since their cost corresponds to paths of minimum length from the start state (in other words, would there be a shorter path in terms of length instead of cost, it would have been discovered in a previous layer of the search tree traversed by BFS with a lower cost).

It seems to me that you would agree with this but it might not satisfy you because all nodes in the same level would have exactly the same path cost (and nodes at depth $d$ would have a total cost equal to $\sum\limits_{i=0}^{d-1}=2^d-1$), but the previous proof was necessary in order to consider the following case now:

Let us re-define the cost function as:

$$ c(n,n')=\left\{\begin{array}{l} 2^{g^*(s,n)}, \mbox{in some cases, whichever}\\ 2^{g^*(s,n)}+\delta, \mbox{otherwise}\end{array}\right. $$

where $delta$ is just a small number, say $\frac{1}{2}$, such that it is smaller than the smallest of all costs $2^0=1$. Now you have a lot of different ways to get different path costs of nodes lying at the same level. In this particular case, the path cost of a node at depth $d$ ranges in the interval $[2^{d+1}-1, 2^{d+1}+\delta\times d-1]$.

However, the optimality condition of BFS still applies because the maximum difference ($\delta\times d$) is not enough to shift any node at depth $d$ after nodes that lie at depth $(d+1)$ in the queue the reason being that the path cost of those nodes ranges in the interval $[2^{d+2}-1, 2^{d+2}+\delta(d+1)-1]$. For a value of $\delta$ small enough nodes with different costs (even if they lie at the same depth) are found through optimal paths. However, note that I am assuming here $\delta$ to be small enough. If it is not, then BFS could be easily fooled and sub-optimal paths would be easily found by BFS.

Nice question, really! Hope this contributes somehow,

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16758