Netwerkstroomprobleem - Network flow problem
Bij combinatorische optimalisatie zijn netwerkstroomproblemen een klasse van rekenproblemen waarbij de invoer een stroomnetwerk is (een grafiek met numerieke capaciteiten aan de randen), en het doel is om een stroom te construeren , numerieke waarden op elke rand die de capaciteit respecteren beperkingen en waarbij de inkomende stroom gelijk is aan de uitgaande stroom op alle hoekpunten behalve voor bepaalde aangewezen terminals.
Specifieke soorten netwerkstroomproblemen zijn onder meer:
- Het maximale stroomprobleem , waarbij het doel is om de totale hoeveelheid stroom uit de bronterminals en in de gootsteenterminals te maximaliseren
- Het stroomprobleem met minimale kosten , waarbij de randen zowel kosten als capaciteiten hebben en het doel is om een bepaalde hoeveelheid stroom (of een maximale stroom) te bereiken met zo laag mogelijke kosten
- Het multi-commodity flow-probleem , waarbij men meerdere stromen moet construeren voor verschillende commodities waarvan de totale stroombedragen samen de capaciteiten respecteren
- Nergens nul stroming , een type stroming bestudeerd in combinatoriek waarin de stromingshoeveelheden beperkt zijn tot een eindige reeks niet -nulwaarden
De max-flow min-cut-stelling stelt de waarde van een maximale flow gelijk aan de waarde van een minimale cut , een partitie van de hoekpunten van het flow-netwerk die de totale capaciteit van randen die van de ene kant van de partitie naar de andere kruisen minimaliseert. Geschatte max-flow min-cut-stellingen bieden een uitbreiding van dit resultaat tot multi-commodity flow-problemen. De Gomory-Hu-boom van een ongericht stroomnetwerk biedt een beknopte weergave van alle minimale sneden tussen verschillende paren eindpuntpunten.
Algoritmen voor het construeren van stromen omvatten
- Dinic's algoritme , een sterk polynoom algoritme voor maximale doorstroming
- Het Edmonds-Karp-algoritme , een sneller sterk polynoom-algoritme voor maximale doorstroming
- Het Ford-Fulkerson-algoritme , een hebberig algoritme voor maximale doorstroming dat over het algemeen niet sterk polynoom is
- Het netwerk-simplex-algoritme , een methode gebaseerd op lineaire programmering maar gespecialiseerd voor netwerkstroom
- Het ongeëvenaarde algoritme voor een stroom met minimale kosten
- Het push-herlabel algoritme voor maximale doorstroming , een van de meest efficiënte bekende technieken voor maximale doorstroming
Anders kan het probleem worden geformuleerd als een meer conventioneel lineair programma of soortgelijk en opgelost met behulp van een optimalisatieoplosser voor algemene doeleinden.
|
Dit artikel bevat een lijst met gerelateerde items met dezelfde naam (of vergelijkbare namen). Als een interne link u ten onrechte hierheen heeft geleid, wilt u misschien de link wijzigen zodat deze rechtstreeks naar het bedoelde artikel verwijst. |
