Алгоритмы - построение и анализ (1021735), страница 140
Текст из файла (страница 140)
Алгоритм Дейкстры имеет некоторую схожесть как с поиском в ширину (см. раздел 22.2), так и с алгоритмом Прима, предназначенным для построения минимальных остовных деревьев (см. раздел 23.2). Поиск в ширину он напоминает в том отношении, что множество Е соответствует множеству черных вершин, используемых при поиске в ширину; точно так же, как вершинам множества Я сопоставляются конечные веса кратчайших путей, так и черным вершинам при поиске в ширину сопоставляются правильные расстояния. На алгоритм Прима алгоритм Дейкстры похож в том отношении, что в обоих этих алгоритмах с помощью неубывающей очереди с приоритетами находится "самая легкая" вершина за пределами заданного множества (в алгоритме Дейкстры это множество 5, а в алгоритме Прима — "выращиваемое" дерево), затем эта вершина добавляется в множество, после чего соответствующим образом корректируются и упорядочиваются веса оставшихся за пределами множества вершин.
686 Часть Ч1 Алгоритмы для работы с графами Упражнения 24.3-1. Выполните алгоритм Дейкстры над ориентированным графом, изобра- женным на рис. 24.2. Рассмотрите два варианта задачи, в одном из которых истоком является вершина з, а в другом — вершина а. Используя в качестве образца рис. 24.6, укажите, чему будуг равны значения д и я, и какие вершины будут входить в множество Я после каждой итерации цикла згИ!е. 24.3-2. Приведите простой пример ориентированного графа с отрицательными весами ребер, лля которого алгоритм Дейкстры дает неправильные ответы.
Почему доказательство теоремы 24.6 не годится, если веса ребер могут быть отрицательными? 24.3-3. Предположим, что строка 4 алгоритма Дейкстры изменена следующим образом: 4 тчЫ!е )ф > 1 В результате этого изменения цикл згЬПе выполняется ٠— 1 раз, а не ~Ц раз. Корректен ли предложенный алгоритм? 24.3-4. Пусть дан ориентированный граф С = (К Е), с каждым ребром (и, е) ЕЕ которого связано значение г (и, е), являющееся действительным числом в интервале О < г (и, с) < 1, и представляющее надежность соединительного кабеля между вершиной и и вершиной е. Величина г (и, е) интерпретируется как вероятность того, что в канале, соединяющем вершины и и е, не произойдет сбой; при этом предполагается, что все вероятности независимы.
Сформулируйте эффективный алгоритм, позволяющий найти наиболее надежный путь, соединяющий две заданные вершины. 24.3-5. Пусть С = (Ъ; Е) — взвешенный ориентированный граф с весовой функ- цией ш: Š— (1, 2,..., И'), где И' — некоторое положительное целое число. Ни для каких двух вершин кратчайшие пути, ведущие из истока а в эти вершины, не имеют одинаковые веса. Предположим, что определен невзвешенный ориентированный граф С' = 1~" 0 1г', Е'), в котором каждое ребро (и, е) е Е заменяется и (и, с) последовательными ребрами единичного веса.
Сколько вершин содержит граф С'? Теперь предположим, что в графе С' выполняется поиск в ширину. Покажите, что порядок, в котором вершины множества 1" окрашиваются в черный цвет при поиске в ширину в графе С', совпадает с порядком извлечения вершин множества Ъ' из очереди с приоритетами в строке 5 при выполнении алгоритма Ппкзткл над графом С. 24.3-6. Пусть С = (1г, .Е) — взвешенный ориентированный граф с весовой функ- цией ю: Е -~ (О, 1,..., И~), где И" — некоторое целое неотрицательное число. Модифицируйте алгоритм Дейкстры таким образом, чтобы он 687 Глава 24.
Кратчайшие пути иэ одной вершины находил кратчайшие пути из заданной вершины в в течение времени 0 (И~Ъ'+ Е). 24.3-7. Модифнцируйте алгоритм из упражнения 24.3-6 таким образом, чтобы он выполнялся за время 0 ИУ+ Е) 18 И'). (Указание: сколько различных оценок кратчайших путей для вершин из множества У вЂ” Я может встретиться одновременно?) 24.3-8. Предположим, что имеется взвешенный ориентированный граф С = = (Ъ', Е), в котором веса ребер, исходящих из некоторого истока в, могут быть отрицательными, веса всех других ребер неотрицательные„и циклы с отрицательными весами отсутствуют. Докажите, что в таком графе алгоритм Дейкстры корректно находит кратчайшие пути из истока в.
24.4 Разностные ограничения и кратчайшие пути В главе 29 изучается общая задача линейного программирования, в котором нужно оптимизировать линейную функцию, удовлетворяющую системе линейных неравенств. В этом разделе исследуется частный случай задачи линейного программирования, который сводится к поиску кратчайших путей из одной вершины. Полученную в результате задачу о кратчайших путях из одной вершины можно решить с помощью алгоритма Беллмана-Форда, решив таким образом задачу линейного программирования. Линейное программирование В общей задаче линейного программирования (11пеаг-ргойгаппп)п8 ргоЫеш) задается матрица А размером гп х и, пз-компонентный вектор Ь и и-иэмпонентный вектор с.
Нужно найти состоящий из и элементов вектор х, максимизирующий целевую функцию (оЬ)есйче Йпсйоп) 2 „', с;х;, на которую накладывается гп ограничений Ах < Ь. Несмотря на то, что время работы симплекс-алгоритма, который рассматривается в главе 29, не всегда выражается полиномиальной функцией от размера входных данных, существуют другие алгоритмы линейного программирования с полиномиальным временем работы. Имеется ряд причин, по которым важно понимать, как устроены задачи линейного программирования.
Во-первых, если известно, что данная задача приводится к задаче линейного программирования с полиномиальным размером, то отсюда непосредственно следует, что для такой задачи существует алгоритм с полиномиальным временем работы. Во-вторых, имеется большое количество частных случаев задач линейного программирования, для которых существуют более производительные алгоритмы. Например, 688 в настоящем разделе показано, что задача о кратчайших путях из заданного истока — именно такой частный случай. К другим задачам, которые можно привести к задачам линейного программирования, относятся задача о кратчайшем пути между парой заданных вершин (упражнение 24.4-4) и задача о максимальном потоке (упражнение 26.1-8).
Иногда не имеет значения, какой должна получиться целевая функция; достаточно найти произвольное допустимое реиюеиие (геаз(Ые зо!щюп), т.е. любой вектор х, удовлетворяющий неравенству Ах < Ь, или определить, что допустимых решений не существует. Сосредоточим внимание на таких зидачох суигествоваиил (ГеаяЬ1!йу ргоЫеш).
Системы разностных ограничений В системе разностпых ограничений (зуз!еш ог" ййегелсе солзггппГз) каждая строка в матрице линейного программирования А содержит одно значение 1 и одно значение — 1, а все прочие элементы в этой строке равны О. Другими словами, ограничения, заданные системой неравенств Ах < Ь, представляют собой систему гп разиостпых ограничений (Ййегепсе сопя!та(пгз), содержащих и неизвестных. Каждое ограничение в этой системе — обычное линейное неравенство вида х — х; < Ьь, где1<г,з <пи1<lс<т.
Например, рассмотрим задачу поиска 5-компонентного вектора х = (х;), удовлетворяющего системе неравенств О О О О О -1 ΠΠ— 1 1 О О х1 хз О 1 Π— 1 1 Π— 1 О 1 Π— 1 1 х4 ха 1 -1 1 О О 1 -1 Π— 1 О О О О О О О Часть Ч!. Алгоритмы для работы с графами 689 Эта задача эквивалентна поиску неизвестных величин х4 при 4' = 1,2,...,5, удо- влетворяющих восьми приведенным ниже ограничениям: Одно из решений этой задачи имеет вид х = ( — 5, — 3, О, — 1, — 4), что можно проверить прямой подстановкой. На самом деле эта задача имеет множество решений.
Например, еще одно решение — х' = (О, 2, 5, 4, 1). Эти два решения взаимосвязаны: разность между любой парой соответствующих компонентов векторов х' и х равна 5. Этот факт — не простое совпадение. Лемма 24.8. Пусть х = (хы хз,..., х„) — решение системы разностных ограни- чений Ах < Ь, а 41 — произвольная константа. Тогда х+Н = (х4+4(, ха+а,..., х„+ + 4() — тоже решение системы Ах < Ь. Доказаа4еиьса4во. Для каждой пары переменных х4 и ху можно записать соотно- шение (х4 + Ы) — (х + И) = х4 — х .
Таким образом, если вектор х удовлетворяет системе неравенств Ах < Ь, то ей удовлетворяет и вектор х + 41. Системы разностных ограничений возникают в самых разнообразных приложениях. Например, неизвестные величины х4 могут обозначать моменты времени, в которые происходят события. Каждое ограничение можно рассматривать как требование, при котором между двумя событиями должно пройти некоторое время, не меньшее (или не большее) некоторой заданной величины.
Возможно, эти события — задания, которые необходимо выполнить в процессе сборки некоторого изделия. Например, если в момент времени хз применяется клей, время фиксации которого — 2 часа, а деталь будет устанавливаться в момент времени хз, то необхолимо наложить огРаничение хз > х> + 2 или, что эквивалентно, хз — хз < — 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
