Problem z przepływem sieci - Network flow problem
W optymalizacji kombinatorycznej , problemy przepływu sieci są klasą problemów obliczeniowych, w których wejście jest siecią przepływu (wykres o pojemności liczbowych na krawędzi), a celem jest skonstruowanie przepływu , wartości liczbowe w każdym kierunku, które uwzględniają zdolność ograniczenia i które mają przepływ wejściowy równy przepływowi wychodzącemu na wszystkich wierzchołkach z wyjątkiem niektórych wyznaczonych terminali.
Specyficzne typy problemów z przepływem w sieci obejmują:
- Problem z maksymalnym przepływem , w którym celem jest maksymalizacja całkowitej ilości przepływu z końcówek źródłowych do zacisków zlewu
- Problemu przepływu minimalnego kosztu , w których krawędzie łączy się z kosztami, jak również możliwości, a celem jest osiągnięcie określonej ilości przepływu (lub maksymalny przepływ), który ma minimalną możliwą koszty
- Problemu przepływu wielu surowców , w którym należy skonstruować wiele przepływów do różnych surowców, których całkowity przepływ kwoty razem przestrzegać pojemności
- Przepływ nigdzie zero , rodzaj przepływu badany w kombinatoryce, w którym ilości przepływu są ograniczone do skończonego zbioru wartości niezerowych
Max-min Przepływ cięcia twierdzenie równa wartości przepływu maksymalnego na wartość minimalną cięcia partycja wierzchołków siecią przepływu, który zmniejsza do minimum całkowitą ilość krawędzi przebiegających z jednej strony przegrody na drugiej. Przybliżone twierdzenia o maksymalnym przepływie i minimalnym cięciu zapewniają rozszerzenie tego wyniku na problemy związane z przepływem wielu towarów. Gomory-hu drzewa o nieukierunkowane sieci przepływu stanowi reprezentację zwięzły wszystkich cięć przerwy pomiędzy różnymi parami wierzchołków zaciskowych.
Algorytmy konstruowania przepływów obejmują
- Algorytm Dinica , silnie wielomianowy algorytm dla maksymalnego przepływu
- Algorytm Edmonds-Karp szybszy silnie wielomianowej algorytm maksymalnego przepływu
- Algorytm Ford-Fulkersona , chciwy algorytm maksymalnego przepływu, które nie jest na ogół silnie wielomian
- Przez algorytm Network Simplex , metoda oparta na programowaniu liniowym, ale specjalizuje się dla przepływu sieci
- Algorytm poza przechylonym dla przepływu minimalnego kosztu
- Algorytm maksymalnego przepływu push relabel jedną z najbardziej skutecznych technik znanych maksymalnym przepływie
W przeciwnym razie problem można sformułować jako bardziej konwencjonalny program liniowy lub podobny i rozwiązać za pomocą narzędzia do optymalizacji ogólnego przeznaczenia.
|
Ten artykuł zawiera listę powiązanych elementów, które mają tę samą nazwę (lub podobne). Jeśli link wewnętrzny niepoprawnie doprowadził Cię tutaj, możesz zmienić link, aby wskazywał bezpośrednio na wybrany artykuł. |
