资源描述：
《dynamic backtracking》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、JournalofArti cialIntelligenceResearch1(1993)25-46Submitted7/93;published8/93DynamicBacktrackingMatthewL.Ginsbergginsberg@cs.uoregon.eduCIRL,UniversityofOregon,Eugene,OR97403-1269USAAbstractBecauseoftheiroccasionalneedtoreturntoshallowpointsinasearchtree,existi
2、ngbacktrackingmethodscansometimeserasemeaningfulprogresstowardsolvingasearchproblem.Inthispaper,wepresentamethodbywhichbacktrackpointscanbemoveddeeperinthesearchspace,therebyavoidingthisdiculty.Thetechniquedevelopedisavariantofdependency-directedbacktrackingth
3、atusesonlypolynomialspacewhilestillprovidingusefulcontrolinformationandretainingthecompletenessguaranteesprovidedbyearlierapproaches.1.IntroductionImaginethatyouaretryingtosolvesomeconstraint-satisfactionproblem,orcsp.Intheinterestsofde niteness,Iwillsupposetha
4、tthecspinquestioninvolvescoloringamapoftheUnitedStatessubjecttotherestrictionthatadjacentstatesbecoloreddi erently.ImaginewebeginbycoloringthestatesalongtheMississippi,therebysplittingtheremainingproblemintwo.Wenowbegintocolorthestatesinthewesternhalfofthecount
5、ry,coloringperhapshalfadozenofthembeforedecidingthatwearelikelytobeabletocolortherest.SupposealsothatthelaststatecoloredwasArizona.Atthispoint,wechangeourfocustotheeasternhalfofthecountry.Afterall,ifwecan'tcolortheeasternhalfbecauseofourcoloringchoicesforthesta
6、tesalongtheMississippi,thereisnopointinwastingtimecompletingthecoloringofthewesternstates.Wesuccessfullycolortheeasternstatesandthenreturntothewest.Unfortunately,wecolorNewMexicoandUtahandthengetstuck,unabletocolor(say)Nevada.What'smore,backtrackingdoesn'thelp,
7、atleastinthesensethatchangingthecolorsforNewMexicoandUtahalonedoesnotallowustoproceedfarther.Depth- rstsearchwouldnowhaveusbacktracktotheeasternstates,tryinganewcolorfor(say)NewYorkinthevainhopethatthiswouldsolveourproblemsoutWest.Thisisobviouslypointless;thebl
8、ockadealongtheMississippimakesitimpossibleforNewYorktohaveanyimpactonourattempttocolorNevadaorotherwesternstates.What'smore,wearelikelytoexamineeverypossiblecoloringoftheeas
