### 3.7.4 Branch and Bound

Depth-first **branch-and-bound** search is a way to combine the
space saving of depth-first search with heuristic information. It is
particularly applicable when many paths to a goal exist and we
want an optimal path. As in *A ^{*}* search, we assume that

*h(n)*is less than or equal to the cost of a lowest-cost path from

*n*to a goal node.

The idea of a branch-and-bound search is to maintain the
lowest-cost path to a goal found so far, and its cost. Suppose this cost is *bound*. If the search
encounters a path *p* such that *cost(p)+h(p) ≥ bound*, path *p* can
be pruned. If a non-pruned path to a goal is found, it must be better
than the previous best path. This new solution is remembered and *bound* is set to the
cost of this new solution. It then keeps searching for a better solution.

Branch-and-bound search generates a sequence of ever-improving solutions. Once it has found a solution, it can keep improving it. Branch-and-bound search is typically used with depth-first search, where the space saving of the depth-first search can be achieved. It can be implemented similarly to depth-bounded search, but where the bound is in terms of path cost and reduces as shorter paths are found. The algorithm remembers the lowest-cost path found and returns this path when the search finishes.

**Procedure**DFBranchAndBound(

*G,s,goal,h,bound*)

_{0}2:

**Inputs**

3:

*G*: graph with nodes

*N*and arcs

*A*

4:

*s*: start node

5:

*goal*: Boolean function on nodes

6:

*h*: heuristic function on nodes

7:

*bound*: initial depth bound (can be

_{0}*∞*if not specified)

8:

**Output**

9: a least-cost path from

*s*to a goal node if there is a solution with cost less than

*bound*

_{0}10: or

*⊥*if there is no solution with cost less than

*bound*

_{0}11:

**Local**

12:

*best_path*: path or

*⊥*

13:

*bound*: non-negative real

14:

**Procedure**cbsearch(

*⟨n*)

_{0},...,n_{k}⟩15:

**if**(

*cost(⟨n*)

_{0},...,n_{k}⟩)+h(n_{k}) < bound**then**

16:

**if**(

*goal(n*)

_{k})**then**

17:

*best_path ←⟨n*

_{0},...,n_{k}⟩18:

*bound ←cost(⟨n*

_{0},...,n_{k}⟩)19:

**else**

20:

**for each**arc

*⟨n*

_{k},n⟩∈A**do**

21:

*cbsearch(⟨n*

_{0},...,n_{k},n⟩)22:

*best_path ←⊥*

23:

*bound ←bound*

_{0}24:

*cbsearch(⟨s⟩)*

25:

**return**

*best_path*

The algorithm is shown in Figure 3.11. The
internal procedure *cbsearch*, for cost-bounded search, uses the
global variables to provide information to the main procedure.

Initially, *bound* can be set to infinity, but it is often useful
to set it to an overestimate, *bound _{0}*, of the path
cost of an optimal solution. This algorithm will return an optimal
solution - a least-cost path from the start node to a goal node - if
there is a solution with cost less than the initial bound

*bound*.

_{0}If the initial bound is slightly above the cost of a lowest-cost
path, this algorithm can find an optimal path expanding no more arcs
than *A ^{*}* search. This happens when the initial bound is such that the algorithm prunes any path
that has a higher cost than a lowest-cost path; once it has found a path to
the goal, it only explores paths whose the

*f*-value is lower than the path found. These are exactly the paths that

*A*explores when it finds one solution.

^{*}If it returns *⊥* when *bound _{0}=∞*, there are no solutions. If
it returns

*⊥*when

*bound*is some finite value, it means no solution exists with cost less than

_{0}*bound*. This algorithm can be combined with iterative deepening to increase the bound until either a solution is found or it can be shown there is no solution. See Exercise 3.13.

_{0}**Example 3.17:**Consider the tree-shaped graph in Figure 3.12. The goal nodes are shaded. Suppose that each arc has length 1, and there is no heuristic information (i.e.,

*h(n)=0*for each node

*n*). In the algorithm, suppose

*depth*and the depth-first search always chooses the leftmost child first. This figure shows the order in which the nodes are checked to determine if they are a goal node. The nodes that are not numbered are not checked for being a goal node.

_{0}=∞The subtree under the node numbered "5" does not have a goal and is
explored fully (or up to depth *depth _{0}* if it had a finite value).
The ninth node checked is a goal node. It has a path cost of 5, and so
the bound is set to 5. From
then on, only paths with a length of less than 5 are checked for being
a solution. The fifteenth node checked is also a goal. It has a path
cost of 3, and so the bound is reduced to 3. There are no other goal nodes
found, and so the path to the node labeled 15 is returned. It is an
optimal path. There is another optimal path that is pruned; the
algorithm never checks the children of the node labeled with 18.

If there was heuristic information, it could be used to prune parts of
the search space, as in *A ^{*}* search.