|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[164] Рис. 25.1 25.1 Ориентированный граф с рёбрами отрицательного веса. У каждой вершины указан вес кратчайшего пути из s в эту вершину. Поскольку вершины ей/ образуют цикл отрицательного веса, достижимый из вершины s, веса кратчайших путей в каждую из этих вершин равны -оо. Сделав несколько циклов, можно пойти в д, так что вес кратчайшего пути в д также равен - оо. Вершины h, г и j недостижимы из s, так что (хоть они и лежат на цикле отрицательного веса), вес кратчайшего пути в эти вершины есть оо. иска кратчайших путей (например, алгоритм Дейкстры) используют это и применимы лишь для графов с неотрицательными весами. Другие (например, алгоритм Беллмана-Форда) допускают рёбра отрицательного веса и даже дают верный результат, если из исходной вершины нельзя дойти до цикла отрицательного веса. Обычно алгоритм сообщает, если такой цикл отрицательного веса обнаружен. Представление кратчайших путей в алгоритме Часто требуется не просто подсчитать веса кратчайших путей, но и найти сами эти пути. Мы будем использовать для их представления тот же приём, что и в деревьях поиска в ширину в разд. 23.2. Именно, пусть G = (V, Е) - заданный граф. Для каждой вершины v G V мы будем помнить её предшественника (predecessor) ir[v]. Предшественник вершины - это либо другая вершина (указатель на неё), либо nil. По завершении работы алгоритмов, рассматриваемых в этой главе, цепочка предшественников, начинающаяся с произвольной вершины v, будет представлять собой кратчайший путь из s в v (в обратном порядке), так что, если ir[v] ф nil, процедура Print-Path(G, s, v) из разд. 23.2 напечатает кратчайший путь из s в v. В процессе работы алгоритмов цепочки, получаемые итерациями 7г, не обязательно будут кратчайшими путями, но всё равно можно рассмотреть ориентированный подграф предшествования (predecessor subgraph) Gv = (VV,EV), определённый так: вершины Gv - это те вершины G, у которых предшественник отличен от nil, плюс исходная вершина: Vw = { v е V : tt[v] ф nil } U {s}. Рёбра Gv - это стрелки, указывающие из ir[v] ф nil в v. Ev = {(tt[v],v) е Е : v eVv\{s}}. Мы докажем, что по окончании работы наших алгоритмов граф Gv будет «деревом кратчайших путей» - деревом с корнем s, содержащим кратчайшие пути из s во все достижимые из s вершины. Деревья кратчайших путей аналогичны деревьям поиска в ширину из разд. 23.2, с той разницей, что на сей раз кратчайшими объявляются пути с наименьшим весом, а не наименьшим числом ребер. Рис. 25.2 25.2 (а) Взвешенный ориентированный граф; в вершинах указаны веса кратчайших путей из s. (б) Серые рёбра образуют дерево кратчайших путей с корнем s. (в) Другое дерево кратчайших путей с тем же корнем. Точное определение выглядит так. Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w: Е -> Ж. Предположим, что G не имеет циклов отрицательного веса, достижимых из исходной вершины s, так что все кратчайшие пути из s корректно определены. По определению, дерево кратчайших путей (shorted-paths tree) с корнем в s есть ориентированный подграф G = (V, Е), где V С V и Е С Е, для которого: 1.V - множество вершин, достижимых из вершины v; 2.G является деревом с корнем s; 3.для каждого v £ V путь из s в v в графе G является кратчайшим путем из s в v в графе G. Ни кратчайшие пути, ни деревья кратчайших путей не обязаны быть единственными. На рис. 25.2 изображен взвешенный ориентированный граф и два различных дерева кратчайших путей с общим корнем. План главы Все алгоритмы для поиска кратчайших путей, рассматриваемые в этой главе, основаны на технике, известной под названием релаксация (relaxation). В разд. 25.1 мы рассматриваем общие свойства кратчайших путей, а затем доказываем ряд важных фактов про релаксацию. Алгоритм Дейкстры, решающий задачу о кратчайших путях из одной вершины для случая неотрицательных весов, разобран в разд. 25.2. Разд. 25.3 посвящен алгоритму Беллмана-Форда, применимому и в том случае, когда рёбра могут иметь отрицательный вес. (Если граф содержит цикл отрицательного веса, достижимый из исходной вершины, алгоритм Беллмана-Форда сообщает об этом.) В разд. 25.4 рассматривается алгоритм для нахождения кратчайших путей в ациклических графах, работающий за линейное время. Наконец, в разд. 25.5 мы показываем, как применить алгоритм Беллмана-Форда к решению одного специального случая задачи линейного программирования. При работе с символами оо и -оо мы будем придерживаться следующих соглашений. Если а ф -оо, то будем считать, что а + оо = оо + а = оо; аналогично, если а ф оо, то а+( -оо) = ( - оо)+а = - оо. 25.1. Кратчайшие пути и релаксация В этом разделе описываются свойства кратчайших путей и объясняется общий приём, используемый всеми алгоритмами этой главы и называемый «релаксацией». Он состоит, грубо говоря, в постепенном уточнении верхней оценки на вес кратчайшего пути в данную вершину - пока неравенство не превратится в равенство. При первом чтении вы можете разобрать только формулировки результатов (обратите особое внимание на лемму 25.7; леммы 25.8 и 25.9 при первом чтении можно пропустить), после чего перейти к алгоритмам разд. 25.2 и 25.3. Свойство оптимальности для подзадач Любая часть кратчайшего пути сама есть кратчайший путь. Это значит, что задача о кратчайших путях обладает свойством оптимальности для подзадач - признак того, что к ней может быть применимо динамическое программирование (глава 16) или жадный алгоритм (глава 17). И действительно, алгоритм Дейкстры является жадным алгоритмом, а алгоритм Флойда-Уоршолла для нахождения кратчайших путей между всеми парами вершин (глава 26) основан на динамическом программировании. Следующая лемма и ее следствие уточняют, в чем конкретно состоит свойство оптимальности для подзадач в задаче о кратчайших путях. Лемма 25.1 (Отрезки кратчайших путей являются кратчайши- Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w: Е -> Ж. Если р = (v\, v2, , vk) - кратчайший путь из vi в vk и 1 г j к, то рг] = (vi,vi+1,...,Vj) есть кратчайший путь из V{ в Vj. Доказательство Если путь pij не кратчайший, то, заменяя в пути р участок от Vi до Vj на более короткий путь из иг- в Vj, мы уменьшим вес пути из pi в рк - противоречие. (Здесь «более короткий» означает «с меньшим весом».) Следствие из доказанной леммы обобщает лемму 23.1. Следствие 25.2 Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w: Е -> R. Рассммотрим кратчайший путь р из s в v. Пусть и -т- v - последнее ребро этого пути (р есть s и -> v). Тогда S(s, v) = S(s, и) + w(u, v). Доказательство По лемме 25.1 путь р является кратчайшим, так что S(s,v) = w(p) + w(u, v) = S(s, и) + w(u, v). Следующая лемма проста, но полезна. Лемма 25.3 Пусть G = (V, Е) - взвешенный ориентированный |
Среды: 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 | ||