计算机程序设计艺术第四卷 Combinatorial Searching

KNUTHTHEARTOFCOMPUTERPROGRAMMINGVOLUME4PRE-FASCICLE0AADRAFTOFSECTION7:INTRODUCTIONTOCOMBINATORIALSEARCHINGDONALDE.KNUTHStanfordUniversityADDISON{WESLEY677InternetStanfordGraphBaseMMIXInternetpagehttp://www-s-faulty.stanford.edu/~knuth/taop.htmlontainsurrentinformationaboutthisbookandrelatedbooks.Seealsohttp://www-s-faulty.stanford.edu/~knuth/sgb.htmlforinformationaboutTheStanfordGraphBase,inludingdownloadablesoftwarefordealingwiththegraphsusedinmanyoftheexamplesinChapter7.Seealsohttp://www-s-faulty.stanford.edu/~knuth/mmixware.htmlfordown-loadablesoftwaretosimulatetheMMIXomputer.Copyright2007byAddison{WesleyAllrightsreserved.Nopartofthispubliationmaybereprodued,storedinaretrievalsystem,ortransmitted,inanyform,orbyanymeans,eletroni,mehanial,photo-opying,reording,orotherwise,withouttheprioronsentofthepublisher,exeptthattheoÆialeletronilemaybeusedtoprintsingleopiesforpersonal(notommerial)use.Zerothprinting(revision2),06August2007FOLLANDPASCALInternetPREFACEToputallthegoodstuintoonebookispatentlyimpossible,andattemptingeventobereasonablyomprehensiveaboutertainaspetsofthesubjetislikelytoleadtorunawaygrowth.|GERALDB.FOLLAND,\Editor’sCorner(2005)Ladernierehosequ’ontrouveenfaisantunouvrageestdesavoirellequ’ilfautmettrelapremiere.|BLAISEPASCAL,Pensees740(.1660)ThisbookletontainsdraftmaterialthatI’mirulatingtoexpertsintheeld,inhopesthattheyanhelpremoveitsmostegregiouserrorsbeforetoomanyotherpeopleseeit.Iamalso,however,postingitontheInternetforourageousand/orrandomreaderswhodon’tmindtheriskofreadingafewpagesthathavenotyetreahedaverymaturestate.Beware:ThismaterialhasnotyetbeenproofreadasthoroughlyasthemanusriptsofVolumes1,2,and3wereatthetimeoftheirrstprintings.Andthosearefully-hekedvolumes,alas,weresubsequentlyfoundtoontainthousandsofmistakes.Giventhisaveat,Ihopethatmyerrorsthistimewillnotbesonumerousand/orobtrusivethatyouwillbedisouragedfromreadingthematerialarefully.Ididtrytomakethetextbothinterestingandauthoritative,asfarasitgoes.Buttheeldisvast;Iannothopetohavesurroundeditenoughtoorralitompletely.SoIbegyoutoletmeknowaboutanydeieniesthatyoudisover.Toputthematerialinontext,thispre-fasileontainstheopeningremarksintendedtolaunhalong,longhapteronombinatorialalgorithms.Chapter7isplannedtobebyfarthelongestsinglehapterofTheArtofComputerProgramming;itwilleventuallyllatleastthreevolumes(namelyVolumes4A,4B,and4C),assumingthatI’mabletoremainhealthy.Liketheseond-longesthapter(Chapter5),itbeginswithpump-primingintrodutorymaterialthatomesbeforethemaintext,inludingdozensofexerisestogettheballrolling.Alongvoyageliesahead,andsomeimportantprovisionsneedtobebroughtonboardbeforeweembark.FurthermoreIwanttominimizetheshokoftransitionbetweenChapter6andthenewhapter,beauseChapter6wasoriginallywrittenandpublishedmorethanthirtyyearsago.Chapter7proper,whihfollowsthematerialinthepresentpre-fasile,beginswithSetion7.1:ZerosandOnes.Setion7.1isanothersortofintro-dution,atadierentlevel;ithasfoursubsetionsaboutBooleanandbitwiseomputations,appearingrespetivelyinpre-fasiles0b,0,1a,and1b.Thenextpart,7.2,isaboutgeneratingallpossibilities,anditbeginswithSetioniiiivPREFACEStanfordGraphBaseDeanGoogleve-letterwordsInternetWilsonKnuthHARARY7.2.1:GeneratingBasiCombinatorialPatterns.FasilesforSetion7.2.1havealreadyappearedinprint.Setion7.2.2willdealwithbaktrakingingeneral.Andsoitwillgoon,ifallgoeswell;anoutlineoftheentireChapter7asurrentlyenvisagedappearsonthetaopwebpagethatisitedonpageii.ThisintrodutorysetionhasturnedouttohavemorethantwieasmanyexerisesasIhadoriginallyplanned.Butmanyofthemarequitesimple,in-tendedtoreinforethereader’sunderstandingofbasidenitions,ortoaquaintreaderswiththejoysofTheStanfordGraphBase.Otherexerisesweresimplyirresistible,astheyriedouttobeinludedhere|although,believeitornot,IdidrejetmorepotentialleadsthanIatuallyfollowedup.Mynotesonombinatorialalgorithmshavebeenaumulatingformorethanfortyyears,soIfearthatinseveralrespetsmyknowledgeiswoefullybehindthetimes.Pleaselook,forexample,attheexerisesthatI’velassedasresearhproblems(ratedwithdiÆultylevel46orhigher),namelyexerises15,16,67,and125;I’vealsoimpliitlymentionedorposedadditionalunsolvedquestionsintheanswerstoexerises7and133(m).Arethoseproblemsstillopen?Pleaseinformmeifyouknowofasolutiontoanyoftheseintriguingquestions.Andofourseifnosolutionisknowntodaybutyoudomakeprogressonanyoftheminthefuture,Ihopeyou’llletmeknow.IurgentlyneedyourhelpalsowithrespettosomeexerisesthatImadeupasIwaspreparingthismaterial.Iertainlydon’tliketoreeivereditforthingsthathavealreadybeenpublishedbyothers,andmostoftheseresultsarequitenatural\fruitsthatwerejustwaitingtobe\pluked.Thereforepleasetellmeifyouknowwhodeservestoberedited,withrespettotheideasfoundinexerises3,25,32,35,72,84,108,116,and135,and/ortheanswertoexerises105.ThankstoJeDeanofGoogleforlettingmelookatthestatistisofve-letterwordsintheInternetatthebeginningof2004,andtoRobinWilsonoftheOpenUniversityforhisarefulreadingandmanydetailedsuggestions.Ishallhappilypayander’sfeeof$2.56foreaherrorinthisdraftwhenitisrstreportedtome,whetherthaterrorbetyp