Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.

### 3.5.3 Lowest-Cost-First Search

When a non-unit cost is associated with arcs, we often want to find the solution that minimizes the total cost of the path. For example, for a delivery robot, costs may be distances and we may want a solution that gives the minimum total distance. Costs for a delivery robot may be resources required by the robot to carry out the action represented by the arc. The cost for a tutoring system may be the time and effort required by the students. In each of these cases, the searcher should try to minimize the total cost of the path found to reach the goal.

The search algorithms considered thus far are not guaranteed to find the minimum-cost paths; they have not used the arc cost information at all. Breadth-first search finds a solution with the fewest arcs first, but the distribution of arc costs may be such that a path of fewest arcs is not one of minimal cost.

The simplest search method that is guaranteed to find a minimum cost path
is similar to breadth-first search; however, instead of expanding a path
with the fewest number of arcs, it selects a path with the minimum
cost. This is implemented by treating the frontier as a priority
queue ordered by the *cost* function.

**Example 3.11:**Consider a lowest-cost-first search from

*o103*in the graph given in Figure 3.2. The only goal node is

*r123*. In this example, paths are denoted by the end node of the path. A subscript shows the cost of the path.

Initially, the frontier is *[o103 _{0}]*. At the next stage it is

*[b3*. The path to

_{4},ts_{8},o109_{12}]*b3*is selected, with the resulting frontier

[b1_{8},ts_{8},b4_{11},o109_{12}].

The path to *b1* is then selected, resulting
in frontier

[ts_{8},c2_{11},b4_{11},o109_{12},b2_{14}].

Then the path to
*ts* is selected, and the resulting frontier is

[c2_{11},b4_{11},o109_{12},mail_{14},b2_{14}].

Then *c2* is
selected, and so forth. Note how the lowest-cost-first search grows many paths incrementally,
always expanding the path with lowest cost.

If the costs of the arcs are bounded below by a positive constant and the branching factor is finite, the lowest-cost-first search is guaranteed to find an optimal solution - a solution with lowest path cost - if a solution exists. Moreover, the first path to a goal that is found is a path with least cost. Such a solution is optimal, because the algorithm generates paths from the start in order of path cost. If a better path existed than the first solution found, it would have been selected from the frontier earlier.

The bounded arc cost is used to guarantee the lowest-cost search will find
an optimal solution. Without such a bound there can be infinite paths
with a finite cost. For example, there could be nodes
*n _{0},n_{1},n_{2},...* with an arc

*⟨n*for each

_{i-1},n_{i}⟩*i>0*with cost

*1/2*. Infinitely many paths of the form

^{i}*⟨n*exist, all of which have a cost of less than 1. If there is an arc from

_{0},n_{1},n_{2},...,n_{k}⟩*n*to a goal node with a cost greater than or equal to 1, it will never be selected. This is the basis of Zeno's paradoxes that Aristotle wrote about more than 2,300 years ago.

_{0}Like breadth-first search, lowest-cost-first search is typically exponential in
both space and time. It generates *all* paths from the start that have
a cost less than the cost of the solution.