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

PATHRETRIEVER(Goalg,Storeσ,Pathp):Goal×Store

{

ifp= thenreturn g,σ ;

else{

<(gl,cl),(gr,cr)>:=BRANCH(g,σ);

ifp= left,... then{

TELL(σ,cl);

returnPATHRETRIEVER(gl,σ);

else{

TELL(σ,cr);

returnPATHRETRIEVER(gr,σ);

}

}

}

Fig.3.Afunctiontofollowacomputationpath. 361

VanHentenryckandLeProvost[1991]).Itisthusnotsurprisingthattheyarealsovaluableintheimplementationofsearchstrategies[Perron1999].

Inthisarticle,abranchingdecisionisrepresentedbyeitherleftorrighttodenotewhethertheleftorrightdisjunctwasselected.

De nition2.7(ComputationPath).Acomputationpathisasequence d1,...,dn wheredi∈{left,right}(1≤i≤n).

Itiseasytoinstrumenttheoperationalsemanticsgivenearliertocollectcomputationpathsthatuniquelyidentifyeachcon guration.Itsuf cestoconsidercon gurationsoftheform g,σ,p or σ,p ,wherepisacomputationpathandtoupdatethetransitionrulestoobtain,say,

¬SUCCESS(σ)∧¬FAILURE(σ)BRANCH(g,σ)= (gl,cl),(gr,cr) ;

llwhere d1,...,dn ::ddenotesthecomputationpath d1,...,dn,d .Theothertransitionrulescanbeinstrumentedsimilarly.

Givenitscomputationpath,itisalsoeasytoretrieveacon gurationstartingfromtheinitialcon guration.Figure3showsasimplefunctiontoperformthistask.Severalalgorithmspresentedinthispaperusesimilarideas.

3.LIMITEDDISCREPANCYSEARCH

LimitedDiscrepancySearch(LDS)[HarveyandGinsberg1995]isasearchstrategyrelyingonagoodheuristicfortheproblemathand.Itsbasicideaistoexplorethesearchtreeinwavesandeachsuccessivewaveallowstheheuristictomakemoremistakes.Wave0simplyfollowstheheuristic.Wave1exploresthesolutionswhichcanbereachedbyassumingthattheheuristicmadeonemistake.Moregenerally,waveiexploresthesolutionsthatcanbereachedbyassumingthattheheuristicmakesimistakes.

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