不確定圖最大流可靠性問題研究.pdf

1、東南大學碩士學位論文不確定圖最大流可靠性問題研究姓名：王頤寧申請學位級別：碩士專業(yè)：計算機應用技術指導教師：呂建華20120604AbstractAsaclassicalcombinatorialoptimizationproblem，themaximumflowhasbeenstudiedformorethan40yearsandappliedtoawiderangeofareasUncertaintyisrecognizedtobe

2、allinherentcharacteristicinactualsystems，forexample，componentsinthepowertransmissionnetworkornodesinthedatacommunicationnetworkhasaprobabilityofbeingabnormalWehaveuncertaingraphmodelbyintegratingnetworksystemwithuncertai

3、ntyThemaximumflowproblemonuncertaingraphisanaturalextensionofthetraditionalmaximumflowproblemFirstofall，thisthesisdefinesthemaximumflowproblemandthemostreliablemaximumflowonuncertaingraph，whichcanbeusedtoeffectivelyaddre

4、ssarangeofissuessuchasbuildingareliablenetwork，reliabletransmissionpathselection，aswellastheanalysisoftheweaklinkofasystemANegativeCommunityBasedIterativeAlgorithm(NCBI)isproposed，whicheliminatesthenegativecommunityofthe

5、residualgraphNCBIalgorithmdefinesresidualgraphweightcalculatingrules，andproposedtheconceptofthenegativecommunityIteliminatesthenegativecommunityontheresidualgraphiterativelytoboostthereliabilityofmaximumflowuntilamostrel

6、iablemaximumflowiscalculatedInordertospeeduptheiterativeprocess，thisthesisproposedaCircleCancellationBasedImprovedAlgorithm(CCBI)，whichgivesprioritytotheeliminationofnegativecircleflowinsteadofnegativecommunityInordertor

7、educethecomplexityoftheiterativealgorithm，aMaximumNegativeCommunityEliminationAlgorithm(MNCE)isproposedMNCEalgorithmdirectlyobtainsthemostreliablemaximumflowbyeliminatingthemaximumnegativecommunityontheresidualgraphandef

8、fectivelyimprovestheperformanceofthealgorithmSincenegativecommunityonlyappearsonthestronglyconnectedcomponents，MNCEalgorithmdividestheresidualgraphintoseveralstronglyconnectedsubgraphsSOthatthesearchspaceofthenegativecom

9、munitycanbereducedandthealgorithmcanobtainsagoodscalabilityusingparallelcomputingInordertofurtherreducethespaceofnegativecommunitythisthesisproposesaCriticalEdgesBasedCapacitySimplifyAlgorithm(CEBCS)Criticaledgesaretheed

10、gesofresidualgraph，whichcanaffectthereliabilityofflowFirstlyCEBCSalgorithmdividesthenegativecommunityspaceaccordingtodifferentcombinationsoftheflowoncriticaledges，andthensimplifiesedges’capacityofthepartitionsCEBCSalgori

11、thmsignificantlyreducesthesearchspaceofnegativecommunityandeffectivelyimprovestheperformanceofthealgorithmTheexperimentinvestigatedthefactorsaffectingtheefficiencyofthealgorithm，andcomparedtheperformanceofMNCEalgorithman