Глава 22, Потоки в сетях. ния задач о потоках в сетях, рассматриваемые далее алгоритмы решения задач о потоках в сети намного проще и эффективнее

ния задач о потоках в сетях, рассматриваемые далее алгоритмы решения задач о потоках в сети намного проще и эффективнее, чем те, которые решают LP-задачи. Однако иссле­дователи продолжают совершенствовать программы решения LP-задач, и все еще оста­ется возможность того, что качественный алгоритм решения LP-задачи, будучи исполь­зованным для решения задач о потоках в сетях, может когда-нибудь превзойти по всем параметрам алгоритмы, которые мы рассматриваем в данной главе.

Классическое решение задач о потоках в сетях тесно связаны с другими, уже изучен­ными, алгоритмами на графах, и мы можем писать удивительно компактные программы их решения, воспользовавшись разработанными ранее алгоритмическими инструментами. Как мы могли убедиться во множестве других ситуаций, качественные алгоритмы и струк­туры данных иногда позволяют существенно уменьшить время выполнения программ. Изучение методов разработки более совершенных реализаций классических алгоритмов, способных решать обширные классы задач, продолжается, и время от времени появля­ются новые подходы.

В разделе 22.1 мы проведем исследование свойств транспортных сетей (flow networks), в рамках которого мы интерпретируем веса ребер как пропускные способности (capacities) и рассматриваем свойства потоков (flows), представленные вторым множеством весов ре­бер, которые удовлетворяют некоторым естественным условиям. Далее мы рассмотрим задачу о максимальном потоке, которая заключается в вычислении лучшего в некотором специальном техническом смысле потока. В разделах 22.2 и 22.3 мы рассмотрим два под­хода к решению задачи о максимальном потоке и изучим некоторое множество различ­ных реализаций ее решения. Многие из алгоритмов и структур данных, которые мы рас­сматривали ранее, непосредственно зависят от разработки эффективного решения задачи о максимальном потоке. У нас еще нет наилучшего из возможных алгоритмов решения задачи о максимальном потоке, поэтому мы пока рассмотрим конкретные решения, ис­пользуемые на практике. Чтобы продемонстрировать масштабность и разноплановость задачи поиска максимального потока, в разделе 22.4 мы рассмотрим другие формулировки этой задачи, равно как и возможность ее сведения к другим задачам.

Алгоритмы решения задачи о максимальном потоке и их реализации подготавливают нас к обсуждению более важной и более общей задачи о потоке минимальной стоимости, по условиям которой мы присваиваем ребрам стоимости (еще одно множество весов ребер) и определяем стоимости потоков, когда ищем решение задачи о максимальном потоке, обладающем минимальной стоимостью. Мы рассмотрим классическое общее ре­шение задачи о потоке минимальной стоимости, известное как алгоритм вычеркивания цик­лов (cycle-canceling algorithm), а затем, в разделе 22.6, дадим конкретную реализацию алго­ритма вычеркивания циклов, известную как сетевой симплексный алгоритм. В разделе 22.3 мы обсудим все сведения к задаче о потоке минимальной стоимости, которые включают, помимо прочих, все приложения, которые отмечались выше.

Алгоритмы решения задачи о потоках в сети представляют собой тему, подходящую для завершения данной книги, сразу по нескольким причинам. Упомянутая тема является как бы вознаграждением за усилия, потраченные на изучение базовых алгоритмических ин­струментальных средств, таких как связные списки, очереди с приоритетами и общие методы поиска на графах. Классы, осуществляющие обработку графов, которые изуча­лись в этой книге, непосредственно приводят к компактным и эффективным реализаци-

Часть 5. Алгоритмы на графах

ям классов для задач о потоках в сетях. Эти реализации поднимают нас на новый уровень возможностей решения задач и могут быть непосредственно использованы в многочис­ленных практических приложениях. Более того, изучение возможностей их применения и понимание свойственных им ограничений позволяют установить контекст для исследо­ваний, направленных на получение более совершенных алгоритмов решения еще более сложных задач, - именно этим вопросам посвящается часть 8.