General Branch and Bound, and its relation to A* and AO*

Dana S. Nau, Vipin Kumar, Laveen Kanal

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

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 languageEnglish (US)
Pages (from-to)29-58
Number of pages30
JournalArtificial Intelligence
Volume23
Issue number1
DOIs
StatePublished - May 1984

Fingerprint Dive into the research topics of 'General Branch and Bound, and its relation to A* and AO*'. Together they form a unique fingerprint.

Cite this