A Decomposition-Based Implementation of Search Strategies(19)

Search strategies, that is, strategies that describe how to explore search trees, have raised much interest for constraint satisfaction in recent years. In particular, limited discrepancy search and its variations have been shown to achieve significant imp

DecompositionforSearchStrategies 369

Insummary,RLDSisanimplementationofLDSthatmayproducesubstan-tialimprovementsincomputationtimesoverLDS.Itsmainlimitationisalackofrobustnessduetotherecomputationprocess,whichrequirestorestoretheexactsamecomputationstatesforthebranchingfunction.Dependingontheapplication,thismayimposesigni cantoverheadsinmemoryspaceandmaydestroythegenericityofthealgorithm.

6.ADECOMPOSITIONIMPLEMENTATION

DLDSisanimplementationofLDSmotivatedbyourdesiretoimprovetherobustnessofRLDS,whilepreservingitsef ciency.Asdiscussedintheprevioussection,themaindif cultyinRLDSistherecomputationprocessthatmustrestoretheexactsamecomputationstatestoreachthepoppedcon guration.ThefundamentalideaofDLDSistoviewthesearchprocedureasaproblemdecompositionschemeandtoreasonintermsofsubproblemsinsteadofcompu-tationpaths.Viewingsearchproceduresasdecompositionschemesis,ofcourse,notanewidea(see,e.g.,instance,FreuderandHubbe[1995]).Thenoveltyhereisthatthisviewpointcanbenaturallyexploitedtoobtainanef cientandrobustimplementationofLDSandmanysearchstrategies.Recallthatthebranchingfunctionreturnsadisjunction

(gl∧cl)∨(gr∧cr)

andthatthemaingoalofthealgorithmistosearchforsolutionstothetwosubproblemsde nedbythesedisjuncts.ThebasicideabehindDLDSisthustopushsubproblemsinthequeueinsteadofcon gurations.Inotherwords,DLDSmanipulatespathsofconstraints c1,...,cn which,whenaddedtotheoriginalconstraintstoreσ,de nesasubproblem.

TheoverallstructureofDLDSresemblesthearchitectureofRLDS.DLDSisalsoorganizedaroundaqueueandanactivecon gurationandhasasimilaroveralldesign.However,ithasthreemaindifferences:

(1)Thequeuedoesnotstorecon gurationsbutsubproblems.Thesesubprob-

lemsarerepresentedassequencesofconstraints.

(2)Whenrestoringasubproblem,DLDSdoesnotusethebranchingfunction.

Instead,itsimplyrestoresthesubproblemsbybacktrackingandTELLop-erations.

(3)Therestoredsubproblemisexploredusingtheoriginalgoal,whichiscorrect

byProposition2.6(therestartingproperty).

Figure8depictstheimplementationofDLDSSATIFY.FunctionDLDSEX-PLOREhasanadditionalargument(comparedtoRLDSEXPLORE)representingtheoriginalgoal.ObservetheconcatenationoperationinfunctionDLDSEX-PLOREthatmanipulatespathsofconstraintsinsteadofcomputationpaths.Themainsimpli cationhoweverarisesinfunctionDLDSRESTOREwhichrestoresthesubproblem

oopo=<c1,...,cn,cn+1,...,cn+j>

ACMTransactionsonComputationalLogic,Vol.5,No.2,April2004.