Алгоритмы - построение и анализ (1021735), страница 141
Текст из файла (страница 141)
При другой технологии может потребоваться, чтобы деталь устанавливалась после применения клея, но не позже, чем когда он "схватится" наполовину. В этом случае получаем пару ограничений хз > хз и хз < хг + 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), где х; — компоненты вектора х, удовлетворяющего системе Ах < Ь.
Объясните, как можно использовать этот факт, если алгоритм применяется для составления расписания строительных работ. Часть Ч1. Алгоритмы для работы с графами 694 24.4-10. Предположим, что каждая строка матрицы А задачи линейного программирования Ах < Ь соответствует либо разностному ограничению, либо ограничению на одну переменную вида кч < Ьь или — х; < Ьь. Покажите, как адаптировать алгоритм Беллмана-Форда для решения систем ограничений этого вида.
24.4-11. Разработайте эффективный алгоритм решения системы разностных ограничений Ах < Ь, в которой все элементы вектора Ь являются действительными числами, а все неизвестные х; должны быть целыми числами. * 24.4-12. Разработайте эффективный алгоритм решения системы разностных ограничений Ах < Ь, в которой все элементы вектора Ь являются действительными числами, а определенное подмножество некоторых (но не обязательно всех) неизвестных х; должны быть целыми числами. 24.5 Доказательства свойств кратчайших путей Корректность аргументов, которые используются в этой главе, основана на неравенстве треугольника, свойстве верхней границы, свойстве отсутствия пути, свойстве сходимости, свойстве ослабления пути и свойстве подграфа предшествования.
В начале главы эти свойства сформулированы без доказательств, которые представлены в настоящем разделе. Неравенство треугольника При изучении поиска в ширину (раздел 22.2) в лемме 22.1 доказано простое свойство, которым обладают кратчайшие расстояния в невзвешенных графах. Неравенство треугольника обобщает это свойство для взвешенных графов. Лемма 24.10 (Неравенство треугольника). Пусть С = (У, Е) — взвешенный ориентированный граф с весовой функцией ю: Š— Н и истоком ж Тогда для всех ребер (и, о) е Е выполняется неравенство б(а,о) < б(а,и)+ю(и,о). Доказательсглво. Предположим, что существует кратчайший путь р из истока а в вершину о.
Тогда вес этого пути р не превышает веса любого другого пути из вершины а в вершину о. В частности, вес пути р не превышает веса пути, состоящего из кратчайшего пути из исходной вершины в в вершину и и ребра (и, о). В упражнении 24.5-3 предлагается рассмотреть случай, в котором не существует кратчайшего пути из вершины а в вершину о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
