WikiDer > Проблема сетевого потока
 | Эта статья не цитировать любой источники. (Апрель 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
В комбинаторная оптимизация, проблемы с сетевым потоком представляют собой класс вычислительных задач, в которых на входе проточная сеть (граф с числовыми емкостями на ребрах), и цель состоит в том, чтобы построить поток, числовые значения на каждом ребре, которые соответствуют ограничениям пропускной способности и которые имеют входящий поток, равный исходящему потоку во всех вершинах, кроме определенных назначенных терминалов.
Конкретные типы проблем сетевого потока включают:
- В проблема максимального потока, в котором цель состоит в том, чтобы максимизировать общий объем потока из терминалов источника в терминалы приемника
- В проблема минимальных затрат, в котором края имеют стоимость, а также пропускную способность, и цель состоит в том, чтобы достичь заданного количества потока (или максимального потока), который имеет минимально возможные затраты
- В проблема многопродуктового потока, в котором необходимо построить несколько потоков для разных товаров, общие суммы потоков которых вместе учитывают мощности
- Нигде-нулевой поток, тип потока, изучаемый в комбинаторике, в котором объемы потока ограничены конечным набором ненулевых значений
В теорема о максимальном потоке и минимальном отсечении приравнивает значение максимального расхода к значению минимальный разрез, раздел вершин потоковой сети, который минимизирует общую пропускную способность ребер, пересекающих одну сторону раздела в другую. Приближенные теоремы о максимальном расходе и минимальном сокращении распространить этот результат на проблемы с потоками нескольких товаров. В Дерево Гомори – Ху ненаправленной потоковой сети обеспечивает краткое представление всех минимальных разрезов между различными парами конечных вершин.
Алгоритмы для построения потоков включают
- Алгоритм диника, сильно полиномиальный алгоритм максимального потока
- В Алгоритм Эдмондса – Карпа, более быстрый сильно полиномиальный алгоритм для максимального потока
- В Алгоритм Форда – Фулкерсона, жадный алгоритм для максимального потока, который, вообще говоря, не является сильно полиномиальным
- В сетевой симплексный алгоритм, метод, основанный на линейном программировании, но специализированный для сетевого потока.
- В нестандартный алгоритм для потока с минимальными затратами
- В push – изменить алгоритм максимального потока, один из наиболее эффективных известных методов достижения максимального потока
 | Этот статья включает список связанных элементов с одинаковыми именами (или похожими именами). Если внутренняя ссылка неправильно привел вас сюда, вы можете изменить ссылку, чтобы она указывала непосредственно на предполагаемую статью. |