---
title: "Preprocessing Search Spaces for Branch and Bound Search"
authors:
  - "Qiang Yang"
  - "Dana S. Nau"
doi: ""
url: "https://ijcai.org/proceedings/1989/55"
pdf: "https://ijcai.org/proceedings/1989/0055.pdf"
venue: "Proceedings of the Eleventh International Joint Conference on Artificial Intelligence"
year: 1989
pages: "349-352"
track: "Automated Deduction"
keywords:
---

# Preprocessing Search Spaces for Branch and Bound Search

Qiang Yang, Dana S. Nau

*Proceedings of the Eleventh International Joint Conference on Artificial Intelligence*, pages 349-352.

## Abstract

Heuristi c se ar ch pro ce dur es ar e useful in a large numb er of problems of practical importanc e. Su ch proce dur es op e rat e by s ea rching several p a ths in a search spac e at th e same tim e, expa nding some paths mor e quickly than others depe nding on whi ch paths look most promising. Often large amounts of tim e are required in keeping track of th e control knowledge. For some problems , this overhead ca n be greatly re du ce d by pr eprocessing the problem in ap propriat e ways . In parti c ular , we discuss a data s tructur e ca ll ed a thread ed decision gmph. , whi ch ca n be cre ated by pr e process ing the s ea rch space for some problems, and whi ch ca ptur es the control knowle dg e for problem solving . We show how this ca n be done , a nd we prese nt. a n analysis showing that by usin g s uch a nw thod , a great d ea l of tim e ca n be saw~d during pro blem so lving pr ocesses.