Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 143
Текст из файла (страница 143)
Объясните, как можно использовать этот факт, если алгоритм применяется для составления расписания строительных работ. Часть Ч1. Алгоритмы для работы с графами 694 24.4-10. Предположим, что каждая строка матрицы А задачи линейного программирования Ах < Ь соответствует либо разностному ограничению, либо ограничению на одну переменную вида кч < Ьь или — х; < Ьь. Покажите, как адаптировать алгоритм Беллмана-Форда для решения систем ограничений этого вида. 24.4-11. Разработайте эффективный алгоритм решения системы разностных ограничений Ах < Ь, в которой все элементы вектора Ь являются действительными числами, а все неизвестные х; должны быть целыми числами.
* 24.4-12. Разработайте эффективный алгоритм решения системы разностных ограничений Ах < Ь, в которой все элементы вектора Ь являются действительными числами, а определенное подмножество некоторых (но не обязательно всех) неизвестных х; должны быть целыми числами. 24.5 Доказательства свойств кратчайших путей Корректность аргументов, которые используются в этой главе, основана на неравенстве треугольника, свойстве верхней границы, свойстве отсутствия пути, свойстве сходимости, свойстве ослабления пути и свойстве подграфа предшествования.
В начале главы эти свойства сформулированы без доказательств, которые представлены в настоящем разделе. Неравенство треугольника При изучении поиска в ширину (раздел 22.2) в лемме 22.1 доказано простое свойство, которым обладают кратчайшие расстояния в невзвешенных графах. Неравенство треугольника обобщает это свойство для взвешенных графов. Лемма 24.10 (Неравенство треугольника).
Пусть С = (У, Е) — взвешенный ориентированный граф с весовой функцией ю: Š— Н и истоком ж Тогда для всех ребер (и, о) е Е выполняется неравенство б(а,о) < б(а,и)+ю(и,о). Доказательсглво. Предположим, что существует кратчайший путь р из истока а в вершину о. Тогда вес этого пути р не превышает веса любого другого пути из вершины а в вершину о. В частности, вес пути р не превышает веса пути, состоящего из кратчайшего пути из исходной вершины в в вершину и и ребра (и, о). В упражнении 24.5-3 предлагается рассмотреть случай, в котором не существует кратчайшего пути из вершины а в вершину о. И Глава 24.
Кратчайшие пути из одной вершины 695 Влияние ослабления на оценки кратчайшего пути Приведенная ниже группа лемм описывает, какому воздействию подвергаются оценки кратчайшего пути, когда выполняется последовательность шагов ослабления ребер взвешенного ориентированного графа, инициализированного процедурой 1ьлт1илгн Япчсьи Яоцксе. Лемма 24.11 (Свойство верхней границы).
Пусть С = (К Е) — взвешенный ориентированный граф с весовой функцией и: Š— В.. Пусть з Е Ъ' — исток, а граф инициализировал процедурой 1н|т1лш2н Япчоьн Боцкси(С, а). Тогда для всех вершин и е У выполняется неравенство Ы[о] > б(э,е), и этот инвариант поддерживается в ходе всей последовательности этапов ослабления ребер графа С. Более того, как только атрибут Н [с] достигает своей нижней границы б (а, и), он в дальнейшем не изменяется. Доказашельслыо. Докажем инвариант Н[е] > б(э,ю) для всех вершин е е Ъ", воспользовавшись индукцией по числу шагов ослабления. В качестве базиса индукции воспользуемся неравенством Н [и] > б (а, и), которое, очевидно, истинно непосредственно после инициализации, поскольку Ы [а] = = 0 > б (э, а) (заметим, что величина б (э, э) = — со, если вершина а находится в цикле с отрицательным весом; в противном случае б (э, а) = 0), и из Н [е] = со следует, что с( [о] > б (э, е) для всех вершин и е Ъ' — (а).
В качестве шага индукции рассмотрим ослабление ребра (и, е). Согласно гипотезе индукции, для всех вершин х е У перед ослаблением выполняется неравенство о*[х] > б (э, х). Единственное значение и', которое может измениться— это значение Ы [е]. Если оно изменяется, мы имеем с([е] = с([и]+ ш(и,о) > б(з,и) + ш(и,п) > б(э,е), где первое неравенство следует из гипотезы индукции, а второе — из неравенства треугольника, так что инвариант сохраняется. Чтобы увидеть, что значение и'[и] не будет изменяться после того, как становится справедливым соотношение Ы [п] = б (э, е), заметим, что по достижении своей нижней границы это значение больше не сможет уменьшаться, поскольку, как уже было показано, и' [е] > б (э, и).
Оно также не может возрастать, поскольку ослабление не увеличивает значений Н. Следствие 24.12 (Свойство отсутствия пути). Предположим, что во взвешенном ориентированном графе С = (Ъ; Е) с весовой функцией ш: Š— зь отсутствуют пути, соединяющие исток а е У с данной вершиной и Е У. Тогда после инициализации графа процедурой 1ьлт~Аш2е Бпчо1.е 500кси(С, э) мы имеем 0 [и] = б (э, и) = оо, и это равенство сохраняется в качестве инварианта в ходе выполнения произвольной последовательности шагов ослабления ребер графа С. Часть Ч1.
Алгоритмы для работы с графами б96 Доказательство. Согласно свойству верхней границы, всегда выполняется соот- ношение оо = Б (в, и) < с1 [и], так что с1 [и] = оо = б (в, и). Лемма 24.13. Пусть С = (У, Е) — взвешенный ориентированный граф с весовой функцией ю: Е -+ В., и пусть (и, и) й Е.
Тогда непосредственно после ослабления ребра (и, и) при помощи процедуры КБ.Ах(и, и, ю) выполняется неравенство сс[и] < с1[и]+ ю(и,и). Доказалсельслсво. Если непосредственно перед ослаблением ребра (и, и) выполняется неравенство Н [и] > с1 [и] + ю (и, и), то после этой операции оно преобразуется в равенство с1 [и] = с1 [и] + ю (и, и).
Если же непосредственно перед ослаблением выполняется неравенство с( [и) < с1 [и) + ю (и, и), то в процессе ослабления ни значение с1 [и], ни значение с1 [и] не изменяются, так что после данной операции с1[и] < И[и) + ю(и,и). Лемма 24.14 (Свойство сходимости). Пусть С = (У,Е) — взвешенный ориентированный граф с весовой функцией ю: Š— > К, в Е ~' — исток, а в - и -+ и— кратчайший путь в графе С для некоторых его вершин и, и е У. Предположим„ что граф С инициализировал процедурой 1ьлтслшхн Зисс1.н Боцн~н(С, в), после чего выполнена последовательность этапов ослабления, включающая вызов процедуры Ка.лх(и, и, ю).
Если в некоторый момент времени до вызова выполняется равенство с1 [и] = б (в, и), то в любой момент времени после вызова справедливо равенство с1[и] = 6(в,и). Доказательство. Согласно свойству верхней границы, если в некоторый момент до ослабления ребра (и, и) выполняется равенство с1 [и) = б (в, и), то оно остается справедливым и впоследствии. В частности, после ослабления ребра (и, и) имеем с1 [и) < с1 [и] + ю (и, и) = д (в, и) + и (и, и) = б (в, и), где неравенство следует из леммы 24.13, а последнее равенство — из леммы 24.1.
В соответствии со свойством верхней границы с([и] > б(в,и), откуда можно сделать вывод о том, что с([и] = 6(в, и), и зто равенство впоследствии сохраняется. И Лемма 24.15 (Свойство ослабления пути). Пусть С = (Ъ", Е) — взвешенный ориентированный граф с весовой функцией ю: Š— Н., а ай У вЂ” исток. Рассмотрим произвольный кратчайший путь р = (ио, из,..., иь) из истока в = ио в вершину иь. Если граф С инициализирован процедурой 1ьлтслшгн Инчон Боцнсн(С, в), а затем выполнена последовательность ослаблений ребер (ио, ис), (им из), ..., (иь ыиь) в указанном порядке, то после этих ослаблений и в любой момент времени впоследствии выполняется равенство с1[иь] = б(в,иь).
Это свойство Глава 24. Кратчайшие пути из одной вершины 697 справедливо независимо от того, производятся ли ослабления на других ребрах, включая ослабления, которые чередуются с ослаблениями ребер пути р. Доказательство. По индукции покажем, что после ослабления на 1-м ребре пути р выполняется равенство а [е!] = б (а, о!). В качестве базиса примем ! = О; перед тем, как будет ослаблено хоть одно ребро, входящее в путь р, после процедуры инициализации очевидно, что а[по] = И[в] = О = д(в,в).
Согласно свойству верхней границы, значение а' [в] после инициализации больше не изменяется. На очередном шаге индукции предполагается, что выполняется равенство а [о! !] = 6(в,п! !), и рассматривается ослабление ребра (о! !,о!). Согласно свойству сходимости, после этого ослабления выполняется равенство а [о!] = = д (в, о!), которое впоследствии сохраняется. Ослабление и деревья кратчайших путей Теперь покажем, что после того, как в результате последовательности ослаблений оценки кратчайших путей сойдутся к весам кратчайших путей, подграф предшествовання С„, образованный полученными значениями л, будет деревом кратчайших путей для графа С. Начнем с приведенной ниже леммы, в которой показано, что подграф предшествования всегда образует корневое дерево с корнем в истоке.
Лемма 24.16. Пусть С = ()г, Е) — взвешенный ориентированный граф с весовой функцией ю: Е В., а в е Ъ' — исток. Предполагается также, что граф С не содержит циклов с отрицательным весом, достижимых из истока в. Тогда после инициализации графа с помощью процедуры 1ы!т!Аь!Ее 8!хб!.е БО(лье(С, в) подграф предшествования С образует корневое дерево с корнем в, а любая последовательность шагов ослабления ребер графа С поддерживает это свойство в качестве инварианта.
Доказаюиельсогво. Вначале единственной вершиной графа С„является исток, и лемма тривиальным образом выполняется. Рассмотрим подграф предшествования С„, возникающий в результате последовательности этапов ослабления. Сначала докажем, что этот граф — ациклический. Чтобы получить противоречие, предположим, что после некоторого шага ослабления в графе С„создается цикл. Пусть это цикл с = (оо, ег,..., оь), где оь = ео. Тогда при 1 = 1, 2,..., /с выполняется равенство л [п!] = п! ь и без потери общности можно считать, что цикл был создан в результате ослабления ребра (оь з, оь) графа С„.
Утверждается, что все вершины цикла с достижимы из истока ж Почему7 Для каждой вершины цикла с существует предшественник (т.е. значение соответствующего атрибута отлично от значения мп.), поэтому каждой из этих вершин Часть Ч1. Алгоритмы для работы с графами 698 сопоставляется конечная оценка кратчайшего пути, когда ее атрибуту я присваивается значение, отличное от значения нп.. Согласно свойству верхней границы, каждой вершине цикла с соответствует вес кратчайшего пути, из чего следует, что она достижима из истока а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
