|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[167] в этом случае картинка осталась той же, но подпись переписана Рис. 25.6 25.6 В пути от s до и выделена часть (s-x), проходящая целиком внутри S, и первая вершина у, лежащая вне S (возможно, х = s или у = и). вершина и с наименьшим значением d[u]; она добавляется к множеству S (в первый раз имеем и = s). В строках 7-8 каждое ребро (и, v), выходящее из и, подвергается релаксации (при этом могут измениться оценка d[v] и предшественник 7г[г>]). Заметим, что в цикле новые вершины в очередь Q не добавляются и что каждая вершина, удаляемая из Q, добавляется к множеству S лишь однажды. Следовательно, число итераций цикла while равно \V\. Поскольку алгоритм Дейкстры всякий раз выбирает для обработки вершины с наименьшей оценкой кратчайшего пути, можно сказать, что он относится к жадным алгоритмам (гл. 17). Покажем, что в данном случае жадная стратегия даёт правильный результат. Теорема 25.10 (Правильность алгоритма Дейкстры) Пусть G = (V, Е) - взвешенный ориентированный граф с неотрицательной весовой функцией w: £->Ки исходной вершиной s. Тогда после применения алгоритма Дейкстры к этому графу для всех вершин и £ V будут выполняться равенства d[u] = S(s, и). Доказательство Проверим, что после любого числа итераций цикла textbfwhile выполнено следующее свойство: (a)для вершин v £ S значение d[v] равно S(s,v), причём существует путь из s в v веса S(s,v), проходящий только по вершинам из S; (b)для вершин v £ Q = V \ S значение d[v] равно наименьшему весу пути из s в v, если учитывать только те пути, в которых все вершины, кроме последней (v), лежат в S (если таких путей нет, d[v] = оо). После первой итерации цикла (когда в S лежит только вершина s и только что проведены релаксации всех рёбер, ведущих из s) это свойство выполнено. Проверим, что оно не нарушится и на следующих итерациях. Пусть и - вершина Q с минимальным значением d[u]. Если d[u] = оо, то не существует пути, в котором все вершины, кроме последней, лежат в S. Значит, из S вообще нельзя никак выйти (оборвав путь в момент выхода, мы получили бы путь с указанным свойством). Пусть теперь d[u] конечно. Тогда существует путь из s в и веса d[u], проходящий по вершинам S до последнего момента (до вершины и). Докажем, что он будет кратчайшим. (Тем самым вершину и можно добавить в S, не нарушая утверждения (а).) Пусть есть какой-то другой путь из s в и (рис. 25.6). Посмотрим на первую вершину этого пути, лежащую вне S; обозначим её у (возможно, у = и). Часть пути от s до у проходит по S до последнего момента, поэтому вес этой части не меньше d[y] (по предположению (а)). Осталось заметить, что вес всего пути не меньше веса его части (веса рёбер неотрицательны) и что d[y] d[u], поскольку в Q вершина и имела наименьшее значение d[u]. Итак, условие (а) останется верным после добавления и к S. Остаётся проверить условие (Ь). Поскольку S увеличилось и стало равным S = S U {и}, путей, не выходящих из S до последнего момента, стало больше, и для соблюдения условия (Ь) значения d[v] для v £ Q надо уменьшать. Это и делается в процессе релаксации. При релаксации ребра (и, v) значение d[v] становится равным Мы знаем, что d[v] есть вес некоторого пути, который ведёт из s в v, оставаясь до последнего шага в S. Второй член d[u] + w(u,v) есть вес некоторого пути, который ведёт из s в и (оставаясь до последнего шага в S), а затем идёт по ребру (и, v). Таким образом существует путь из s в v, который до последнего шага остаётся в S и имеет вес d[v]. Покажем, что любой путь р из s в v, который до последнего шага остаётся в S, имеет вес не меньше d[v]. В самом деле, если х £ S - его предпоследняя вершина, то либо х £ S, и тогда вес пути р не меньше d[v] по индуктивному предположению (а), либо х = и, и тогда вес пути р не меньше d[u] + w(u, v). Мы доказали, что условия (а) и (Ь) остаются верными после любого числа итераций. Значит, они верны и после выхода из цикла; в этот момент S = V и потому d[u] = S(s,u) для любой вершины Из доказанной теоремы и леммы 25.9 немедленно вытекает Следствие 25.11 Пусть G = (V, Е) - взвешенный ориентированный граф с неотрицательной весовой функцией w и исходной вершиной s. Тогда после применения алгоритма Дейкстры к этому графу подграф предшественников Gv будет деревом кратчайших путей с корнем в s. Время работы алгоритма Дейкстры Сначала предположим, что очередь с приоритетами Q = V \ S реализована как массив. При этом стоимость операции Extract-Мш есть 0(V); поскольку алгоритм делает V таких операций, суммарная стоимость всех удалений из очереди есть 0(V2). Что же до стоимости остальных операций, то каждая вершина v £ V добавляется к множеству S только один раз, и каждое ребро из Аф[и] обрабатывается тоже один раз. Общее количество элементов во всех списках смежных вершин есть \Е\; стоимость каждой релаксации есть 0(1). Поэтому стоимость прочих операций есть 0(E), а общая стоимость алгоритма есть 0(V2 + Е). v £ V. Если граф является разреженным, имеет смысл реализовать очередь с помощью (двоичной) кучи (раздел 7.5). Получаемый алгоритм называют иногда модифицированным алгоритмом Дейкстры (modified Dijkstra algorithm). Стоимость операции Extract-Min при такой реализации очереди есть O(lgC), а стоимость построения кучи (строка 3) есть О(С). Присваивание d[v] <- d[u] + w(u, v) при релаксации ребра реализуется с помощью вызова процедуры Decrease-Key(Q, v, d[u] + w(u, v)), имеющего стоимость 0(lgV) (см. упражнение 7.5-4). Количество таких вызовов не превосходит \Е\, так что общая стоимость модифицированного алгоритма Дейкстры есть 0((V + Е) lg V) (если все вершины достижимы из исходной, то граф связен, \Е\ \V\ - 1 и последнюю оценку можно переписать как 0(E\gV)). Если реализовать очередь Q в виде фибоначчиевой кучи (см. главу 21), то можно добиться стоимости 0(V\gV + Е): в самом деле, при этом учётная стоимость каждой из \V\ операций Extract-Мш будет 0(lgV), а учетная стоимость каждой из \Е\ операций Decrease-Key будет 0(1). Кстати, кучи Фибоначчи были изобретены именно в связи с модифицированным алгоритмом Дейкстры: поскольку при его исполнении может потребоваться гораздо больше вызовов процедуры Decrease-Key, чем Extract-Min, хотелось снизить стоимость Decrease-Key. Алгоритм Дейкстры напоминает как алгоритм поиска в ширину (разд. 23.2), так и алгоритм Прима нахождения минимального покрывающего дерева (разд. 24.2). Роль множества S в алгоритме Дейкстры аналогична роли множества черных вершин при поиске в ширину. Сходство алгоритмов Дейкстры и Прима в том, что они оба пользуются очередью с приоритетами при реализации жадной стратегии. Упражнения 25.2-1 Примените алгоритм Дейкстры к графу на рис. 25.2, выбрав за исходную сначала вершину s, а затем вершину у. Следуя образцу рис. 25.5, покажите ход исполнения алгоритма. 25-2.2 Приведите пример графа (с отрицательными весами рёбер), для которого алгоритм Дейкстры даёт неверный ответ. Где в доказательстве теоремы 25.10 используется неотрицательность весовой функции? 25-2.3 Если заменить строку 4 в алгоритме Дейкстры на 4 while Q >1 то число итераций цикла while уменьшится на 1. Будет ли изменённый таким образом алгоритм правильным? 25-2.4 |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||