资源描述：
《麻省理工 网络优化 课程课件13globalmincutalgorithm.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、15.082and6.855JApril1,2003TheGlobalMinCutproblem1GlobalMincutINPUT:AnetworkG=(N,A)OUTPUT:Acut(S,NS)suchthatcap(S,NS)isminimum.Note:Wedonotassumethatthereisasourcenodesanddestinationnodet.Typically,butnotalways,thenetworkisundirected.2ApplicationtotheTSP:TravelingSalesmanProblemWhatisaminimu
2、mlengthtourthatvisitseachpoint?3AnintegerprogrammingformulationLetx=1ifthereisanarc(i,j)inthetourTijx=0otherwise.ij©Therearetwoarcsincidenttonodei©Foreverycutset(S,N-S),therearetwoarcsfromStoN-S.∑x=2foreachnodei(1)jij∑x≥≠2foreachnodesetSN(2)iS∈∈,jNSij(3)xx=foreachi,jijji0≤≤xx1integerforeachi
3、,j(4)ijij4AnyintegersolutionwillbeatourSAnysolutionto(1)and(3)and(4)willbetheunionofdisjointdirectedcycles.But2ormoredisjointcyclesviolates(2).5MoreontheformulationSupposethatonehasasolutiontothelinearprogramsatisfying(1),(3)and(4)butrelaxingtheintegralityconstraints.©Separationproblem:Either
4、showthatallconstraintsin(2)aresatisfiedorelsedetermineaviolatedconstraint.∑iS∈∈,jNSxij≥≠2foreachnodesetSNInterpretation:eachcuthasflowatleast2.Note:theseparationproblemisrepeatedlysolvedbythebestTSPsolvers.6TheTSPexample2/3Letxbeaflowsatisfying(1),(3)and(4).2/3LetG=(N,A)beagraphinwhichuijist
5、hevaluexinijtheLP.1/2Let(S,T)betheminimumglobalcutinG.ThesolutionxisfeasiblefortheLPifandonlyifthecapacityofthecutisatleast2.Inthiscase,(S,T)isgivesaconstraintviolating(2).7OverviewofwhatthealgorithmillustratesWewillsolvetheproblemasasequenceofnmins-tcutproblems,witharunningtimeofones-tcutalg
6、orithm.©Heuristicscanspeedupalgorithmsinpractice,andsometimesintheory.©Don’tthrowawayvaluableinformation.Reuseitifpossible.©Sometimessubtlechangesmakereallysignificantdifferences.8Algorithm1.AverysimpleversionPhase1:Findthemincut(S,NS)with1∈S.Phase2:Findthemincut(S,NS)with1∈NSWeonlydescrib
7、ePhase1.Phase2issimilar.114Algorithm1.54Forj=2tonfindthebest1-jcut.136Example:Themincuttotherightis63themin1-4cut(and1themin1-5cutand25themin1-6cut).9Algorithm2Forj=2tonfindthebestcutundertherestrictionthatnodes1toj-1areallontheS-sideofthecut
