Разработка и анализ алгоритма Несколько неудачных попыток

Для начала припомним алгоритм Дейкстры для нахождения кратчайшего пути при отсутствии ребер с отрицательной стоимостью. Этот метод вычисляет крат- чайший путь от начальной точки 5 до любого другого узла v в графе, фактически с использованием жадного алгоритма.
Основная идея заключается в построении такого множества S, для которого известен кратчайший путь от 5 к каждому узлу S. Работа начинается с S = {5} (мы знаем, что при отсутствии отрицательных ребер кратчайший путь из 5 в 5 имеет стоимость 0), после чего начинается жадное добавление элементов в множество S. На первом жадном шаге рассматривается ребро минимальной стоимости, выходящее из узла i, то есть min.^Vcsi. Пусть v — узел, для которого достигается минимум. Ключевой факт, заложенный в основу алгоритма Дейкстры, заключается в том, что кратчайшим путем из 5 в v является путь из одного ребра {5, v}. Следовательно, узел v можно немедленно добавить в множество S. Путь {5, v} очевидно является кратчайшим путем к v при отсутствии ребер с отрицательной стоимостью: любой другой путь из 5 в v должен начинаться с ребра, выходящего из 5, стоимость которого по крайней мере не меньше стоимо- сти ребра (5, v).

Если ребра могут иметь отрицательную стоимость, это рассуждение перестает быть истинным. Как подсказывает пример на рис. 6.21, а, путь, начинающийся с ребра с высокой стоимостью, которая компенсируется последующими ребрами с отрицательной стоимостью, может быть «дешевле» пути, начинающегося с ребра низкой стоимости. Следовательно, жадный метод в стиле алгоритма Дейкстры здесь не сработает.



Рис. 6.21. а — с отрицательной стоимостью ребер алгоритм Дейкстры может дать неверный ответ на задачу кратчайшего пути; b — при увеличении стоимости каждого ребра на 3 стоимости всех ребер становятся неотрицательными, но при этом изменяется

кратчайший путь s-t

Другая естественная идея — выполнить предварительное изменение стоимо- стей ребер Сj, прибавив к каждой некоторую большую константу M; иначе говоря, для каждого ребра (i, j)

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка и анализ алгоритма Несколько неудачных попыток:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  3. § 2.ФУНКЦИИ МЕТОДОЛОГИИ В РАЗРАБОТКЕ МЕТОДИК АНАЛИЗА СОЦИАЛЬНЫХ ФАКТОВ
  4. Статья 540. Выполнение обязательства, в котором принимают участие несколько кредиторов или несколько должников
  5. Неудачный брак
  6. Неудачный брак
  7. История суицидальных попыток.
  8. История суицидальных попыток.
  9. КАК ОТКАЗАТЬСЯ ОТ ПОПЫТОК ИЗМЕНИТЬ МУЖЧИНУ
  10. Обратите неудачное выступление в источник своей силы