Rozdział 8. Algorytmy przepływu w sieciach

Przegląd

Wiele problemów można rozpatrywać jako sieć złożoną z wierzchołków i krawędzi, z przypisaną do każdej krawędzi maksymalną przepustowością przypływu towarów. Algorytmy pomieszczone w tym rozdziale są pod wieloma względami bezpośrednią pochodną zapotrzebowania na rozwiązywanie problemów tych specjalnych klas. Ahuja [1993] podaje szerokie omówienie licznych zastosowań algorytmów sieci przepływowych:

Przydział zadań

Mając zbiór zadań do wykonania przez grupę pracowników, znajdź przydział, który minimalizuje ogólny koszt, przy czym różni pracownicy mogą być różnie opłacani, zależnie od przydzielonego im zadania.

Dopasowywanie obustronne

Mając zbiór kandydatów, z którymi przeprowadzono rozmowy kwalifikacyjne ...

Get Algorytmy. Almanach now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.