Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 155
Текст из файла (страница 155)
24.3.8 Пусть С = (У. Е) — взвешенный ориентированный граф с весовой функцией щ: Š— > (О, 1,..., И'), где И' — некоторое целое неотрицательное число. Модифицируйте алгоритм Дейкстры так, чтобы он вычислял кратчайшие пути из заданной вершины а за время 0(И'У + Е). 24.3.9 Модифицируйте алгоритм из упр. 24.3.8 таким образом, чтобы он выполнялся за время 0((У + Е) 18 И'). (Указалае7 сколько различных оценок кратчайших путей для вершин из множества У вЂ” Я может встретиться одновременно?) 24.3.10 Предположим, что имеется взвешенный ориентированный граф С = (У, Е), в котором веса ребер, исходящих из некоторого истока а, могут быть отрицательными, веса всех других ребер неотрицательные, а циклы с отрицательными весами отсутствуют. Докажите, что в таком графе алгоритм Дейкстры корректно находит кратчайшие пути из истока ж 24.4.
Разностные ограничения и кратчайшие пути В главе 29 изучается общая задача линейного программирования, в которой нужно оптимизировать линейную функцию, удовлетворяющую системе линейных неравенств. В этом разделе исследуется частный случай задачи линейногс программирования, который сводится к поиску кратчайших путей из одной вер- 703 Глава 24. Кратчайшие луши ез одной вершины шины. Полученную в результате задачу о кратчайших путях из одной вершины можно решить с помощью алгоритма Беллмана — Форда, решив таким образом задачу линейного программирования. Линейное программирование В обобщенной задаче линейного арограммнроаання (!!пеаг-ргойгапцшлд ргоЫеш) задаются матрица А размером гп х и, из-компонентный вектор Ь и и- компонентный вектор с.
Нужно найти состоящий из и элементов вектор х, максимизнрующий целевую функцию (о!зесг1че йшсз!оп) 2,. с,хо на которую наклвдывается гп ограничений Ах < Ь. Несмотря на то что время работы симплекс-алгоритма, который рассматривается в главе 29, не всегда является полиномиальной функцией от размера входных данных, существуют другие алгоритмы линейного программирования с полиномиальным временем работы. Имеется несколько причин, по которым важно понимать, как устроены задачи линейного программирования. Во-первых, если известно, что некоторая задача приводится к задаче линейного программирования с полиномиальным размером, то отсюда непосредственно следует, что для такой задачи существует алгоритм с полиномиальным временем работы.
Во-вторых, имеется большое количество частных случаев задач линейного программирования, для которых существуют более производительные алгоритмы. Например, задача о кратчайшем пути между парой заданных вершин (упр. 24.4.4) и задача о максимальном потоке (упр. 26.1.5) являются частными случаями задачи линейного программирования. Иногда не имеет значения, какой вид имеет целевая функция; достаточно найти произвольное допустимое решение ((еав1Ые во!цйоп), т.е. любой вектор х, удовлетворяющий неравенству Ах < Ь, или убедиться, что допустимых решений не существует. Сосредоточим внимание на таких задачах сугцествоаання (геав!ЬВ1!у ргоЫеш).
Системы разиостных ограничений В системе разностнык ограннченнй (вувГеш о! б!(1егепсе сопвзгашгв) каждая строка в матрице линейного программирования А содержит одно значение 1 и одно значение — 1, а все прочие элементы в этой строке равны О.
Другими словами, ограничения, заданные системой неравенств Ах < Ь, представляют собой систему гп разностнык ограниченой (Ййегепсе сопя!та!пГв), содержащих и неизвестных. Каждое ограничение в этой системе — обычное линейное неравенство вида хз х <Ь| где 1 < з, 2 < и, ( ф 2' и 1 < й < гп. Часть 17. алгоравмы дм работы с графама Рассмотрим, например, задачу поиска 5-компонентного вектора х = (х,), удовлетворяющего системе неравенств х1 Х2 хз < х4 хь Эта задача эквивалентна поискУ неизвестных величин хм хз, хз,х4, хз, Удовле- творяющих восьми разностным ограничениям: Одним из решений этой задачи является х = ( — 5, — 3, О, — 1, — 4), что можно проверить прямой подстановкой.
На самом деле эта задача имеет множество решений. Например, еще одно решение — х' = (О, 2, 5, 4, 1). Эти два решения взаимосвязаны: разность между любой парой соответствующих компонентов векторов х' и х равна 5. Этот факт — не простое совпадение. Лемма 24,В Пусть х = (хмхз,...,х„) является решением системы разностных ограниче- ний Ах < Ь, а д — произвольная константа. Тогда х+с( = (х1+с(, хз+с(,..., х„+И) также является решением системы Ах < Ь. Двказвшельсшвв.
Для каждой пары переменных х; и х можно записать соотношение (х; + с() — (х + с() = х; — хг. Таким образом, если вектор х удовлетворяет системе неравенств Ах < 5, то ей удовлетворяет и вектор х + с(. Системы разностных ограничений возникают в самых разнообразных приложениях. Например, неизвестные величины х; могут обозначать моменты времени, в которые происходят события. Каждое ограничение можно рассматривать как требование, при котором между двумя событиями должно пройти некоторое время, не меньшее (или не большее) некоторой заданной величины. Возмоясно. этн события — задания, которые необходимо выполнить в процессе сборки нею.= 1 — 1 О 1 О О О 1 Π— 1 О 1 — 1 ΠΠΠΠ— 1 ΠΠ— 1 ΠΠΠΠΠΠ— 1 О -1 О О 1 О 1 О О 1 -1 1 хз — хз< О, х1 — хь < -1, х2 хь< хз — х1< 5, х4 хз< 4, х4 — хз < — 1, хь — хз < -3, хь — х4 < — 3.
Π— 1 1 5 4 -1 — 3 -3 (24.3) (24.4) (24.5) (24.6) (24Л) (24.8) (24.9) (24.10) 705 Глава 24. Краычайыие арии ил адиай вврыииы торого изделия. Например, если в момент времени х1 применяется клей, время фиксации которого — 2 часа, а деталь будет устанавливаться в момент времени хг, то необходимо наложить ограничение хг > х| + 2, или, что эквивалентно, х1 — хг < — 2.
При другой технологии может потребоваться, чтобы деталь устанавливалась после применения клея, но не позже, чем когда он "схватится" наполовину. В этом случае получаем пару ограничений хг > х5 и хг < х1 + 1, нли, что эквивалентно,х1 — хг < 0 и хг — х1 < 1. Графы ограничений Системы разностных ограничений можно рассматривать с точки зрения теории графов. Идея заключается в том, что в системе разностных ограничений Ах < Ь матрицу задачи линейного программирования А размером т х и можно рассматривать как транспонированную матрицу инцидентности (см.
упр. 22.1.7) графа с и вершинами и т ребрами. Каждая вершина е, графа при 1 = 1, 2,..., п соответствует одной из и неизвестных переменных х,. Каждое ориентированное ребро графа соответствует одному из т независимых неравенств, в которое входят две неизвестные величины. Если выражаться формальным языком, то заданной системе разностных ограничений Ах < Ь сопоставляется граф ограничений (сопзПашг йгарй), представляюший собой взвешенный ориентированный граф С = (17, Е), в котором Е = ((ип о ): х — х, < Ьь является ограничением) 15((оо о1) (юо,ог) (оо оз) (оо ои)) .
Вскоре станет понятно, что дополнительная вершина со вводится для того, чтобы в графе имелась вершина, из которой гарантированно была достижима любая другая вершина. Таким образом, множество К состоит из вершин ип каждая из которых соответствует неизвестной х„и дополнительной вершины ео. В множестве ребер Е на каждое разностное ограничение приходится по одному ребру; кроме того, в это множество вхсдят ребра (ео,ли), каждое из которых соответствует неизвестной величине х,. Если накладывается разностное ограничение х. — х, < Ьь, это означает, что вес ребра (ип о ) равен ш(ю,,оэ) = Ьь.
Вес каждого ребра, исходящего из вершины оо, равен О. На рис. 24.8 приведен граф ограничений для системы разностных ограничений (24.3)-(24.10). Из приведенной ниже теоремы видно, что решение системы разностных ограничений можно найти пугем определения весов кратчайших путей в соответствуюШем графе ограничений. Теореме 24. 9 Пусть С = (17, Е) представляет собой граф ограничений, соответствующий заданной системе разностных ограничений Ах < Ь.
Если граф С не содержит циклов Чаешь Гй Алгоритмы длл раоомы с графами Рнс. 24.8. Граф ограничений длл системы раэносппат ограничений (24.3К24.10). В канвой вершине ог указано значение 6(ео, о,). Одно допустимое решение этой системы имеет вид х = ( — о, -3, О, — 1, -4). с отрицательным весом, то вектор х = (б(ио, иг), б(ио из) . б(ио и )) (24.11) является допустимым решением системы. Если граф г содержит циклы с отрицательным весом, то допустимых решений не существует.