文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Formal models of heavy-tailed behavior in combinatorial search
侵权投诉

Formal models of heavy-tailed behavior in combinatorial search

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

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email