Preprocessing Search Spaces for Branch and Bound Search

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.