Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 22. Потоки в сетях
|
|
ные реализации послужат объектом исследований с целью определения более точных границ для худших случаев. В самом деле, это одна из главных причин, чтобы провести их исследование в первую очередь! Теперь, как мы могли убедиться, реализация и использование большого класса таких реализаций тривиальны: мы просто выполняем подстановку различных реализаций обобщенной очереди или определений приоритетов в программу 22.3. Анализ различий поведения в условиях худшего случая представляет собой еще более трудную задачу, что подтверждается классическими результатами, к изучению которых применительно к двум базовым реализациям рассмотренного выше алгоритма вычисления аугментальных путей мы далее переходим.
Сначала мы проводим анализ алгоритма вычисления кратчайшего аугментального пути. Этот метод не является предметом задачи, представленной на рис. 22.19. В самом деле, мы не можем использовать ее для замены множителя М выражением VE/2 при определении времени выполнения, тем самым утверждая, что задача определения потоков в сетях относится к числу решаемых. Мы даже можем классифицировать ее как относящуюся к категории легко решаемых (решаемую за полиномиальное время в практических случаях посредством простой, но в то же время искусной реализации).
Свойство 22.7. Число аугментальных путей, необходимых для реализации алгоритма Форда-Фалкерсона, использующей кратчайшие аугменталъные пути, не превышает VE/2.
Доказательство: Сначала, как это следует из примера на рис. 22.17, ни один из кратчайших путей не короче предыдущего. Чтобы установить этот факт, мы покажем методом доказательства от противного, что справедливо более сильное свойство: никакой аугментальный путь не может уменьшить длину кратчайшего пути из вершины s в любую другую вершину остаточной сети. Предположим, тем не менее, что некоторому аугментальному пути это удается, а вершина v есть первая вершина на этом пути. При этом мы рассмотрим два случая: либо никакая вершина на новом, более коротком пути из s в v не появляется в этом аугментальном пути, либо некоторая вершина w на новом кратчайшем пути из s в v появляется где-то между v и t в аугментальном пути. Обе ситуации противоречат условию минимальности аугментального пути.
Теперь, по построению, каждый аугментальный путь содержит, по меньшей мере, одно критическое ребро: ребро, которое удаляется из остаточной сети, поскольку оно соответствует либо прямому ребру, которое наполняется до пропускной способности, либо обратному ребру, которое опорожняется. Предположим, что ребро u-v есть критическое ребро для аугментального пути Р длиной d. Следующий аугментальный путь должен иметь, по меньшей мере, длину d + 2, поскольку этот путь должен проходить из s в v, затем вдоль ребра u-v, затем из и в t. Первый сегмент имеет, по меньшей мере, длину, на 1 больше, чем расстояние от s в и в Р, а заключительный сегмент длины, по меньшей мере, на 1 больше, чем расстояние из v в t в P, так что длина этого пути на 2 больше, чем Р.
Поскольку длины аугментальных путей не могут быть больше V, из этого факта следует, что каждое ребро может оказаться критическим на максимум V/2 аугментальных путях, так что общее число аугментальных путей не может быть больше EV/2. ■
Следствие. Время, необходимое для отыскания максимального потока в разреженной сети, равно O(V3).
Доказательство: Время, необходимое для отыскания аугментального пути, есть О(Е), так что общее время есть О(ЕV2). Отсюда сразу же следует указанная выше граница. ■
Часть 5. Алгоритмы на графах
Величина V3достаточно велика, чтобы служить гарантией высокой производительности алгоритма на крупных сетях. Но этот факт не должен воспрепятствовать применению этого алгоритма на крупных сетях, поскольку это есть оценка его производительности в худшем случае, которая не всегда подходит для прогнозирования производительности алгоритма в практических ситуациях. Например, как только что было установлено, максимальная пропускная способность М (или максимальное отношение пропускных способностей) может быть намного меньше V так что свойство 22.6 обеспечивает более точную границу. В самом деле, в лучшем случае число аугментальных путей, необходимых для метода Форда-Фалкерсона, меньше полустепени исхода вершины s или полустепени захода вершины t, которые, в свою очередь, могут быть намного меньше V. При наличии такого разброса производительности в лучшем и худшем случаях, сравнивать алгоритмы нахождения аугментальных путей, взяв за основу только границы худшего случая, по меньшей мере, неразумно.
Тем не менее, другие реализации, которые столь же просты, как и метод определения кратчайшего аугментального пути, могут иметь более точные границы или используют границы, хорошо зарекомендовавшие себя на практике (или оба вида границ). Например, в примере, представленном на рис. 22.17 и 22.18, алгоритм вычисления максимального аугментального пути использует намного меньше путей для отыскания максимального потока, чем метод определения кратчайшего аугментального пути. Теперь мы обратимся к анализу худшего случая рассматриваемого алгоритма.
Во-первых, так же, как и в случае алгоритма Прима и алгоритма Дейкстры (см. разделы 20.6 и 21.2), мы можем реализовать очередь с приоритетами таким образом, что для выполнения рассматриваемым алгоритмом одной итерации в худшем случае понадобится время, пропорциональное V2 (для насыщенных графов), либо {Е + V) log V (для разреженных графов), тем не менее, эти оценки пессимистичны, поскольку алгоритм сразу же остановится, как только достигнет стока. Мы также убедились, что можем немного улучшить рабочие характеристики, если воспользуемся более совершенными структурами данных. Однако более важной и более труднорешаемой задачей является определение необходимого числа аугментальных путей.
Свойство 22.8. число аугментальных путей, необходимых для реализации алгоритма Форда-Фалкерсона с поиском максимальных аугментальных путей, не превышает 2Е lgM
Доказательство: Пусть дана некоторая сеть, a F есть величина ее максимального потока. Пусть v есть значение потока в той точке выполнения алгоритма, когда мы начинаем поиск аугментального пути. Применяя свойство 22.2 к остаточной сети, мы можем разложить поток максимум на Е ориентированных путей, что дает нам в сумме F - v, так что поток, по меньшей мере, в одном из путей есть, по меньшей мере, (F — v)/E. Теперь либо мы найдем максимальный поток перед тем, как выполнять построение следующих 2Е аугментальных путей, либо величина такого аугментального пути после построения этой последовательности из 2Е путей станет меньше, чем (F— v)/2E, что в свою очередь меньше, чем одна вторая от значения максимума, имевшего место перед тем, как была построена эта последовательность из 2Е путей. То есть, в худшем случае нам нужна последовательность из 2Е путей, чтобы уменьшить количество путей в два раза. Первое значение количества путей не может превышать М, которое мы должны уменьшать в два раза максимум lgM раз, так что в конечном итоге мы имеем максимум lgM последовательностей из 2Е путей. ■
|
|