Abstract
Branch and Bound (B&B) is a problem-solving technique which is widely used for various problems encountered in operations research and combinatorial mathematics. Various heuristic search procedures used in artificial intelligence (AI) are considered to be related to B&B procedures. However, in the absence of any generally accepted terminology for B&B procedures, there have been widely differing opinions regarding the relationships between these procedures and B&B. This paper presents a formulation of B&B general enough to include previous formulations as special cases, and shows how two well-known AI search procedures (A* and AO*) are special cases of this general formulation.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 29-58 |
| Number of pages | 30 |
| Journal | Artificial Intelligence |
| Volume | 23 |
| Issue number | 1 |
| DOIs | |
| State | Published - May 1984 |
Bibliographical note
Funding Information:Given a (possibly infinite) discrete set X and a real-valued objective function F whose domain is X, find an optimal element x* E X such that F(x*) = min{F(x) I x ~ X}) Unless there is enough problem-specific knowledge available to obtain the optimum element of the set in some straightforward manner, the only course available may be to enumerate some or all of the elements of X until an optimal element is found. However, the sets X and {F(x) \[x E X} are usually tThis work was supported by NSF Grant ENG-7822159 to the Laboratory for Pattern Analysis at the University of Maryland. 1In some applications, the maximal element (i.e., x* such that F(x*)= max{F(x)\[ x U X}) is desired rather than the minimal element.