Глава 22, Потоки в сетях. Во многих ситуациях, имеющих место на практике, мы используем относительно не­большое число циклов

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

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

Задача о максимальном потоке минимальной стоимости представляет собой наиболее общую модель решения задач из числа изученных до сих пор, поэтому вызывает удивле­ние тот факт, что мы можем решить ее, воспользовавшись столь простой реализацией. Ввиду особой важности этой модели, были разработаны и подробно исследованы другие многочисленные реализации метода вычеркивания циклов и многие другие методы. Про­грамма 22.9 отличается удивительной простотой и представляет собой эффективную от­правную точку для вычислений, однако в ней имеются два слабых места, которые могут послужить причиной ее низкой производительности. Во-первых, каждый раз, когда мы ищем отрицательный цикл, мы начинаем с самого начала. Можно ли сохранить проме­жуточную информацию, полученную во время поиска одного отрицательного цикла, ко­торая может оказаться полезной при поиске следующего цикла? Во-вторых, программа 22.9 использует только первый отрицательный цикл, который находит алгоритм Беллма-на-Форда. Сможем ли мы направить поиск на выявление отрицательных циклов с осо­быми свойствами? В разделе 22.6 мы рассмотрим более совершенную реализацию, кото­рая, будучи обобщенной, дает ответы на оба эти вопроса.