![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 22, Потоки в сетях. Во многих ситуациях, имеющих место на практике, мы используем относительно небольшое число циклов
Можно разработать стратегию выявления циклов отрицательной стоимости, гарантирующую, что число использованных циклов отрицательной стоимости меньше VE (см. раздел ссылок). Этот результат имеет важное значение, ибо он устанавливает тот факт, что задача о потоке минимальной стоимости имеет решение (равно как и все другие задачи, которые сводятся к ней). Тем не менее, на практике предпочтение обычно отдается реализациям, которые, признавая (теоретически) оценки для худшего случая, используют значительно меньше итераций при решении задач, возникающих на практике, чем их число, которое прогнозируется границами для худшего случая. Задача о максимальном потоке минимальной стоимости представляет собой наиболее общую модель решения задач из числа изученных до сих пор, поэтому вызывает удивление тот факт, что мы можем решить ее, воспользовавшись столь простой реализацией. Ввиду особой важности этой модели, были разработаны и подробно исследованы другие многочисленные реализации метода вычеркивания циклов и многие другие методы. Программа 22.9 отличается удивительной простотой и представляет собой эффективную отправную точку для вычислений, однако в ней имеются два слабых места, которые могут послужить причиной ее низкой производительности. Во-первых, каждый раз, когда мы ищем отрицательный цикл, мы начинаем с самого начала. Можно ли сохранить промежуточную информацию, полученную во время поиска одного отрицательного цикла, которая может оказаться полезной при поиске следующего цикла? Во-вторых, программа 22.9 использует только первый отрицательный цикл, который находит алгоритм Беллма-на-Форда. Сможем ли мы направить поиск на выявление отрицательных циклов с особыми свойствами? В разделе 22.6 мы рассмотрим более совершенную реализацию, которая, будучи обобщенной, дает ответы на оба эти вопроса.
|