Abstract. Recently, it has been found that the cost distributions of randomized backtrack search in combinatorial domains are often heavytailed. Such heavy-tailed distributions explain the high variability observed when using backtrack-style procedures. A
FormalModelsofHeavy-TailedBehaviorin
CombinatorialSearch
HubieChen,CarlaGomes,andBartSelman
DepartmentofComputerScience,CornellUniversity,Ithaca,NY14853,USA
{hubes,gomes,selman}@cs.cornell.edu
Abstract.Recently,ithasbeenfoundthatthecostdistributionsof
randomizedbacktracksearchincombinatorialdomainsareoftenheavy-
tailed.Suchheavy-taileddistributionsexplainthehighvariabilityob-
servedwhenusingbacktrack-styleprocedures.Agoodunderstanding
ofthisphenomenoncanleadtobettersearchtechniques.Forexample,
restartstrategiesprovideagoodmechanismforeliminatingtheheavy-
tailedbehaviorandboostingtheoverallsearchperformance.Several
state-of-the-artSATsolversnowincorporatesuchrestartmechanisms.
Thestudyofheavy-tailedphenomenaincombinatorialsearchhassofar
beenbeenlargelybasedonempiricaldata.Weintroduceseveralabstract
treesearchmodels,andshowformallyhowheavy-tailedcostdistribution
canariseinbacktracksearch.Wealsodiscusshowtheseinsightsmayfa-
cilitatethedevelopmentofbettercombinatorialsearchmethods.
1Introduction
Recentlytherehavebeenaseriesofnewinsightsintothehighvariabilityob-servedintheruntimeofbacktracksearchprocedures.Empiricalworkhasshownthattheruntimedistributionsofbacktrackstylealgorithmsoftenexhibitso-calledheavy-tailedbehavior[5].Heavy-tailedprobabilitydistributionsarehighlynon-standarddistributionsthatcaptureunusuallyerraticbehaviorandlargevariationsinrandomphenomena.Theunderstandingofsuchphenomenainbacktracksearchhasprovidednewinsightsintothedesignofsearchalgorithmsandledtonewsearchstrategies,inparticular,restartstrategies.Suchstrategiesavoidthelongtailsintheruntimedistributionsandtakeadvantageoftheprob-abilitymassatthebeginningofthedistributions.Randomizationandrestartstrategiesarenowanintegralpartofseveralstate-of-the-artSATsolvers,forexample,Cha [12],GRASP[11],Relsat[1],andSatz-rand[9,4].
Researchonheavy-taileddistributionsandrestartstrategiesincombinatorialsearchhasbeenlargelybasedonempiricalstudiesofruntimedistributions.However,sofar,adetailedrigorousunderstandingofsuchphenomenahasbeenlacking.Inthispaper,weprovideaformalcharacterizationofseveraltreesearchmodelsandshowunderwhatconditionsheavy-taileddistributionscanarise.Intuitively,heavy-tailedbehaviorinbacktrackstylesearcharisesfromthefactthatwrongbranchingdecisionsmayleadtheproceduretoexploreanexpo-nentiallylargesubtreeofthesearchspacethatcontainsnosolutions.Depending
1
A Random Jump Strategy for Combinatorial Search Hantao Zhang? Computer ...the phenomenon of “heavy-tailed cost distributions” [8, 9, 10, 11]. ...
Selman: 2001, ‘Formal Models of Heavy-tailed Behavior in Combinatorial Search’. In: Proceedings CP’01. Paphos, Cyprus, pp. 408–421. Dechter, R.:...
Selman: 2001, ‘Formal Models of Heavy-tailed Behavior in Combinatorial Search’. In: Proceedings CP’01. Paphos, Cyprus, pp. 408–421. Dechter, R.:...
instances and about solver behavior into ...Researchers have noted that combinatorial search ...a heavy-tailed (powerlaw) distribution, having ...
A Random Jump Strategy for Combinatorial Search Hantao Zhang? Computer ...the phenomenon of “heavy-tailed cost distributions” [8, 9, 10, 11]. ...
热门文档