АиСД S04E04. Потоки. Алгоритм Диница. Алгоритм Малхотры — Кумара — Махешвари

• Обсуждение алгоритма Эдмана-Карпа и масштабирования.  

• Напоминание о поиске дополняющего пути и увеличении потока вдоль него.  

• Условие: остаточная пропускная способность всех ребер должна быть больше нуля.  

• Алгоритм работает за время O nm^2, где n - количество вершин, m - количество ребер.  

• Идея: использовать обход в ширину для нахождения кратчайших путей.  

• Удаление ненужных ребер и вершин для повышения эффективности.  

• Создание слоистой сети для нахождения кратчайших путей.  

• Удаление вершин и ребер, не влияющих на кратчайшие пути.  

• Использование обхода в ширину для нахождения кратчайших путей.  

• Обход в ширину для нахождения кратчайших путей.  

• Удаление тупиков и ненужных вершин.  

• Использование любого ребра для нахождения кратчайшего пути.  

• Нахождение кратчайшего пути и добавление потока вдоль него.  

• Удаление ребер с минимальной пропускной способностью.  

• Обратные ребра не влияют на кратчайшие пути и могут быть удалены.  

• Удаляем лишние тупики после удаления ребра.  

• Каскадно удаляем тупики, которые появились.  

• Продолжаем искать кратчайший путь.  

• Находим минимальное ребро на пути.  

• Увеличиваем поток вдоль пути.  

• Удаляем тупики и проверяем наличие путей.  

• Используем BFS и DFS для нахождения путей.  

• Увеличиваем поток на минимальное ребро.  

• Удаляем тупики, пока не найдем пути.  

• Если нет путей, значит, все пути найдены.  

• Расстояние до вершины увеличивается.  

• Цикл выполняется не более n раз.  

• Удаляем тупики лениво, чтобы не удалять их каскадно.  

• Увеличиваем поток по всем ребрам.  

• Удаляем ребра, которые стали насыщенными.  

• Удаление тупиков занимает O n.  

• Тупики удаляются навсегда.  

• Время удаления тупиков незначительно по сравнению с DFS.  

• Добавление масштабирования улучшает время работы.  

• Время работы становится O n log n.  

• Это приближает алгоритм к современным реализациям.  

• Обсуждение необходимости оптимизации пути.  

• План: сохранить все найденные пути и использовать их для улучшения.  

• Цель: найти минимальное ребро на пути и прибавить его ко всем ребрам.  

• Вспоминание прошлогодних методов работы с деревьями отрезков.  

• Применение этих методов для оптимизации пути.  

• Удаление нулевых ребер и сохранение оставшихся путей.  

• Удаление нулевых ребер и сохранение оставшихся путей.  

• Поиск минимального ребра и его удаление.  

• Продолжение поиска пути до следующей вершины с оставшимся путем.  

• Описание структуры дерева, образованного сохраненными путями.  

• У каждой вершины будет не более одного помеченного ребра.  

• Алгоритм поиска пути до корня дерева.  

• Если вершина является корнем дерева, то это дополняющий путь.  

• Применение действий: найти минимальную трудоспособность, прибавить дельту, удалить минимальное ребро.  

• Если вершина не является корнем дерева или тупиком, то продолжаем поиск.  

• Начало алгоритма: использование BFS.  

• Применение оптимизационных действий для улучшения пути.  

• Начинаем с вершины С и идем к корню дерева.  

• Находим минимальное ребро и добавляем дельту ко всем ребрам на пути.  

• Удаляем ребра, если они ведут в тупик.  

• Если нет тупика, добавляем ребро в дерево.  

• Используем структуру данных, которая умеет считать функции на путях и перестраивать деревья.  

• Добавляем и удаляем ребра лениво, чтобы избежать квадратичного роста.  

• Оцениваем время работы алгоритма.  

• Учитываем, что каждая ветка ифа выполняется не более m раз.  

• Линкуем ребра не более m раз, что позволяет оценить время работы за O(m log n).  

• Алгоритм работает за логарифмическое время.  

• Каждое ребро удаляется не более одного раза.  

• Суммарное время работы составляет логарифм от числа ребер.  

• Можно улучшить алгоритм, уменьшив логарифм до логарифма по основанию м делить на н.  

• Это позволяет хранить меньше деревьев и улучшить производительность.  

• Параметры алгоритма можно подогнать для лучшего результата.  

• Обсуждение улучшения алгоритма для общего развития.  

• Планы на будущее: обсуждение единичных графов и других алгоритмов.  

• Обещание рассказать больше о других алгоритмах, если будет время.  

• Алгоритм для поиска кратчайших путей в графе.  

• Удаление одной вершины или ребра на каждом шаге.  

• Идея удаления целой вершины вместо ребра для улучшения производительности.  

• Обсуждение рисования графа слева направо.  

• Решение нарисовать граф в три слоя.  

• Упоминание о ребрах и способностях вершин.  

• План разгрузить вершину, чтобы через нее не текло больше потока.  

• Обсуждение выбора вершины для разгрузки.  

• Решение удалить минимальное ребро для разгрузки.  

• Обсуждение минимальной вершины для разгрузки.  

• Упоминание о сумме входящих и выходящих потоков.  

• Подсчет минимума для каждой вершины.  

• Пример расчета для нескольких вершин.  

• Определение минимальной вершины с минимальным потоком.  

• Решение попробовать пихнуть три потока через эту вершину.  

• Объяснение, как поток должен пройти через вершину.  

• Пример пихания потока через вершину.  

• Перебор ребер для распределения потока.  

• Перебор ребер для распределения излишка потока.  

• Объяснение, почему поток не может застрять.  

• Пример распределения потока из вершины в вершину т.  

• Обсуждение необходимости обновления данных.  

• Решение пересчитывать минимум при изменении данных.  

• Подсчет минимума как незначительная операция по сравнению с другими расчетами.  

• Время работы складывается из нескольких этапов.  

• Сначала строится слоистая сеть, затем на ней выполняется работа.  

• Каждый раз находится минимальная вершина и поток от нее.  

• Дельта потока распределяется по ребрам.  

• Если ребро слишком маленькое, оно удаляется из сети.  

• Последнее ребро может остаться ненулевым.  

• Для каждой вершины есть одно ребро, которое не удаляется.  

• Каждое ребро проверяется и удаляется один раз за итерацию.  

• Общее количество ребер, которые проверяются и удаляются, равно n.  

• Авторы алгоритма: Малхо, Рак, Кумар и Махешвар.  

• Обсуждение проблем с единичными потоками.  

• Решение остановиться и углубиться в детали позже.