Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 142
Текст из файла (страница 142)
Другими словами, ограничения, заданные системой неравенств Ах < Ь, представляют собой систему гп разиостпых ограничений (Ййегепсе сопя!та(пгз), содержащих и неизвестных. Каждое ограничение в этой системе — обычное линейное неравенство вида х — х; < Ьь, где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. При другой технологии может потребоваться, чтобы деталь устанавливалась после применения клея, но не позже, чем когда он "схватится" наполовину.
В этом случае получаем пару ограничений хз > хз и хз < хг + 1, или, что эквивалентно, х] хз(~Оихз — хг(~1, Глава 24. Кратчайшие пути из одной вершины х4 — хз < О, Х4 — хз < — 1, Х2 — Х5 ~ К1, хз — х4 <5, х4 хз <4, х4 — хз > — 1> Х5 — хз < -3, Х5 Х4 ~ (3 (24.3) (24.4) (24.5) (24.6) (24.7) (24.8) (24.9) (24. 10) Часть»' >. Алгоритмы для работы с графами 690 Графы ограничений Системы разностных ограничений удобно рассматривать с точки зрения теории графов. Идея заключается в том, что в системе разностных ограничений Ах < Ь матрицу задачи линейного программирования А размерами т х и можно рассматривать как транспонированную матрицу инцндентности (см.
упражнение 22.1-7) графа с и вершинами и т ребрами. Каждая вершина»; графа пря г = 1,2,..., и соответствует одной из и неизвестных переменных з;. Каждое ориентированное ребро графа соответствует одному из гп независимых неравенств, в которое входят две неизвестных величины. Если выражаться формальным языком, то заданной системе разностных ограничений Ат < Ь сопоставляется граф ограничений (сопзгга1пг йгарЬ), представляющий собой взвешенный ориентированный граф С = ()г, Е), в котором Е = ((о,,»у): ху — х; < Ьь) 0 ((»о е1) >(ио,оз),,(г>о,~п)).
Вскоре станет понятно, что дополнительная вершина ио вводится для того, чтобы нз нее гарантированно была достижима любая другая вершина. Таким образом, множество Ъ' состоит нз вершин»>ь каждая из которых соответствует неизвестной х;, н дополнительной вершины оо. В множестве ребер Е на каждое разностное ограничение приходится по одному ребру; кроме того, в это множество входят ребра (г>о, ьч), каждое из которых соответствует неизвестной величине х;.
Если накладывается разностное ограничение х — х; < Ьы это означает, что вес ребра (>х, е ) равен и (сн о,) = Ьы Вес каждого ребра, исходящего из вершины еа, равен О. На рис. 24.8 приведен граф ограничений для системы разносных ограничений (24.3)-(24.10). В каждой вершине сч указано значение д (»о, сч). Допустимое решение этой системы имеет вид х = ( — 5, — 3, О, — 1, — 4).
Из приведенной ниже теоремы видно, что решение системы разностных ограничений сводится к определению веса кратчайшего пути в соответствующем графе ограничений. Теорема 24.9. Пусть С = (У,Е) — граф ограничений, соответствующий заданной системе разностных ограничений Ах < Ь. Если граф С не содержит циклов с отрицательным весом, то вектор х = (д (оо о1) > б (ео > ог)» б (ео > гь,) ) (24.11) является допустимым решением системы. Если граф С содержит циклы с отри- цательным весом, то допустимых решений не существует.
691 Глава 24. Кратчайшие пути из одной вершины ,л"7- 'ч:, 1', -,;1 о Рис. 24.8. Граф ограничений, соответствующих системе рвзиостиых ограничений (24.3К24,10) Доказалгельслгво. Сначала покажем, что если граф ограничений не содержит циклов с отрицательным весом, то уравнение (24.11) определяет допустимое решение. Рассмотрим произвольное ребро (о;, о ) е Е.
Согласно неравенству треугольника, выполняется неравенство о (оо, о;) < б (оо, ог) + ю (о;, о;) или, что то же самое, 6(оо,о ) — б(оо,ог) < ю(гч,о.). Таким образом, полагая хг = б(оо,ог) и х = о(оо,о.), мы удовлетворяем разностное ограничение х — х; < ю(о;,о ), соответствующее ребру (о;, о;). Теперь покажем, что если граф ограничений содержит цикл с отрицательным весом, то система разностных ограничений не имеет допустимых решений.
Не теряя общности, предположим, что цикл с отрицательным весом — это цикл с = = (ог,ог,..., оь), где о1 = оы (Вершина оо не может принадлежать циклу с, потому что в нее не входит ни одно ребро.) Цикл с соответствует приведенной ниже системе ограничений: Х2 — Х1 < Ю (О1, О2), хз — хг < ю (ог,оз), хь 1 — хь 2 < ю(оь г,оь 1), хь — хь 1 < ю(ог, г,оь) . Предположим, существует решение х, удовлетворяющее всем этим )с неравенствам. Это решение должно также удовлетворять неравенству, полученному в результате суммирования всех перечисленных к неравенств.
Если просуммировать все левые части, то каждая неизвестная хг один раз войдет со знаком "+" и один раз — со знаком "—" (напомним, что из равенства о1 = оь следует равенство Часть Ч1. Алгоритмы для работы с графами 692 х| = хь). Это означает, что сумма всех левых частей равна О. Сумма правых частей равна ы (с), откуда получается неравенство 0 < и (с). Однако посюльку с— цикл с отрицательным весом, то выполняется неравенство и (с) < О, что приводит нас к противоречию 0 < и (с) < О. И Решение систем разностных ограничений Теорема 24.9 говорит о том, что с помощью алгоритма Беллмана-Форда можно решить систему линейных ограничений. Посюльку в графе ограничений существуют ребра, ведущие из вершины со во все другие вершины, любой цикл с отрицательным весом в графе ограничений достижим из вершины оо. Если алгоритм Беллмана-Форда возвращает значение ткОн, веса кратчайших путей образуют допустимое решение этой системы.
В примере, проиллюстрированном на рис. 24.8, веса кратчайших путей образуют допустимое решение х = ( — 5, — 3,0, — 1, — 4), и, согласно лемме 24.8, х = (Н вЂ” 5, Н вЂ” 3, Н, д — 1, Н вЂ” 4), где с1 — произвольная константа, — тоже является допустимым решением. Если алгоритм БеллманаФорда возвращает значение ГАезе, то система разностных ограничений не имеет решений.
Система разностных ограничений с т ограничениями и и неизвестными порождает граф, состоящий из п+ 1 вершин и и+ т ребер. Таким образом, с помощью алгоритма Беллмана-Форда такую систему можно решить в течение времени О Кп+ 1) (и+ гп)) = О (п~ + пт).
В упражнении 24 4 5 предлагается модифицировать этот алгоритм таким образом, чтобы он выполнялся в течение времени О (пгп), даже если гп намного меньше„чем и. Упражнения 24.4-1. Найдите допустимое решение приведенной ниже системы разностных ограничений или определите, что решений не существует: Х1- Х2 Х1 Х4 Х2 ХЗ Х2 — Хб Х2 Хб ХЗ вЂ” Хб Х4 Х2 Хб — Х1 Хб — Х4 Хб хз < 1, < — 4, < 2, < 7, < 5, < 10, < 2, < -1, < 3, < — 8. Глава 24. Кратчайшие пути из одной вершины 693 24.4-2. Найдите допустимое решение приведенной ниже системы разностных ограничений или определите, что решений не существует: Х1 — хг < 4, Х1 — хз < 5, < — 6, хг х4 хз — хг Х4 Хз Х4 — ХЗ Х4 Хь Ха Хз < 1, < 3, < 5, < 10, < — 4, хз — х4 < -8.
24.4-3. Может ли вес кратчайшего пути, исходящего из новой вершины оо в графе ограничений, быть положительным? Объясните свой ответ. 24.4-4. Сформулируйте задачу о кратчайшем пути между парой заданных вершин в виде задачи линейного программирования. 24.4-5. Покажите, как можно модифицировать алгоритм Беллмана-Форда, чтобы он позволял решить систему разностных ограничений с гн неравенствами и п неизвестными в течение времени О (пт).
24.4-6. Предположим, что в дополнение к системе разностных ограничений накладываются ограничения-равенства (ейиай4у сопзПа1п4з), имеющие вид хз = х + Ьь. Покажите, как адаптировать алгоритм Беллмана-Форда, чтобы с его помощью можно было решать системы ограничений такого вида. 24.4-7. Покажите, как можно решить систему разностных ограничений с помощью алгоритма, подобного алгоритму Беллмана-Форда, который обрабатывает граф ограничений, не содержащий дополнительную вершину оо.
*24.4-8. Пусть Ах < Ь вЂ” система гп разностных ограничений с и неизвестными. Покажите, что при обработке графа ограничений, соответствующего этой системе, алгоритм Беллмана-Форда максимизирует сумму '> '„" хп где вектор х удовлетворяет системе Ах < Ь, а все компоненты х;— неравенству хз < О. *24.4-9. Покажите, что в процессе обработки графа ограничений, соответствующего системе разностных ограничений Ах < Ь„алгоритм БеллманаФорда минимизирует величину (шах(х ) — ш1п (х;1), где х; — компоненты вектора х, удовлетворяющего системе Ах < Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
