Intelligent Systems by Universal Teacher Publications

Search Techniques

Branch-and-Bound Search

Branch-and-Bound Search (Dec. 99)

The branch-and-bound search strategy applies to problems having a graph search space where more than one alternative path may exist between two nodes. This strategy saves all path lengths (or costs) from a node to all generated nodes and chooses the shortest path for further expansion. It then compares the new path lengths with all old ones and again chooses the shortest path for expansion. In this way, any path to a goal node is certain to be a minimal length path. This process is illustrated in the following figure:

An algorithm for the branch-and-bound strategy that uses a queue data structure to hold partial paths developed during the search is as follows.

1. Place the start node of zero path length on the queue.
2. Until the queue is empty or a goal node has been found: (a) determine if the first path in the queue contains a goal node, (b) if the first path contains a goal node exit with success, (c) if the first path does not contain a goal node, remove the path from the queue and form new paths by extending the removed path by one step, (d) compute the cost of the new paths and add them to queue, (e) sort the paths on the queue with lowest-cost paths in front.
3. Otherwise, exit with failure.

Always extending the lowest-cost path in branch-and-bound search insures that a lowest-cost path will be found if one exists. But, this is at the expense of computing and remembering all competing paths.

**A* Search Algorithm**

A * Search Algorithm (Dec. 99, Jan. 01, Dec. 01)

The A* algorithm is a specialization of best-first search. It provides general guidelines with which to estimate goal distances for general search graphs.

At each node along a path to the goal, the A * algorithm generates all successor nodes and computes an estimate of the distance (cost) from the start node to a goal node through each of the successors. It then chooses the successor with the short estimated distance for expansion. The successors for this node are then generated, their distances estimated, and the process continues until a goal is found or search ends in failure.

The form of the heuristic estimation function for A* is

f*(n) = g*(n) + h*(n)

where the two components g*(n) and h*(n) are estimates of the cost (or distance) from the start node to node n and the cost from node n to a goal node, respectively. The asterisks are used to designate estimates of the corresponding true values f(n) = g(n) + h(n). For state space tree problems g*(n) = g(n) since there is only one path and the distance g*(n) will be known to be the true minimum from the start to the current node n. This is not true in general for graphs, since alternate paths from the start node to n may exist.

It is convenient to maintain two lists of node types designated as open and closed. Nodes on the open list are nodes that have been generated but not yet expanded while nodes on the closed list are nodes that have been expanded and whose children are, therefore, available to the search program. The steps of A* algorithm are listed below:

1. Place the starting node s on open.
2. If open is empty, stop and return failure.
3. Remove from open the node n that has the smallest value of f*(n). If the node is a goal node, return success and stop. Otherwise,
4. Expand n, generating all of its successors n' and place n on closed. For every successor n', if n' is not already on open or closed attach a back-pointer to n, compute f*(n') and place it on open.
5. Each n' that is already on open or closed should be attached to back-pointers which reflect the lowest g*(n') path. If n' was on closed and its pointer was changed, remove it and place it on open.
6. Return to step 2.

AI Contents