Algorithms Illuminated Part 4.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：12.41M 资料格式：pdf 举报版权申诉

justidle-16053332-16359647523581949456.pdf-第1页.png

第1页 / 共274页

justidle-16053332-16359647523581949456.pdf-第2页.png

第2页 / 共274页

justidle-16053332-16359647523581949456.pdf-第3页.png

第3页 / 共274页

justidle-16053332-16359647523581949456.pdf-第4页.png

第4页 / 共274页

justidle-16053332-16359647523581949456.pdf-第5页.png

第5页 / 共274页

justidle-16053332-16359647523581949456.pdf-第6页.png

第6页 / 共274页

justidle-16053332-16359647523581949456.pdf-第7页.png

第7页 / 共274页

justidle-16053332-16359647523581949456.pdf-第8页.png

第8页 / 共274页

文本预览

AlgorithmsIlluminatedPart4:AlgorithmsforNP-HardProblemsTimRoughgarden

c2020byTimRoughgardenAllrightsreserved.Noportionofthisbookmaybereproducedinanyformwithoutpermissionfromthepublisher,exceptaspermittedbyU.S.copyrightlaw.FirstEditionCoverimage:NormanZammitt,BlueBurning,1982acryliconcanvas;84x1681/2in.(213.36x427.99cm)SanFranciscoMuseumofModernArt,GiftofJudgeandMrs.WilliamJ.LasarowcEstateofNormanZammittPhotograph:KatherineDuTielISBN:978-0-9992829-6-0(Paperback)ISBN:978-0-9992829-7-7(ebook)LibraryofCongressControlNumber:2017914282SoundlikeyourselfPublishing,LLCNewYork,NYsoundlikeyourselfpublishing@gmail.comwww.algorithmsilluminated.org

ContentsPrefacev19WhatIsNP-Hardness?119.1MSTvs.TSP:AnAlgorithmicMystery119.2PossibleLevelsofExpertise719.3EasyandHardProblems919.4AlgorithmicStrategiesforNP-HardProblems1719.5ProvingNP-Hardness:ASimpleRecipe2319.6RookieMistakesandAcceptableInaccuracies33Problems3720CompromisingonCorrectness:EﬃcientInexactAlgorithms4120.1MakespanMinimization4120.2MaximumCoverage55*20.3InﬂuenceMaximization6620.4The2-OPTHeuristicAlgorithmfortheTSP7520.5PrinciplesofLocalSearch82Problems9421CompromisingonSpeed:ExactIneﬃcientAlgorithms10521.1TheBellman-Held-KarpAlgorithmfortheTSP105*21.2FindingLongPathsbyColorCoding11421.3Problem-SpeciﬁcAlgorithmsvs.MagicBoxes12721.4MixedIntegerProgrammingSolvers12921.5SatisﬁabilitySolvers134Problems140iii

ivContents22ProvingProblemsNP-Hard14822.1ReductionsRevisited14822.23-SATandtheCook-LevinTheorem15022.3TheBigPicture15222.4ATemplateforReductions15622.5IndependentSetIsNP-Hard158*22.6DirectedHamiltonianPathIsNP-Hard16322.7TheTSPIsNP-Hard16922.8SubsetSumIsNP-Hard172Problems17823P,NP,andAllThat182*23.1AmassingEvidenceofIntractability183*23.2Decision,Search,andOptimization185*23.3NP:ProblemswithEasilyRecognizedSolutions186*23.4TheP6=NPConjecture192*23.5TheExponentialTimeHypothesis195*23.6NP-Completeness200Problems20524CaseStudy:TheFCCIncentiveAuction20824.1RepurposingWirelessSpectrum20824.2GreedyHeuristicsforBuyingBackLicenses21124.3FeasibilityChecking21924.4ImplementationasaDescendingClockAuction22624.5TheFinalOutcome231Problems233Epilogue:AFieldGuidetoAlgorithmDesign236HintsandSolutions239Index251

PrefaceThisbookisthefourthinaseriesbasedonmyonlinealgorithmscoursesthathavebeenrunningregularlysince2012,whichinturnarebasedonanundergraduatecoursethatItaughtmanytimesatStanfordUniversity.Part4assumesatleastsomefamiliaritywithasymptoticanalysisandbig-Onotation,graphsearchandshortest-pathalgorithms,greedyalgorithms,anddynamicprogramming(allcoveredinParts1–3).WhatWe’llCoverinThisBookAlgorithmsIlluminated,Part4isallaboutNP-hardproblemsandwhattodoaboutthem.AlgorithmictoolsfortacklingNP-hardproblems.Manyreal-worldproblemsare“NP-hard”andappearunsolvablebythetypesofalways-correctandalways-fastalgorithmsthathavestarredintheﬁrstthreepartsofthisbookseries.WhenanNP-hardproblemshowsupinyourownwork,youmustcompromiseoneithercorrect-nessorspeed.We’llseetechniquesold(likegreedyalgorithms)andnew(likelocalsearch)fordevisingfastheuristicalgorithmsthatare“approximatelycorrect,”withapplicationstoscheduling,inﬂuencemaximizationinsocialnetworks,andthetravelingsalesmanproblem.We’llalsocovertechniquesold(likedynamicprogramming)andnew(likeMIPandSATsolvers)fordevelopingcorrectalgorithmsthatimprovedramaticallyonexhaustivesearch;applicationshereincludethetravelingsalesmanproblem(again),ﬁndingsignalingpathwaysinbiologicalnetworks,andtelevisionstationrepackinginarecentandhigh-stakesspectrumauctionintheUnitedStates.RecognizingNP-hardproblems.ThisbookwillalsotrainyoutoquicklyrecognizeanNP-hardproblemsothatyoudon’tinadver-v

viPrefacetentlywastetimetryingtodesignatoo-good-to-be-truealgorithmforit.You’llacquirefamiliaritywithmanyfamousandbasicNP-hardproblems,rangingfromsatisﬁabilitytographcoloringtotheHamil-tonianpathproblem.Throughpractice,you’lllearnthetricksofthetradeinprovingproblemsNP-hardviareductions.Foramoredetailedlookintothebook’scontents,checkoutthe“Upshot”sectionsthatconcludeeachchapterandhighlightthemostimportantpoints.The“FieldGuidetoAlgorithmDesign”onpage236providesabird’s-eyeviewofhowthetopicsofthisbookﬁtintothebiggeralgorithmicpicture.Thestarredsectionsofthebookarethemostadvancedones.Thetime-constrainedreadercanskipthesesectionsonaﬁrstreadingwithoutanylossofcontinuity.Topicscoveredintheﬁrstthreeparts.AlgorithmsIllumi-nated,Part1coversasymptoticnotation(big-Onotationanditsclosecousins),divide-and-conqueralgorithmsandthemastermethod,randomizedQuickSortanditsanalysis,andlinear-timeselectionalgo-rithms.Part2isaboutdatastructures(heaps,balancedsearchtrees,hashtables,bloomﬁlters),graphprimitives(breadth-anddepth-ﬁrstsearch,connectivity,shortestpaths),andtheirapplications(rang-ingfromdeduplicationtosocialnetworkanalysis).Part3focusesongreedyalgorithms(scheduling,minimumspanningtrees,cluster-ing,Huﬀmancodes)anddynamicprogramming(knapsack,sequencealignment,shortestpaths,optimalsearchtrees).SkillsYou’llLearnFromThisBookSeriesMasteringalgorithmstakestimeandeﬀort.Whybother?Becomeabetterprogrammer.You’lllearnseveralblazinglyfastsubroutinesforprocessingdataaswellasseveralusefuldatastructuresfororganizingdatathatyoucandeploydirectlyinyourownprograms.Implementingandusingthesealgorithmswillstretchandimproveyourprogrammingskills.You’llalsolearngeneralalgorithmdesignparadigmsthatarerelevanttomanydiﬀerentproblemsacrossdiﬀerentdomains,aswellastoolsforpredictingtheperformanceofsuchalgorithms.These“algorithmicdesignpatterns”canhelpyoucomeupwithnewalgorithmsforproblemsthatariseinyourownwork.

分享到：

赞收藏

资料库

Algorithms Illuminated Part 4.pdf

相关推荐

课程资源

热门标签

最新资料