资源描述：
《Chapter 6 Backtracking.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法设计与分析NorthChinaElectricPowerUniversityAlgorithmsDesign&Analysis华北电力大学计算机科学与技术学院SchoolofComputerScience&TechnologyofNorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversityChapter6Backtracking1.Introduction2.GeneratingPermutations3.Thecolorin
2、gproblem4.The8-queensproblem5.符号三角形问题6.旅行售货员问题7.最优装载问题NorthChinaElectricPowerUniversity§1IntroductionInmanyrealworldproblems,asinmostoftheNP-hardproblem,asolutioncanbeobtainedbyexhaustivelysearchingthroughalargebutfinitenumberofpossibilities.Moreover,fo
3、rvirtuallyalltheseproblems,theredoesnotexistanalgorithmthatusesamethodotherthanexhaustivesearch.Hence,theneedfordevelopingsystematictechniquesofsearching,withthehopeofcuttingdownthesearchspacetopossiblyamuchsmallerspace.Backtrackingdesigntechniquecanbed
4、escribedasanorganizedexhaustivesearchwhichcanoftenavoidssearchingallpossibilities.Itisgenerallysuitableforsolvingproblemswhereapotentiallylargebutfinitenumberofsolutionshavetobeinspected.Inthissection,wedescribethegeneralbacktrackingalgorithmasasystemat
5、icsearchmethodthatcanbeappliedtoaclassofsearchproblemswhosesolutionconsistsofavector{x1,x2,…,xi}satisfyingsomepredefinedconstraints.Hereiissomeintegerbetween0andn,wherenisaconstantthatisdependentontheproblemformulation.Insomeproblemsimayvaryfromonesolut
6、iontoanotherasthefollowingexampleillustrate.Examples1:Consideravariantofthepartitionproblemdefinedasfollows.GivenasetofintegersX={x1,x2,…,xn}andanintegery,findasubsetYofXwhosesumisequaltoy.ForinstanceifX={10,20,30,40,50,60}NorthChinaElectricPowerUnivers
7、ityandy=60,thenthereare,forexample,threesolutionsofdifferentlength,namelyItisnothardtodeviseabacktrackingalgorithmtosolvethisproblem.Notethatthisproblemcanbeformulatedinanotherwaysothatthesolutionisabooleanvectoroflengthnintheobviousway.Thus,theabovethr
8、eesolutionsmaybeexpressedbythebooleanvectorsNorthChinaElectricPowerUniversity{10,20,30},{20,40}and{60}{1,1,1,0,0,0},{0,1,0,1,0,0}and{0,0,0,0,0,1}Inbacktracking,eachxiinthesolutionvectorbelongstoafinitelinearlyorderedsetXi.Thus,th
