An Experimental Analysis of the B* Tree Search Algorithm

Abstract

A set of selection rules is presented for guiding the B* search procedure. The selection rules are based on a simple probability model. Using those selection procedures, the B* algorithm will expand approximately one-third as many nodes as a best first search and approximately two-thirds as many nodes as the previous best version of the B* algorithm. The B* algorithm, using the selection procedures, will expand 30% more nodes than optimum, for small trees, and up to 170% for larger trees. The issues of when the B* paradigm is useful is examined with the effect of invalid bounds on the algorithm.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 08, 1980
Accession Number
ADA224252

Entities

People

  • Andrew J. Palay

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Human Systems

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Artificial Intelligence
  • Computations
  • Computer Science
  • Computers
  • Equations
  • Measurement
  • New York
  • Probability
  • Simulations
  • Test And Evaluation
  • Trees (Data Structures)
  • Universities
  • Value

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Explosive Engineering.
  • Systems Analysis and Design