Поиск кратчайших путей
Одна из проблем, о которой стоит помнить, — содержит ли версия алгоритма, эффективная по затратам памяти, достаточно информации для восстановления самих кратчайших путей?
В случае алгоритма выравнивания последовательностей из предыдущего раздела нам пришлось прибегнуть к хитроумному методу «разделяй и властвуй» для восстановления решения в реализации, эффективной по затратам памяти.
Другими словами, когда значение M [v] сбрасывается до минимума (cvw + M [w]), мы присваиваем first[v] узел w, для которого этот минимум достигается.
Пусть теперь P обозначает направленный «граф указателей», узлами которого являются V, а ребрами — {(v, first[v])}. Ключевой факт заключается в следующем:
(6.27) Если граф указателей P содержит цикл C, то этот цикл должен иметь отрицательную стоимость.
Доказательство. Если first[v] = w в любой момент времени, то должно выполняться условие M [v] ≥ cvw + M [w]. В самом деле, левая и правая стороны равны после обновления, которое задает first[v] равным w; а поскольку M [w] может уменьшаться, это уравнение может превратиться в неравенство.
Пусть v1, v2, …, vk — узлы, входящие в цикл C графа указателей; будем считать, что (vk, v1) — последнее добавляемое ребро.
Теперь рассмотрим значения непосредственно перед последним обновлением. В этот момент M [vi] ≥ + M [vi+1] для всех i = 1, …, k − 1, а также M [vk] > + M [v1], потому что мы собираемся обновить M [vk] и изменить first[vk] на v1.
При суммировании всех этих неравенств значения M [vi] аннулируются, и мы получаем : отрицательный цикл, как и утверждалось.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу