Алгоритмы и структуры данных 5. Алгоритм Штор-Вагнера, Дерево Гомори-Ху, Метод Клейна

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

• Задача является модификацией задачи о поиске максимального потока минимальной стоимости, где стоимость потока может быть отрицательной.  

• Циркуляция - это поток величины ноль, который может быть выгоден, если есть отрицательные ребра и отрицательные циклы.  

• Задача о поиске циркуляции минимальной стоимости может быть решена с помощью задачи о поиске максимального потока минимальной стоимости.  

• Утверждается, что любую циркуляцию можно декомпозировать на не более чем модуль e циклов.  

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

• Вводится понятие минимальной циркуляции и оптимальной циркуляции.  

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

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

• Доказывается, что если в остаточной сети существует циркуляция, то существует циркуляция, стоимость которой меньше стоимости исходной циркуляции.  

• Обсуждается идея доказательства и формальное доказательство.  

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

• Обсуждается возможность использования этого факта для доказательства существования цикла отрицательной стоимости в декомпозиции ф штрих минус ф.  

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

• Задача сводится к задаче о поиске максимального потока минимальной стоимости.  

• Предлагается алгоритм, который добавляет ребра по очереди в граф и гарантирует, что в каждый момент времени в остаточной сети нет циклов отрицательной стоимости.  

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

• Задача имеет практическое применение, например, в анализе биопоследовательностей и поиске подстроек в строке при анализе ДНК.  

• Математики занимаются изучением таких задач, даже получают гранты на это.  

• Вводится понятие потенциала, которое ставит в соответствие каждой вершине число.  

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

• Если ро- это путь, то приведенная стоимость равна обычной стоимости плюс потенциал начала минус потенциал конца.  

• Вводится определение неотрицательного потенциала, который не влияет на приведенную стоимость цикла.  

• Если существует неотрицательный потенциал, то в графе нет циклов отрицательного веса.  

• В видео обсуждается понятие отрицательного потенциала в теории графов и его связь с отрицательными весами ребер.  

• Утверждается, что если в графе есть отрицательный потенциал, то это гарантирует отсутствие циклов отрицательной стоимости.  

• В видео предлагается использовать отрицательный потенциал для поиска кратчайших путей между вершинами в графе.  

• Обсуждается идея поддержания отрицательного потенциала и его изменение при добавлении новых ребер.  

• В видео упоминается печальная оговорка о том, что расстояния в графе могут измениться после добавления ребра.  

• Обсуждается использование потенциалов для нахождения новых расстояний и их перезапись после добавления ребра.  

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

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

• Потенциал используется для определения расстояния между вершинами и для определения стоимости ребер.  

• Если ребро имеет отрицательную стоимость, то его потенциал увеличивается на некоторую константу, чтобы сделать его не отрицательным.  

• Если в графе есть цикл отрицательной стоимости, то он может быть уничтожен, если заменить потенциал.  

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

• Алгоритм может вызывать взрыв мозга, но если понять логику, то он не сложный.  

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

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

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

• Алгоритм Клейна используется для оптимизации и добавления ребер в зависимости от пропускной способности.  

• Алгоритм может быть использован для оптимизации и добавления ребер, но не гарантирует нахождение оптимального решения.  

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

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

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

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

• В видео обсуждается алгоритм Форда-Фалкерсона для нахождения максимального потока в сети.  

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

• В сети без циклов отрицательной стоимости, алгоритм Форда-Фалкерсона ищет максимальный поток минимальной стоимости.  

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

• В случае, если поток не сойдется, алгоритм продолжает искать кратчайший путь.  

• Алгоритм Форда-Фалкерсона является оптимальным для нахождения максимального потока минимальной стоимости в сети без циклов отрицательной стоимости.  

• В сети с циклами отрицательной стоимости, алгоритм может не найти оптимальный поток.  

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

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

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

• Обсуждаются условия задачи и модификации потенциалов для ее решения.  

• В видео обсуждается алгоритм Куна, который используется для поиска совершенного про-сочетания на жестких ребрах.  

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

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

• Вводится понятие дельта - минимум стоимости ребра, который ведет из вершины и в вершину.  

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

• Если ребра сломались, то нужно вычесть дельта из потенциалов.  

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

• Обсуждается идея оптимизации алгоритма, чтобы он работал быстрее.  

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

• Это позволяет сократить время работы алгоритма до куба.  

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

• Это приводит к сокращению времени работы алгоритма и улучшению его эффективности.  

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

• Алгоритм основан на поддержании суммы ребер, которые соединяют вершины, и использовании кучи Фибоначчи для хранения вершин.  

• В видео приводится доказательство утверждения о том, что минимальный разрез между двумя вершинами равен сумме ребер, которые соединяют эти вершины.  

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

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

• Алгоритм начинается с множества вершин, которые не являются критическими.  

• Утверждение состоит в том, что сумма весов ребер разреза больше либо равна сумме весов ребер, соединяющих критическую вершину с остальными.  

• Доказательство проводится по индукции, начиная с первой критической вершины.  

• Алгоритм применяется к графу, чтобы найти минимальный разрез.  

• Если разрез разделяет ст, то он является минимальным.  

• Если ст лежат в одной доле, то можно объединить их в одну вершину и повторить алгоритм.  

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

• Дерево Гамариху существует и может быть построено с использованием алгоритма Дейкстры.