资源描述：
《1 an average analysis of backtracking on random constraint satisfaction problems》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、AnAverageAnalysisofBacktrackingonRandom*ConstraintSatisfactionProblemsKeXuandWeiLiNationalLaboratoryofSoftwareDevelopmentEnvironmentDepartmentofComputerScienceandEngineeringBeijingUniversityofAeronauticsandAstronautics,Beijing100083,P.R.China#Email:{
2、kexu,liwei}@nlsde.buaa.edu.cnAbstract.InthispaperweproposearandomCSPmodel,calledModelGB,whichisanaturalgeneralizationofstandardModelB.ThispaperconsidersModelGBinthecasewhereeachconstraintiseasytosatisfy.InthiscaseModelGBexhibitsnon-trivialbehaviour(nott
3、riviallysatisfiableorunsatisfiable)asthenumberofvariablesapproachesinfinity.Adetailedanalysistoobtainanasymptoticestimate(goodto1+o(1))oftheaveragenumberofnodesinasearchtreeusedbythebacktrackingalgorithmonModelGBisalsopresented.Itisshownthattheaveragenu
4、mberofnodesrequiredforfindingallsolutionsorprovingthatnosolutionexistsgrowsexponentiallywiththenumberofvariables.SothismodelmightbeaninterestingdistributionforstudyingthenatureofhardinstancesandevaluatingtheperformanceofCSPalgorithms.Inaddition,wefurthe
5、rinvestigatethebehaviouroftheaveragenumberofnodesasr(theratioofconstraintstovariables)varies.Theresultsindicatethatasrincreases,randomCSPinstancesgeteasierandeasiertosolve,andthebasefortheaveragenumberofnodesthatisexponentialinntendsto1asrapproachesinfi
6、nity.Therefore,althoughtheaveragenumberofnodesusedbythebacktrackingalgorithmonrandomCSPisexponential,manyCSPinstanceswillbeveryeasytosolvewhenrissufficientlylarge.Keywords.analysisofalgorithms,averagecomplexity,backtrackingalgorithms,CSP.*Researchsuppor
7、tedbyNational973ProjectofChinaGrantNo.G1999032701.#Forthefirstauthor,thereisapermanentemailaddressthatiske.xu@263.net.11.IntroductionAconstraintsatisfactionproblem(CSP)consistsofafinitesetU={u1,×××,un}ofnvariablesandasetofconstraints.Foreachvariableuado
8、mainDwithdelementsisiiispecified;avariablecanonlybeassignedavaluefromitsdomain.For2£k£naconstraintCi1,i2,×××,ikconsistsofasubset{ui1,ui2,×××,uik}ofUandarelationRi1,i2,×××,ikÍDi1´×××´Dik,wherei1,i2,×××,ikaredistinct.Ci1,i2,×××,iki
