Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 156
Текст из файла (страница 156)
Доднзагинаьснгва. Сначала покажем, что если граф ограничений не содержит циклов с отрицательным весом, то уравнение (24.11) дает допустимое решение. Рассмотрим произвольное ребро (и;,и ) е Е. Согласно неравенству треугольника выполняется неравенство б(ио,и ) < б(ио,ьт) + иг(иг,и ) или, что то же самое, б(ио,иу) — б(ио,и,) < ш(и;,иу).
Таким образом, полагая х, = б(ио,и;) и х = б(ес, иу), мы удовлетворяем разностное ограничение х — х; < иг(и;, и ), соответствующее ребру (и;, и ). Теперь покажем, что если граф ограничений содержит цикл с отрицательным весом, то система разностных ограничений не имеет допустимых решений. Не теряя общности, предположим, что цикл с отрицательным весом — это цикл с = (и1, из,..., иь), где и1 = иа.
(Вершина ио не может принадлежать циклу с, потому что в нее не входит ни одно ребро.) Цикл с соответствует приведенной ниже системе ограничений: хз — хг < ш(им из), хз — хз < и(из,из), хь 1 — хь 2 < иг(иа з,иь 1), ха — хь 1 < иг(иа 1, иь) . Предположим, что существует решение х, удовлетворяющее всем этим и неравенствам. Это решение должно также удовлетворять неравенству, полученномэ Глава 24. Кратнайише нуши ив одной вершины 701 в результате суммирования всех перечисленных й неравенств. Если просуммировать все левые части, то каждая неизвестная х; один раз войдет со знаком "+" и один раз — со знаком "—" (напомним, что из равенства о2 = еь следует равенство хг = хь).
Это означает, что сумма всех левых частей равна О. Сумма правых частей равна ви(с), откуда получается неравенство О < во(с). Однако, поскольку с — цикл с отрицательным весом, выполняется неравенство во(с) < О, что приводит нас к противоречию О < ю(с) < О. Упражнения 24.4 1 Найдите допустимое решение приведенной ниже системы раэностных ограниче- ний или покажите, что решений не существует: Х1 — Х2( 1 хг — хй < -4 < 2, < 7, Х2 ХЗ Х2 — Х5 Х2 — Ха< 5, хз — ха < 10 х4 — хз( 2, хз — Х2 ( -1, х5 — Х4( 3, ха — хз < — 8. Решение систем разностных ограничений Теорема 24.9 говорит о том, что с помощью алгоритма Беллмана-Форда можно репппь систему линейных ограничений. Поскольку в графе ограничений сушествуют ребра, ведущие из вершины ео во все другие вершины, любой цикл с отрицательным весом в графе ограничений достижим из вершины ео.
Если алгоритм Беллмана-Форда возвращает значение типе, веса кратчайших путей образуют допустимое решение этой системы. В примере, проиллюстрированном на рис. 24.8, веса кратчайших путей образуют допустимое решение х = ( — 5, — 3, О, — 1, — 4), и согласно лемме 24.8 х = (д — 5,Н вЂ” З,й,е1 — 1,Н вЂ” 4), где И вЂ” произвольная константа, также является допустимым решением. Если ашоритм БеллманаФорда возвращает значение рльзв, то система разностных ограничений решений не имеет. Система разностных ограничений с т ограничениями и и неизвестными порождает граф, состояший из и + 1 вершин и и + т ребер.
Таким образом, с помощью алгоритма Беллмана-Форда такую систему можно решить за время Оип + 1ип+ т)) = 0(пз + пгп). В упр. 24.4.5 предлагается модифицировать этот алгоритм таким образом, чтобы он выполнялся за время 0(птп), даже если т намного меньше, чем и. Уагыь И. Алгоритмы длл раоомы г графами 24.4.2 Найдите допустимое решение приведенной ниже системы разностных ограниче- ний или покажите„что решений не существует: Хг — Хз( 4 хг — ха< 5, ХЗ-Х4 < -6, Х4 — Ха < 10 хь — хз < — 4, ХЬ Х4 < — 8. 24.4.3 Может ли вес любого кратчайшего пути, исходяшего из новой вершины со в графе ограничений, быть положительным? Объясните свой ответ.
24.4.4 Сформулируйте задачу о кратчайшем пути между парой заданных вершин в виде задачи линейного программирования. 24.4.5 Покажите, как можно модифицировать алгоритм Беллмана-Форда, чтобы он поз- волял решить систему разностных ограничений с пг неравенствами и п неизвест- ными за время 0(пгп). 24,4. б Предположим, что в дополнение к системе разностных ограничений накладыва- ются ограничения-равенства (ейпайгу сопзпа1пгз), имеющие вид хг = х. + бь. Покажите, как адаптировать алгоритм Беллмана-Форда, чтобы с его помощью можно было решать системы ограничений такого вида.
24.4. 7 Покажите, как можно решить систему разностных ограничений с помощью алго- ритма, подобного алгоритму Беллмана-Форда, который обрабатывает граф огра- ничений, не содержащий дополнительную вершину со. 24.4.В * Пусть Ах < 6 — система гп разностных ограничений с п неизвестными. Покажите, что при обработке графа ограничений, соответствующего этой системе, алгоритм Беллмана-Форда максимизирует сумму 2 '," г хь где вектор х удовлетворяет системе Ах < 6, а все компоненты х; — неравенству х, < О. хз — хз Х4 Хг Х4 ХЗ < 1, < 3, < 5, Глава гх Кратчайшие нута из одной вершины 709 24.4. У * Покажите, что в процессе обработки графа ограничений„соответствующего системе разностных ограничений Ах < Ь, алгоритм Беллмана — Форда минимизирует величину (шах (хв) — ппп (х )), где х; — компоненты вектора х, удовлетворяющего системе Ах < Ь. Объясните, как можно использовать этот факт, если алгоритм применяется для составления расписания некоторых конструкторских работ.
24.4.10 Предположим, что каждая строка матрицы А задачи линейного программирования Ах < Ь соответствует либо разностному ограничению, либо ограничению на одну переменную вида хв < Ьь или — х, < Ьь. Покажите, как адаптировать алгоритм Беллмана-Форда для решения систем ограничений такого вида. 24.4. 11 Разработайте эффективный алгоритм решения системы разностных ограничений Ах < Ь, в которой все элементы вектора Ь являются действительными числами, а все неизвестные х, должны быть целыми числами.
24.4.12 * Разработайте эффективный алгоритм решения системы разностных ограничений Ах < Ь, в которой все элементы вектора Ь являются действительными числами, а определенное число неизвестных х; (не обязательно все) должно быть целыми числами. 24.5. Доказательства свойств кратчайших путей Корректность доказательств, которые используются в этой главе, основана на неравенстве треугольника, свойстве верхней границы, свойстве отсутствия пути, свойстве сходимости, свойстве ослабления пути и свойстве подграфа пред- шествования. В начале главы эти свойства сформулированы без доказательств.
В настоящем разделе мы их докажем. Неравенство треупиьника При изучении поиска в ширину (раздел 22.2) в лемме 22А доказано простое свойство, которым обладают кратчайшие расстояния в невзвешенных графах. Неравенство треугольника обобщает это свойство для взвешенных графов. Ламма 24.10 (Неравенство треугольника) Пусть С = (У, Е) представляет собой взвешенный ориентированный граф с весовой функцией ш: Е -+ К и истоком в. Тогда для всех ребер (и, о) е Е выполняется неравенство б(в, о) < б(в, и) + ео(и, о) . Часть П. Алгоритмы длл работы с грифами 7!О Влияние оелабленяя на оценки кратчайшего пути Приведенная ниже группа лемм описывает, какому воздействию подвергаются оценки кратчайшего пути, когда выполняется последовательность шагов ослабления ребер взвешенного ориентированного графа, инициализированного процедурой 1ьцт~лы2к-бичи.к-бопкск.
Лемма 24.11 (Свойство верхней границы) Пусть С = ($; Е) представляет собой взвешенный ориентированный граф с весовой функцией ю: Š— ~ К. Пусть л е 17 — исток, а граф инициализирован процедурой 1ьпт~лш2к-Япчськ-Яопксп(С, в). Тогда для всех вершин и е 17 выполняется неравенство и. И > б(в,и), и этот инвариант поддерживается в ходе всей последовательности шагов ослабления ребер графа С. Более того, как только атрибут и. Н достигает своей нижней границы б(в,и), в дальнейшем он не изменяется. Доказашельсшво. Докажем инвариант и. Н > б(в, и) для всех вершин и е 17, воспользовавшись индукцией по числу шагов ослабления. В качестве базиса индукции используем неравенство и.И > б(в,и), которое очевидным образом истинно непосредственно после инициализации„ поскольку из и.Н = со вытекает и.б > б(л,и) для всех и й Ъ' — (л) и поскольку ж И = О > б(в, в) (заметим, что б(в, в) = — оо, если в находится в цикле с отрицательным весом, и Π— в противном случае).
В качестве шага индукции рассмотрим ослабление ребра (и, и). Согласно гипотезе индукции для всех вершин х е Ъ' перед ослаблением выполняется неравенство х. с( > б(в, х). Единственное значение 4, которое может измениться — это значение и. Н. Если оно изменяется, мы имеем и. с( = и. 4 + ю(и, и) > б(в, и) + ю(и, и) > б(в,и) (согласно гипотезе индукции) (согласно неравенству треугольника), так что инвариант сохраняется.
Чтобы увидеть, что значение и.б не будет изменяться после того, как станет справедливым соотношение и.с( = б(в,и), заметим, что по достижении своей нижней границы это значение больше не сможет уменьшаться, поскольку, как уже было показано, и. Н > б(л,и). Оно также не может возрастать, поскольлу ослабление не увеличивает значений гь Доказаигельсшво.
Предположим, что р представляет собой кратчайший путь из истока в в вершину и. Тогда вес этого пути р не превышает веса любого другого пути из вершины в в вершину и. В частности, вес пути р не превышает веса пути, состоящего из кратчайшего пути из истока в в вершину и и ребра (и, и). В упр. 24.5.3 предлагается рассмотреть случай, когда не существует кратчайшего пути из вершины л в вершину и.
Глава 74. Кратчайшие нута аз одной аершаны 7П Следствие 24.12 (Свойство отсутствия пути) Предположим, что во взвешенном ориентированном графе С = ($7, Е) с весовой функцией ю: Š— 1 И отсутствуют пути, соединяющие исток в Е Ъ' с данной вершиной е б 17. Тогда после инициализации графа процедурой 11ч1т! Аыее-Б1хпееБо!1ксе(С, в) мы имеем е. а = б(в,е) = оо, и это равенство сохраняется в качестве инварианта в ходе выполнения произвольной последовательности шатов ослабления ребер графа С.
Доказательства Согласно свойству верхней границы мы всегда имеем оо = б(в, е) < е, Н, и, таким образом, е. а' = оо = б(в, о). Лемма 24.13 Пусть С = (17, Е) представляет собой взвешенный ориентированный граф с ве- совой функцией ю: Š— ! К и пусть (и,е) Е Е. Тогда непосредственно по- сле ослабления ребра (и,е) путем выполнения Кеелх(и,е, ю) мы имеем е. Ы < и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
