Problem med nettverksflyt - Network flow problem

I kombinatorisk optimalisering er nettverksflytproblemer en klasse beregningsproblemer der inngangen er et strømningsnettverk (en graf med numeriske kapasiteter på kantene), og målet er å konstruere en flyt , numeriske verdier på hver kant som respekterer kapasiteten begrensninger og som har innkommende strøm lik utgående strømning i alle toppunktene bortsett fra visse angitte terminaler.

Spesifikke typer nettverksflytproblemer inkluderer:

• Den maksimale strømning problem , der målet er å maksimalisere den totale mengde av strømningen ut av kildeterminalene og i vasken terminalene
• Den minimale kostnader strømning problem , i hvilke kantene har kostnader samt kapasiteter og målet er å oppnå en gitt strømningsmengde (eller en maksimal vannmengde) som har minst mulig kostnad
• Den flervareflyt problem , i hvilken man må konstruere flere strømmer for forskjellige varer hvis totale strømningsmengdene sammen respekterer kapasitetene
• Ingensteds-null strømning , en type flyt studert i kombinatorikk der strømningsmengdene er begrenset til et endelig sett med ikke -nullverdier

Den max-strømning min-snitt-teoremet tilsvarer verdien av en maksimumsstrøm til verdien av et minimum snitt , en skillevegg av hjørnene i strømnings nettverk som minimerer den totale kapasiteten til kantene krysser fra den ene side av skilleveggen til den andre. Omtrentlig max-flow min-cut-teoremer gir en utvidelse av dette resultatet til flere varestrømningsproblemer. Den Gomory-Hu tre av en urettet strømningsnettverk gir en presis representasjon av alle minimums kutt mellom forskjellige par terminal toppunkter.

Algoritmer for å konstruere strømmer inkluderer

• Dinics algoritme , en sterkt polynomisk algoritme for maksimal flyt
• Den Edmonds-Karp algoritme , en raskere sterkt polynomisk algoritme for maksimal strømning
• Den Ford-Fulkerson algoritme , en grådig algoritme for maksimal strømning som ikke er i alminnelighet sterkt polynom
• Den nettverk simplex-algoritmen , en metode basert på lineær programmering, men spesialisert for nettverk flyt
• Den ut-av-kilter algoritme for minimale kostnader strømning
• Den trykk-relabel maksimal strømningsalgoritme , en av de mest effektive kjente teknikker for maksimal strømning

Ellers kan problemet formuleres som et mer konvensjonelt lineært program eller lignende og løses ved hjelp av en optimaliseringsløsningsmiddel for generelle formål.

Indeks over artikler tilknyttet samme navn Denne artikkelen inneholder en liste over relaterte varer som har samme navn (eller lignende navn). Hvis en intern lenke feilaktig førte deg hit, kan det være lurt å endre lenken for å peke direkte på den tiltenkte artikkelen.