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

1、東南大學(xué)碩士學(xué)位論文不確定圖最大流可靠性問題研究姓名：王頤寧申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)指導(dǎo)教師：呂建華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